We can divide all people into different sets based on the languages they understand and speak. Everyone in a set can communicate with others in the same set—that is, they can understand the languages spoken by each other. Finally, we subtract the number of people in the largest set from the total number of people, which gives us the minimum number of people that need to be excluded.
Step 1: Convert Strings to IDs
All the information provided in the input appears in string form, which is extremely inconvenient for graph construction and traversal. Therefore, we first record strings and assign corresponding IDs using a dictionary and an array.
The record_people function records each line of input, then converts them into Person structs and stores them in the people array, allowing direct access to each person via their ID later. The build_language_dict function creates a HashMap with String keys and usize values, enabling us to find the corresponding value by language name. After converting all strings to IDs, we can begin constructing the graph.
Step 2: Construct the Language Conversion Graph
For each person, they can convert the languages they understand to the language they speak. This is equivalent to drawing a directed edge from the understood language to the spoken language. By traversing each person in this way, we can build a graph of language conversion.
The function’s end uses a HashSet for edge deduplication. Values in the array are placed into a HashSet and then back into the array to achieve deduplication.
Step 3: Verify Two People Can Communicate
After the language graph is established, a function is needed to verify whether two people can understand each other’s spoken languages. If one person’s spoken language can be converted into one of the languages the other person understands, then it can be said that the second person can understand the first person’s speech, and vice versa. This is implemented using a naive DFS algorithm.
The test_biconnected function encapsulates test_connected_dfs. By calling this subfunction twice, it verifies whether two people can communicate.
Step 4: Construct a Disjoint Set Union
When analyzing the relationships between each person, a disjoint set union (DSU) data structure is used for organization. Everyone in a DSU can communicate with each other, and if two people from different DSUs can communicate, those DSUs are merged.
Path compression is used in the DSU implementation. Each call to get_fa updates the node’s parent to the root node of the set, thereby flattening the DSU and optimizing query efficiency.
Step 5: Obtain the Largest DSU Count
An array records the count of each DSU, and each node’s DSU is identified using get_fa, updating the count accordingly. The function returns the count of the largest DSU.
The provided code demonstrates a method for solving the problem by dividing people into sets based on language understanding and speaking, using data structures and algorithms such as hash maps, graphs, DFS, and disjoint set unions to efficiently find the minimum number of people that need to be excluded to allow for universal communication within the remaining group.
In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure. If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems. In the optimization literature this relationship is called the Bellman equation. –Wikipedia
I’m not sure how much you understood from Wikipedia’s description, but I think starting with a simple example would be better.
The Fibonacci Sequence: A Gateway to Dynamic Programming
At its core, the Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Mathematically, it’s defined as:
This simple formula lays the foundation for understanding the three pillars of dynamic programming: State, State Transition Equation, Boundary
State
In dynamic programming, the ‘state’ encapsulates the current situation in our problem-solving context. For the Fibonacci sequence, the state is represented by $F_i$, indicating the i-th number in the sequence. Understanding the state is crucial because it defines what we’re trying to compute.
State Transition Equation
The state transition equation describes how to transition from one state to the next. For the Fibonacci sequence, this is given by $F_i = F_{i-1} + F_{i-2}$. It shows how the current state (F_i) is derived from the previous two states ($F_{i-1}$ and $F_{i-2}$). This equation is the heart of dynamic programming, guiding how we break down problems into smaller, manageable pieces.
Boundary
Boundary conditions provide the starting points or base cases for our computation. For the Fibonacci sequence, these are $F_1$ = 1 and $F_0$ = 0. They’re essential because they prevent infinite recursion and ensure that our dynamic programming algorithm has a clear and definitive starting point.
Concepts end here. Let’s start to code.
Implementation of Fibonacci Sequence
1 2 3 4 5 6 7
defmain(): n = int(input()) fib = [0] * (n + 2) fib[1] = 1 for i inrange(2, n + 2): fib[i] = fib[i - 1] + fib[i - 2] print(fib[n])
Here, we’ve crafted a function named main that computes the nth Fibonacci number. This function prompts for an input, n, and initializes an array fib with a length of n + 2 (extra two is just for safety) to store the Fibonacci sequence. It sets the second element (index 1) to 1, reflecting the sequence’s start. Through a loop, it then calculates each Fibonacci number by summing the two preceding numbers and stores them in the array. Finally, it prints the nth Fibonacci number.
We’ve successfully solved our first dynamic programming problem with this implementation. However, the code can be streamlined for better readability. Let’s work on making it more intuitive.
Implement Fibonacci Recursively
1 2 3 4 5 6
deffib(i): return i if i < 2else fib(i - 1) + fib(i - 2)
defmain(): n = int(input()) print(fib(n))
This recursive implementation is more intuitive and direct, using just a single line of code to define the Fibonacci computation. Let’s execute this function:
1 2 3
35 9227465 The fib function took 2.1213817596435547 seconds to execute.
Okay, everything looks fine… Really? Let’s see the third line of output.
1
The fib function took 2.1213817596435547 seconds to execute.
The function runs extremely slow. What happened there? Let’s check how many times does function fib() be called.
1 2 3 4
35 9227465 The fib function took 3.8617589473724365 seconds to execute. The fib function was called 29860703 times.
The observed slowdown in executing the recursive Fibonacci function, taking over 2 seconds to compute fib(35) and resulting in an astonishing 29,860,703 function calls, highlights a critical inefficiency inherent in the naive recursive approach. This inefficiency is primarily due to the excessive number of redundant calls for calculating the same Fibonacci numbers multiple times.
To understand why so many calls are made, consider how the recursive function works for fib(n): it calls fib(n-1) and fib(n-2). Both of these calls then recursively invoke further fib calculations, leading to a combinatorial explosion of function calls. Many of these calls are repeated; for instance, fib(2) is calculated multiple times across different branches of the recursion tree.
Memorized search
Now let’s try to solve the problem. To address this inefficiency, a technique known as memoization can be applied. Memoization is a form of caching where the results of expensive function calls are stored, so that if the same inputs occur again, the function can return the stored result instead of recalculating it. Applying memoization to the Fibonacci sequence means that once we calculate fib(n), we store its value. If fib(n) is needed again, we simply retrieve the stored value instead of recalculating it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
cache = []
deffib(i): global cache if cache[i] != 0: return cache[i] cache[i] = i if i < 2else fib(i - 1) + fib(i - 2) return cache[i]
defmain(): global cache n = int(input()) cache = [0] * (n + 1) result = fib(n) print(result)
Let’s run and check the performance.
1 2 3
35 9227465 The fib function took 1.539999993838137e-05 seconds to execute.
This performance boost is due to the drastic reduction in the number of calls to the fib function, as each Fibonacci number is calculated only once. Now it has the same runtime as the method use array. But can we make it better?
Rolling array
Let’s revisit our initial dynamic programming approach to computing the nth Fibonacci number. In this version, we allocate an array large enough to hold all Fibonacci numbers up to n. However, we notice a key optimization point: to calculate any Fibonacci number, we only ever need the last two numbers in the sequence.
1 2 3 4 5 6 7
defmain(): n = int(input()) fib = [0] * (n + 2) fib[1] = 1 for i inrange(2, n + 2): fib[i] = fib[i - 1] + fib[i - 2] print(fib[n])
We can find that when we try to get n-th Fibonacci Number. It will create an array with n variables. But each time we only use fib[i],fib[i - 1], and fib[i - 2]. So we can track only these three variables.
1 2 3 4 5 6 7 8 9
defmain(): n = int(input()) fib_i = 1 fib_i_prev = 0 start_time = time.perf_counter() for i inrange(2, n + 1): fib_i, fib_i_prev = fib_i + fib_i_prev, fib_i end_time = time.perf_counter() print(fib_i)
By maintaining just two variables, fib_i and fib_i_prev, and updating them in each iteration, we significantly reduce the space complexity of our program to O(1), while still retaining a time complexity of O(n). This rolling array technique optimizes our solution, making it both space-efficient and fast for calculating Fibonacci numbers. But what happened if it is still too slow.
Matrix Acceleration
At first glance, achieving $O(1)$ space complexity and $O(n)$ time complexity might seem like the pinnacle of optimization for any algorithm. This might lead one to prematurely conclude that there’s no further scope for enhancement. However, this article aims to challenge that notion by introducing a mathematical strategy capable of significantly boosting our program’s efficiency, especially for large-scale problems.
Consider when n scales to $10 ^ 8$. At this magnitude, an algorithm with $O(n)$ time complexity begins to show its limitations, as evidenced by an execution time exceeding 10 seconds. Such scenarios demand a more sophisticated approach to reduce the computational complexity further.
Understanding the Fibonacci Sequence with Matrix Exponentiation
The Fibonacci sequence is a classic example where exponential growth can cause simple recursive or iterative solutions to falter due to their linear or pseudo-linear time complexities. To compute the n-th Fibonacci number efficiently for very large n, we employ matrix exponentiation, a method that allows us to achieve a time complexity of $O(log_2{n})$.
deffib(n): if n < 2: return n st = [[1, 0, 0]] update_matrix = qpow([[1, 1, 0], [1, 0, 1], [0, 0, 0]], n - 1) return matrix_multiply(st, update_matrix)[0][0] % MOD
defqpow(a, n): if n == 1: return a if n % 2 == 0: return qpow(matrix_multiply(a, a), n // 2) return matrix_multiply(a, qpow(matrix_multiply(a, a), n // 2))
defmatrix_multiply(a, b): ans = [[0] * len(b[0]) for _ inrange(len(a))] for i inrange(len(a)): for j inrange(len(b[0])): for k inrange(len(b)): ans[i][j] += a[i][k] * b[k][j] % MOD return ans
if __name__ == "__main__": main()
Implementation Details
The provided Python code showcases an efficient way to compute large Fibonacci numbers modulo MOD = 1000000007, ensuring that the result stays within integer limits suitable for many computational environments.
Matrix Power Quickening (qpow): The heart of this optimization lies in the qpow function, which implements fast exponentiation for matrices. Instead of naively multiplying the matrix n times, this function recursively squares the matrix, reducing the exponent by half each time, effectively turning the time complexity from $O(n)$ to $O(log_2{n})$.
Matrix Multiplication (matrix_multiply): This function multiplies two matrices, a crucial operation in our exponentiation process. Matrix multiplication is used both in the exponentiation process and in calculating the final Fibonacci number from the base case matrix.
Computing Fibonacci (fib): The fib function initializes a state matrix representing the base case of Fibonacci calculation. It then calculates the power of the transition matrix, which encodes the Fibonacci recurrence relation, using the optimized qpow method. The result is a matrix that, when multiplied by the state matrix, yields the n-th Fibonacci number.
Generalization: This method is not limited to Fibonacci numbers; it can be generalized to other problems that can be expressed in terms of matrix exponentiation, showcasing the versatility of the technique.
This Python project is designed to automate chat responses in the popular messaging application, WeChat (微信), using OpenAI’s GPT-3 model. The project leverages the power of GPT-3’s language understanding capabilities to generate contextually relevant responses to incoming messages.
Project Design
The project is structured around two main functions: the GPT function, which interacts with the GPT-3 model, and the main function, which handles the user interface and message processing in WeChat.
GPT Function
The GPT function is designed to generate responses using the GPT-3 model. It takes as input a string text representing the incoming message and a list record that maintains the conversation history. The function appends the incoming message to the conversation record, sets the OpenAI API key, and creates a completion using the OpenAI API. The completion is a response generated by the GPT-3 model based on the conversation history. The function then extracts the assistant’s message from the response, appends it to the conversation record, and returns it.
# Define a function to handle the interaction with the GPT-3 model defGPT(text: str, record: List[dict]) -> str: # Append the user's message to the conversation record record.append({"role": "user", "content": text}) # Print the user's message for debugging purposes print(text) # Set the OpenAI API key openai.api_key = apiKey # Define the model ID id = "gpt-3.5-turbo" # Initialize a question string with the user's text question = "###" + text + "###" # Create a completion using the OpenAI API response = openai.ChatCompletion.create( model=id, messages=record, temperature=0.1, top_p=0.1, max_tokens=2048, ) # Extract the total token usage from the response for debugging purposes usage = response.usage["total_tokens"] # Extract the content from the assistant's message in the response response = response["choices"][0]["message"]["content"] # Append the assistant's message to the conversation record record.append({"role": "assistant", "content": response}) # Return the assistant's response return response
Main Function
The main function is the core of the project. It initializes the conversation with a user’s template and creates a WindowControl object for the WeChat window. It then creates a ListControl object for the chat list in the window and loads reply data from a CSV file.
The function then enters a loop where it continuously checks for unread messages in the chat. When an unread message is found, it clicks on it, extracts the content of the last message, and generates a reply using the GPT function. If the conversation record has more than six messages, it trims it down to maintain a manageable size. The function then prepares the reply to be sent. If there is a reply, it sends it; if there is no reply, it sends a default message.
The script is designed to handle exceptions gracefully. If an error occurs during the execution of the main function, it prints the error and breaks the loop.
defmain(): # Initialize the conversation with the user's template mem = [{"role": "user", "content": template}] try: # Create a WindowControl object for the "微信" window wx = WindowControl(Name="微信") print(wx) wx.SwitchToThisWindow() # Create a ListControl object for the "会话" list in the window chat = wx.ListControl(Name="会话") print("Find chat and combine:", chat) except Exception as e: print(f"Error: {e}") return
# Main loop whileTrue: try: # Look for unread messages in the chat unread = chat.TextControl(searchDepth=4) # Wait until an unread message appears whilenot unread.Exists(0): pass print("Find unread:", unread) # If there is an unread message, click on it ifnot unread.Name: continue unread.Click(simulateMove=False) # Extract the content of the last message last_msg = wx.ListControl(Name="消息").GetChildren()[-1].Name print("Last message:", last_msg) # Generate a reply using the GPT-3 model reply = GPT(last_msg, mem) # If the conversation record has more than 6 messages, trim it down iflen(mem) > 6: mem = mem[3:] mem = [{"role": "user", "content": template}] + mem print("memory size:", len(mem)) # Prepare the reply to be sent ar = [reply] # If there is a reply, send it if ar: wx.SwitchToThisWindow() wx.SendKeys(ar[0].replace( "{br}", "{Shift}{Enter}"), waitTime=0) wx.SendKeys("{Enter}", waitTime=0) wx.TextControl(SubName=ar[0][:5]).Click() else: # If there is no reply, send a default message wx.SwitchToThisWindow() wx.SendKeys("Unknown", waitTime=0) wx.SendKeys("{Enter}", waitTime=0) wx.TextControl(SubName=last_msg[:5]).Click() except Exception as e: print(f"Error: {e}") break
Execution
The script is designed to be run directly. If the script is run directly (i.e., not imported as a module), it calls the main function and starts the automated chat response process.
Conclusion
In summary, this Python project is a sophisticated example of how to use OpenAI’s GPT-3 model to automate responses in a chat application. It demonstrates how to interact with the GPT-3 model, handle user interface elements in a chat application, and manage conversation history for context-aware responses. The project is a testament to the potential of AI in automating tasks and enhancing user experience in messaging platforms.
from typing importList import pandas as pd import numpy as np from uiautomation import WindowControl import openai
apiKey = ""
template = ""
# Define a function to handle the interaction with the GPT-3 model defGPT(text: str, record: List[dict]) -> str: # Append the user's message to the conversation record record.append({"role": "user", "content": text}) # Print the user's message for debugging purposes print(text) # Set the OpenAI API key openai.api_key = apiKey # Define the model ID id = "gpt-3.5-turbo" # Initialize a question string with the user's text question = "###" + text + "###" # Create a completion using the OpenAI API response = openai.ChatCompletion.create( model=id, messages=record, temperature=0.1, top_p=0.1, max_tokens=2048, ) # Extract the total token usage from the response for debugging purposes usage = response.usage["total_tokens"] # Extract the content from the assistant's message in the response response = response["choices"][0]["message"]["content"] # Append the assistant's message to the conversation record record.append({"role": "assistant", "content": response}) # Return the assistant's response return response
# Main function defmain(): # Initialize the conversation with the user's template mem = [{"role": "user", "content": template}] try: # Create a WindowControl object for the "微信" window wx = WindowControl(Name="微信") print(wx) wx.SwitchToThisWindow() # Create a ListControl object for the "会话" list in the window chat = wx.ListControl(Name="会话") print("Find chat and combine:", chat) except Exception as e: print(f"Error: {e}") return
# Main loop whileTrue: try: # Look for unread messages in the chat unread = chat.TextControl(searchDepth=4) # Wait until an unread message appears whilenot unread.Exists(0): pass print("Find unread:", unread) # If there is an unread message, click on it ifnot unread.Name: continue unread.Click(simulateMove=False) # Extract the content of the last message last_msg = wx.ListControl(Name="消息").GetChildren()[-1].Name print("Last message:", last_msg) # Generate a reply using the GPT-3 model reply = GPT(last_msg, mem) # If the conversation record has more than 6 messages, trim it down iflen(mem) > 6: mem = mem[3:] mem = [{"role": "user", "content": template}] + mem print("memory size:", len(mem)) # Prepare the reply to be sent ar = [reply] # If there is a reply, send it if ar: wx.SwitchToThisWindow() wx.SendKeys(ar[0].replace( "{br}", "{Shift}{Enter}"), waitTime=0) wx.SendKeys("{Enter}", waitTime=0) wx.TextControl(SubName=ar[0][:5]).Click() else: # If there is no reply, send a default message wx.SwitchToThisWindow() wx.SendKeys("Unknown", waitTime=0) wx.SendKeys("{Enter}", waitTime=0) wx.TextControl(SubName=last_msg[:5]).Click() except Exception as e: print(f"Error: {e}") break
# Run the main function if this script is run directly if __name__ == "__main__": main()
This article presents a powerful translation tool that combines the advanced GPT-3.5 Turbo language model by OpenAI with the user-friendly Wox launcher plugin system. The tool identifies the input text’s language, translates Chinese text to English or English text to Chinese, and provides an explanation and example in Chinese. The article explains the core functionality, interaction with Wox launcher, and clipboard integration using the pyperclip library. We also provide an example of the code to demonstrate its implementation.
Introduction
In this article, we introduce a powerful translation tool that integrates the cutting-edge GPT-3.5 Turbo language model by OpenAI with the user-friendly Wox launcher plugin system. This tool is designed to identify the input text’s language, translate Chinese text to English or other languages’ text to Chinese, and provide an explanation and an example in Chinese.
Harnessing GPT-3.5 Turbo
The GPT-3.5 Turbo language model by OpenAI is known for its ability to handle complex language tasks efficiently. This translation tool utilizes the model’s capabilities by implementing a translate function that takes a text input, constructs a formatted question to send to the model, and receives a response. The response is then parsed, extracting the relevant information and returning it as a list. You can get more information about ChatAPI here: openAI documentation
deftranslate(text: str) -> list: openai.api_key = KEY id = "gpt-3.5-turbo" question = """ 1: Check the text's language 2: If language != Chinese { translate it into Chinese } else { translate it into English } 3: Desired format: language: -||- translate: -||- explanation: -||- example: -||- ## Text1: ###Hello### language: English translate: 你好 explanation: 这是常用的问候语 example: Hello, how are you today? ## Text2: ###你好### language: Chinese translate: Hello explanation: 这是常用的问候语 example: 你好,你今天怎么样? ## Text3: ###こんにちは### language: Japanese translate: 你好 explanation: 这是常用的问候语 example: こんにちは、今日はお元気ですか? ## Text4: ###안녕하세요### language: Korean translate: 你好 explanation: 这是常用的问候语 example: 안녕하세요, 오늘은 어떻게 지내세요? ## Text5: """ question += "###" + text + "###" response = openai.ChatCompletion.create( model=id, messages=[{ "role": "user", "content": question }], temperature=0, top_p=0.1, max_tokens=2048, ) usage = response.usage["total_tokens"] response = response["choices"][0]["message"]["content"] # print(response) response = list(response.split("\n")) response.append("usage: " + str(usage)) return response
Integrating with Wox Launcher
The Wox launcher plugin system offers a convenient and interactive interface for users to engage with the translation tool. By creating a main class that inherits from the Wox class, the tool defines a query method to handle user input and display results. When a user enters a keyword ending with an ampersand (&), the code calls the translate function, displaying the response as a list of selectable items. You can get more information about the Wox launcher plugin development here: Wox Documentation
To enhance user experience, the script incorporates the pyperclip library, enabling users to copy the selected text to the clipboard with just a click. Upon selecting a result, the copy method is triggered, effortlessly copying the text for users to paste into other applications.
enumColor { // Defines an enum called 'Color' Red, // Enum variant representing the color red Black, // Enum variant representing the color black } structNode<K, V> { // Defines a struct called 'Node' with generic parameters 'K' and 'V' key: K, // Field representing the key of the node value: V, // Field representing the value of the node color: Color, // Field representing the color of the node, which is of type 'Color' enum left: Option<Box<Node<K, V>>>, // Field representing the left child node of the current node (if exists); it is an Option type and wrapped inside a box right: Option<Box<Node<K, V>>>, // Field representing the right child node of the current node (if exists); it is an Option type and wrapped inside a box }
pubstructRBTree<K: Ord, V> { // Defines a struct called 'RBTree' with generic parameters 'K' and 'V'; 'K' must implement 'Ord' trait root: Option<Box<Node<K, V>>>, // Field representing the root node of the red-black tree; it is an Option type and wrapped inside a box }
// Defines a private method called 'rotate_left' that takes a mutable reference to a 'Node' struct fnrotate_left(mut node: &mut Node<K, V>) { // Takes ownership of the right child node of the given node letmut right = node.right.take().unwrap(); // Moves the left child of the right child node to the right child of the given node node.right = right.left.take(); // Sets the parent of the right child node as the given node and returns the right child node right.left = Some(std::mem::replace(&mut node, right)); // Sets the parent of the left child node of the given node to the given node ifletSome(refmut left) = node.left { left.parent = Some(node); } // Sets the parent of the right child node of the given node to the given node ifletSome(refmut right) = node.right { right.parent = Some(node); } // Updates the size of the given node node.update_size(); }
// Defines a private method called 'rotate_right' that takes a mutable reference to a 'Node' struct fnrotate_right(mut node: &mut Node<K, V>) { // Takes ownership of the left child node of the given node letmut left = node.left.take().unwrap(); // Moves the right child of the left child node to the left child of the given node node.left = left.right.take(); // Sets the parent of the left child node as the given node and returns the left child node left.right = Some(std::mem::replace(&mut node, left)); // Sets the parent of the left child node of the given node to the given node ifletSome(refmut left) = node.left { left.parent = Some(node); } // Sets the parent of the right child node of the given node to the given node ifletSome(refmut right) = node.right { right.parent = Some(node); } // Updates the size of the given node node.update_size(); } }
// Defines a private method called 'fix_after_insertion' that takes a mutable reference to a 'Node' struct and an optional mutable reference to the root node fnfix_after_insertion( mut node: &mut Node<K, V>, root: Option<&mutBox<Node<K, V>>>, ) { // Sets the color of the inserted node as 'Red' node.color = Color::Red; // Checks if the node is not the root node and its parent's color is 'Red' while node != root.unwrap() && node.parent().unwrap().color == Color::Red { letparent = node.parent().unwrap(); letgrandparent = node.grandparent().unwrap(); // Checks if the parent is the left child of its grandparent if parent == grandparent.left.as_ref().unwrap() { letuncle = grandparent.right.as_ref(); // Checks if the uncle node exists and its color is 'Red' if uncle.is_some() && uncle.unwrap().color == Color::Red { // Recolors the parent, uncle, and grandparent nodes, and sets the current node to its grandparent parent.color = Color::Black; uncle.unwrap().color = Color::Black; grandparent.color = Color::Red; node = grandparent; } else { // Checks if the current node is the right child of its parent; if so, rotates it to the left around the parent node if node == parent.right.as_ref().unwrap() { node = parent; RBTree::rotate_left(parent); } // Recolors the parent and grandparent nodes, and rotates the grandparent node to the right parent.color = Color::Black; grandparent.color = Color::Red; RBTree::rotate_right(grandparent); } } else { letuncle = grandparent.left.as_ref(); // Checks if the uncle node exists and its color is 'Red' if uncle.is_some() && uncle.unwrap().color == Color::Red { // Recolors the parent, uncle, and grandparent nodes, and sets the current node to its grandparent parent.color = Color::Black; uncle.unwrap().color = Color::Black; grandparent.color = Color::Red; node = grandparent; } else { // Checks if the current node is the left child of its parent; if so, rotates it to the right around the parent node if node == parent.left.as_ref().unwrap() { node = parent; RBTree::rotate_right(parent); } // Recolors the parent and grandparent nodes, and rotates the grandparent node to the left parent.color = Color::Black; grandparent.color = Color::Red; RBTree::rotate_left(grandparent); } } } root.unwrap().color = Color::Black; }
// Defines a public method called 'insert' that takes a key and a value and adds it to the red-black tree pubfninsert(&mutself, key: K, value: V) { // Creates a new node with the given key, value, and color 'Red' letmut new_node = Box::new(Node { key, value, color: Color::Red, left: None, right: None, });
// Checks if the root node exists ifletSome(refmut root) = self.root { letmut current = root.as_mut(); // Traverses through the tree until it finds a suitable place to insert the new node loop { if new_node.key < current.key { ifletSome(refmut left) = current.left { current = left.as_mut(); } else { current.left = Some(new_node); break; } } elseif new_node.key > current.key { ifletSome(refmut right) = current.right { current = right.as_mut(); } else { current.right = Some(new_node); break; } } else { // If the key already exists in the tree, updates its corresponding value and exits the loop current.value = new_node.value; return; } } // Fixes the tree after insertion of the new node RBTree::fix_after_insertion(current, Some(&mutself.root)); } else { // If the root node does not exist, sets the color of the new node as 'Black' and makes it the root node new_node.color = Color::Black; self.root = Some(new_node); } } }
// This function fixes the Red-Black Tree violations that may arise after a node deletion fnfix_after_deletion( mut node: &mut Node<K, V>, root: Option<&mutBox<Node<K, V>>>, ) { while node != root.unwrap() && node.color == Color::Black {
// Get the parent and sibling of the current node letparent = node.parent_mut().unwrap(); letsibling = node.sibling().unwrap();
if sibling.color == Color::Red { // Case 1: The sibling of the current node is red // Change the colors of the parent, sibling, and the child of the sibling sibling.color = Color::Black; parent.color = Color::Red; if node.is_left_child() { // Rotate left if the current node is the left child RBTree::rotate_left(parent); sibling.color = parent.right.as_ref().unwrap().color; parent.right.as_mut().unwrap().color = Color::Black; node = parent.left.as_mut().unwrap(); } else { // Rotate right if the current node is the right child RBTree::rotate_right(parent); sibling.color = parent.left.as_ref().unwrap().color; parent.left.as_mut().unwrap().color = Color::Black; node = parent.right.as_mut().unwrap(); } } else { iflet (Some(left), Some(right)) = (sibling.left.as_ref(), sibling.right.as_ref()) { if left.color == Color::Black && right.color == Color::Black { // Case 2: The sibling of the current node is black and both its children are black // Change the colors of the sibling and move up to the parent sibling.color = Color::Red; node = parent; } else { if node.is_left_child() && right.color == Color::Black { // Case 3: The sibling of the current node is black and the right child is black // Change the colors of the sibling and its left child, and rotate right sibling.color = Color::Red; left.color = Color::Black; RBTree::rotate_right(sibling); sibling = parent.right.as_mut().unwrap(); } elseif node.is_right_child() && left.color == Color::Black { // Case 3: The sibling of the current node is black and the left child is black // Change the colors of the sibling and its right child, and rotate left sibling.color = Color::Red; right.color = Color::Black; RBTree::rotate_left(sibling); sibling = parent.left.as_mut().unwrap(); }
// Case 4: The sibling of the current node is black and has a red child // Change the colors of the parent, sibling, and the child of the sibling sibling.color = parent.color; parent.color = Color::Black; if node.is_left_child() { right.color = Color::Black; RBTree::rotate_left(parent); } else { left.color = Color::Black; RBTree::rotate_right(parent); } break; } } else { // Case 2: The sibling of the current node is black and has no children ifletSome(left) = sibling.left.as_ref() { if node.is_left_child() { // Change the color of the sibling's left child and rotate right left.color = Color::Black; sibling.color = parent.color; RBTree::rotate_right(parent); } else { // Change the color of the sibling and its left child, and rotate right left.color = Color::Red; RBTree::rotate_right(sibling); sibling = parent.right.as_mut().unwrap(); } } else { if node.is_left_child() { // Change the color of the sibling and its left child, and rotate right sibling.color = Color::Red; RBTree::rotate_right(sibling); sibling = parent.right.as_mut().unwrap(); } else { // Change the colors of the parent and sibling, and rotate left sibling.color = parent.color; parent.color = Color::Black; RBTree::rotate_left(parent); break; } } } } }
// Set the color of the current node to black node.color = Color::Black; } // This function deletes a node from the Red-Black Tree according to the given key pubfndelete(&mutself, key: &K) ->Option<V> { letmut current = self.root.as_mut();
whileletSome(node) = current { if key < &node.key { current = node.left.as_mut(); } elseif key > &node.key { current = node.right.as_mut(); } else { if node.left.is_some() && node.right.is_some() { // If the node has two children, replace it with its successor and delete the successor letsuccessor = node.right.as_mut().unwrap().min_node(); node.key = successor.key; node.value = std::mem::replace(&mut successor.value, Default::default()); current = Some(&mut *successor); } else { // If the node has one child or no children, remove it and fix any Red-Black Tree violations letchild = if node.left.is_some() { node.left.take() } else { node.right.take() };
if node.color == Color::Black { ifletSome(ref c) = child { RBTree::fix_after_deletion(c.as_mut(), Some(&mutself.root)); } else { RBTree::fix_after_deletion(node, Some(&mutself.root)); } }
impl<K: Ord, V> RBTree<K, V> { pubfnsearch(&self, key: &K) ->Option<&V> { letmut current = self.root.as_ref(); // Start search from the root of the tree. whileletSome(node) = current { // Traverse the tree until the key is found or a leaf node is reached. if key == &node.key { // If the key is found, return the corresponding value. returnSome(&node.value); } elseif key < &node.key { // If the key is less than the current node's key, search the left subtree. current = node.left.as_ref(); } else { // If the key is greater than the current node's key, search the right subtree. current = node.right.as_ref(); } }
In computer science, Red-Black Trees are a type of self-balancing binary search tree that are used to store and retrieve elements in sorted order with O(log n) time complexity for all major operations. They are designed to be memory-efficient and balanced, making them more efficient than other balanced trees like AVL trees. In this article, we have discussed the implementation of Red-Black Trees in Rust, a modern programming language designed for performance and safety. We have covered the structure of the tree, as well as the functions for insertion, deletion, and searching. Additionally, we have covered the fix functions that are used to restore the height balance and color balance properties of the tree after each insertion and deletion. Finally, we have discussed the left and right rotation functions that are used to maintain the balance properties of the Red-Black Tree. By using Rust to implement Red-Black Trees, we can take advantage of the language’s performance and safety features to create an efficient and reliable data structure.
What is Red Black Tree (RBT)?
Red-Black Trees are binary search trees where each node is colored either red or black. The color of the node is used to balance the tree so that the longest path from the root to any leaf node is no more than twice as long as the shortest path from the root to any other leaf node. This property is known as the height balance property.
Red-Black Trees are constructed with the following rules
Each node is either red or black.
The root node is always black.
Every leaf (NIL) node is black.
If a node is red, then both its children must be black.
Every path from a given node to any of its descendant NIL nodes must contain the same number of black nodes.
By assigning each node with a color and by limiting the number of consecutive colored nodes, RBT ensures that the longest branches will never exceed twice the size of the shortest branches, thus providing a more stable and effective tree. For reference, here’s a visual representation of an RBT:
Here’s a comparison between BST and RBT when we insert “1, 2, 3, 4, 5” in order, demonstrating why RBT is far more efficient than BST when sorted elements are inserted:
Obviously, BST will become extremely low effective when receiving a sorted sequence. And RBT can become more balanced under this situation.
Red-Black Tree Functions
A Red-Black Tree supports the following functions:
Insertion: To insert a new node into the Red-Black Tree, we first create a new node with the given key and value. We then traverse the tree to find the correct location to insert the new node. If the tree is empty, we simply make the new node the root of the tree. If the tree is not empty, we compare the new node’s key to the key of the current node we are examining. If the new node’s key is less than the current node’s key, we move to the left child of the current node. If the new node’s key is greater than the current node’s key, we move to the right child of the current node. We repeat this process until we find an empty location in the tree where we can insert the new node.
Deletion: To delete a node from the Red-Black Tree, we first search for the node with the given key. If the node is not found, we simply return without doing anything. If the node is found, we replace it with its successor, which is the node with the smallest key in the node’s right subtree. We then delete the successor node from the tree using a similar process.
Searching: Searching for a node in the Red-Black Tree is similar to searching in a binary search tree. We start at the root node and compare the given key with the key of the current node. If the keys are equal, we return the value of the current node. If the given key is less than the key of the current node, we move to the left child. If the given key is greater than the key of the current node, we move to the right child. We repeat this process until we find the node with the given key or reach a leaf node.
Rust Code for Red-Black Trees
To implement Red-Black Trees in Rust, we first define a Node struct to represent each node in the tree. The Node struct contains fields for the node’s key, value, color, and left and right children.
1 2 3 4 5 6 7 8 9 10 11
enumColor { // Defines an enum called 'Color' Red, // Enum variant representing the color red Black, // Enum variant representing the color black } structNode<K, V> { // Defines a struct called 'Node' with generic parameters 'K' and 'V' key: K, // Field representing the key of the node value: V, // Field representing the value of the node color: Color, // Field representing the color of the node, which is of type 'Color' enum left: Option<Box<Node<K, V>>>, // Field representing the left child node of the current node (if exists); it is an Option type and wrapped inside a box right: Option<Box<Node<K, V>>>, // Field representing the right child node of the current node (if exists); it is an Option type and wrapped inside a box }
We also define an RBTree struct to represent the Red-Black Tree as a whole. The RBTree struct contains a root node and methods to insert, delete, and search for elements in the tree.
1 2 3
pubstructRBTree<K: Ord, V> { // Defines a struct called 'RBTree' with generic parameters 'K' and 'V'; 'K' must implement 'Ord' trait root: Option<Box<Node<K, V>>>, // Field representing the root node of the red-black tree; it is an Option type and wrapped inside a box }
Left and Right Rotate
These functions perform a left or right rotation of a given node and its children. The rotate_left function takes in a mutable reference to a node and rotates its right child to the left, while the rotate_right function takes in a mutable reference to a node and rotates its left child to the right.
During each rotation, the appropriate pointers are updated to reflect the new structure of the tree. The size of each node is also updated to reflect any changes that occurred during the rotation.
These rotation functions are used by the fix_after_insertion and fix_after_deletion methods to maintain the balance properties of the Red-Black Tree.
// Defines a private method called 'rotate_left' that takes a mutable reference to a 'Node' struct fnrotate_left(mut node: &mut Node<K, V>) { // Takes ownership of the right child node of the given node letmut right = node.right.take().unwrap(); // Moves the left child of the right child node to the right child of the given node node.right = right.left.take(); // Sets the parent of the right child node as the given node and returns the right child node right.left = Some(std::mem::replace(&mut node, right)); // Sets the parent of the left child node of the given node to the given node ifletSome(refmut left) = node.left { left.parent = Some(node); } // Sets the parent of the right child node of the given node to the given node ifletSome(refmut right) = node.right { right.parent = Some(node); } // Updates the size of the given node node.update_size(); }
// Defines a private method called 'rotate_right' that takes a mutable reference to a 'Node' struct fnrotate_right(mut node: &mut Node<K, V>) { // Takes ownership of the left child node of the given node letmut left = node.left.take().unwrap(); // Moves the right child of the left child node to the left child of the given node node.left = left.right.take(); // Sets the parent of the left child node as the given node and returns the left child node left.right = Some(std::mem::replace(&mut node, left)); // Sets the parent of the left child node of the given node to the given node ifletSome(refmut left) = node.left { left.parent = Some(node); } // Sets the parent of the right child node of the given node to the given node ifletSome(refmut right) = node.right { right.parent = Some(node); } // Updates the size of the given node node.update_size(); } }
Insertion Function in Rust
The insert function in Rust follows the same logic as the insertion function described earlier. We create a new node with the given key and value and traverse the tree to find the correct location to insert the new node. If the tree is empty, we simply make the new node the root of the tree. If the tree is not empty, we compare the new node’s key to the key of the current node we are examining. If the new node’s key is less than the current node’s key, we move to the left child of the current node. If the new node’s key is greater than the current node’s key, we move to the right child of the current node. We repeat this process until we find an empty location in the tree where we can insert the new node.
// Defines a private method called 'fix_after_insertion' that takes a mutable reference to a 'Node' struct and an optional mutable reference to the root node fnfix_after_insertion( mut node: &mut Node<K, V>, root: Option<&mutBox<Node<K, V>>>, ) { // Sets the color of the inserted node as 'Red' node.color = Color::Red; // Checks if the node is not the root node and its parent's color is 'Red' while node != root.unwrap() && node.parent().unwrap().color == Color::Red { letparent = node.parent().unwrap(); letgrandparent = node.grandparent().unwrap(); // Checks if the parent is the left child of its grandparent if parent == grandparent.left.as_ref().unwrap() { letuncle = grandparent.right.as_ref(); // Checks if the uncle node exists and its color is 'Red' if uncle.is_some() && uncle.unwrap().color == Color::Red { // Recolors the parent, uncle, and grandparent nodes, and sets the current node to its grandparent parent.color = Color::Black; uncle.unwrap().color = Color::Black; grandparent.color = Color::Red; node = grandparent; } else { // Checks if the current node is the right child of its parent; if so, rotates it to the left around the parent node if node == parent.right.as_ref().unwrap() { node = parent; RBTree::rotate_left(parent); } // Recolors the parent and grandparent nodes, and rotates the grandparent node to the right parent.color = Color::Black; grandparent.color = Color::Red; RBTree::rotate_right(grandparent); } } else { letuncle = grandparent.left.as_ref(); // Checks if the uncle node exists and its color is 'Red' if uncle.is_some() && uncle.unwrap().color == Color::Red { // Recolors the parent, uncle, and grandparent nodes, and sets the current node to its grandparent parent.color = Color::Black; uncle.unwrap().color = Color::Black; grandparent.color = Color::Red; node = grandparent; } else { // Checks if the current node is the left child of its parent; if so, rotates it to the right around the parent node if node == parent.left.as_ref().unwrap() { node = parent; RBTree::rotate_right(parent); } // Recolors the parent and grandparent nodes, and rotates the grandparent node to the left parent.color = Color::Black; grandparent.color = Color::Red; RBTree::rotate_left(grandparent); } } } root.unwrap().color = Color::Black; }
// Defines a public method called 'insert' that takes a key and a value and adds it to the red-black tree pubfninsert(&mutself, key: K, value: V) { // Creates a new node with the given key, value, and color 'Red' letmut new_node = Box::new(Node { key, value, color: Color::Red, left: None, right: None, });
// Checks if the root node exists ifletSome(refmut root) = self.root { letmut current = root.as_mut(); // Traverses through the tree until it finds a suitable place to insert the new node loop { if new_node.key < current.key { ifletSome(refmut left) = current.left { current = left.as_mut(); } else { current.left = Some(new_node); break; } } elseif new_node.key > current.key { ifletSome(refmut right) = current.right { current = right.as_mut(); } else { current.right = Some(new_node); break; } } else { // If the key already exists in the tree, updates its corresponding value and exits the loop current.value = new_node.value; return; } } // Fixes the tree after insertion of the new node RBTree::fix_after_insertion(current, Some(&mutself.root)); } else { // If the root node does not exist, sets the color of the new node as 'Black' and makes it the root node new_node.color = Color::Black; self.root = Some(new_node); } } }
Deletion Function in Rust
The delete function in Rust also follows the same logic as the deletion function described earlier. We search for the node with the given key and replace it with its successor, which is the node with the smallest key in the node’s right subtree. We then delete the successor node from the tree using a similar process.
// This function fixes the Red-Black Tree violations that may arise after a node deletion fnfix_after_deletion( mut node: &mut Node<K, V>, root: Option<&mutBox<Node<K, V>>>, ) { while node != root.unwrap() && node.color == Color::Black {
// Get the parent and sibling of the current node letparent = node.parent_mut().unwrap(); letsibling = node.sibling().unwrap();
if sibling.color == Color::Red { // Case 1: The sibling of the current node is red // Change the colors of the parent, sibling, and the child of the sibling sibling.color = Color::Black; parent.color = Color::Red; if node.is_left_child() { // Rotate left if the current node is the left child RBTree::rotate_left(parent); sibling.color = parent.right.as_ref().unwrap().color; parent.right.as_mut().unwrap().color = Color::Black; node = parent.left.as_mut().unwrap(); } else { // Rotate right if the current node is the right child RBTree::rotate_right(parent); sibling.color = parent.left.as_ref().unwrap().color; parent.left.as_mut().unwrap().color = Color::Black; node = parent.right.as_mut().unwrap(); } } else { iflet (Some(left), Some(right)) = (sibling.left.as_ref(), sibling.right.as_ref()) { if left.color == Color::Black && right.color == Color::Black { // Case 2: The sibling of the current node is black and both its children are black // Change the colors of the sibling and move up to the parent sibling.color = Color::Red; node = parent; } else { if node.is_left_child() && right.color == Color::Black { // Case 3: The sibling of the current node is black and the right child is black // Change the colors of the sibling and its left child, and rotate right sibling.color = Color::Red; left.color = Color::Black; RBTree::rotate_right(sibling); sibling = parent.right.as_mut().unwrap(); } elseif node.is_right_child() && left.color == Color::Black { // Case 3: The sibling of the current node is black and the left child is black // Change the colors of the sibling and its right child, and rotate left sibling.color = Color::Red; right.color = Color::Black; RBTree::rotate_left(sibling); sibling = parent.left.as_mut().unwrap(); }
// Case 4: The sibling of the current node is black and has a red child // Change the colors of the parent, sibling, and the child of the sibling sibling.color = parent.color; parent.color = Color::Black; if node.is_left_child() { right.color = Color::Black; RBTree::rotate_left(parent); } else { left.color = Color::Black; RBTree::rotate_right(parent); } break; } } else { // Case 2: The sibling of the current node is black and has no children ifletSome(left) = sibling.left.as_ref() { if node.is_left_child() { // Change the color of the sibling's left child and rotate right left.color = Color::Black; sibling.color = parent.color; RBTree::rotate_right(parent); } else { // Change the color of the sibling and its left child, and rotate right left.color = Color::Red; RBTree::rotate_right(sibling); sibling = parent.right.as_mut().unwrap(); } } else { if node.is_left_child() { // Change the color of the sibling and its left child, and rotate right sibling.color = Color::Red; RBTree::rotate_right(sibling); sibling = parent.right.as_mut().unwrap(); } else { // Change the colors of the parent and sibling, and rotate left sibling.color = parent.color; parent.color = Color::Black; RBTree::rotate_left(parent); break; } } } } }
// Set the color of the current node to black node.color = Color::Black; } // This function deletes a node from the Red-Black Tree according to the given key pubfndelete(&mutself, key: &K) ->Option<V> { letmut current = self.root.as_mut();
whileletSome(node) = current { if key < &node.key { current = node.left.as_mut(); } elseif key > &node.key { current = node.right.as_mut(); } else { if node.left.is_some() && node.right.is_some() { // If the node has two children, replace it with its successor and delete the successor letsuccessor = node.right.as_mut().unwrap().min_node(); node.key = successor.key; node.value = std::mem::replace(&mut successor.value, Default::default()); current = Some(&mut *successor); } else { // If the node has one child or no children, remove it and fix any Red-Black Tree violations letchild = if node.left.is_some() { node.left.take() } else { node.right.take() };
if node.color == Color::Black { ifletSome(ref c) = child { RBTree::fix_after_deletion(c.as_mut(), Some(&mutself.root)); } else { RBTree::fix_after_deletion(node, Some(&mutself.root)); } }
returnSome(node.value); } } }
None }
Searching Function in Rust
The search function in Rust is also similar to the search function described earlier. We start at the root node and compare the given key with the key of the current node. If the keys are equal, we return the value of the current node. If the given key is less than the key of the current node, we move to the left child. If the given key is greater than the key of the current node, we move to the right child. We repeat this process until we find the node with the given key or reach a leaf node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
impl<K: Ord, V> RBTree<K, V> { pubfnsearch(&self, key: &K) ->Option<&V> { letmut current = self.root.as_ref(); // Start search from the root of the tree. whileletSome(node) = current { // Traverse the tree until the key is found or a leaf node is reached. if key == &node.key { // If the key is found, return the corresponding value. returnSome(&node.value); } elseif key < &node.key { // If the key is less than the current node's key, search the left subtree. current = node.left.as_ref(); } else { // If the key is greater than the current node's key, search the right subtree. current = node.right.as_ref(); } }
None// If the key is not found, return None. } }
Conclusion
Red-Black Trees are a type of self-balancing binary search tree that are used to store and retrieve elements in sorted order with O(log n) time complexity for all major operations. They are designed to be memory efficient and balanced, making them more efficient than other balanced trees like AVL trees. Rust is a modern programming language that is designed for performance and safety, making it a great choice for implementing data structures like the Red-Black Tree.