Red Black Tree

Posted on Edited on In Views:

中文版链接

Abstract

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

  1. Each node is either red or black.
  2. The root node is always black.
  3. Every leaf (NIL) node is black.
  4. If a node is red, then both its children must be black.
  5. 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:

photo_2023-02-22_21-58-43.jpg

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:

photo_2023-02-22_22-32-17.jpg

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:

  1. 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.

  2. 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.

  3. 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
enum Color {   // Defines an enum called 'Color'
    Red,      // Enum variant representing the color red
    Black,    // Enum variant representing the color black
}
struct Node<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
pub struct RBTree<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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
impl<K: Ord, V> RBTree<K, V> {

    // Defines a private method called 'rotate_left' that takes a mutable reference to a 'Node' struct
    fn rotate_left(mut node: &mut Node<K, V>) {
        // Takes ownership of the right child node of the given node
        let mut 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
        if let Some(ref mut left) = node.left {
            left.parent = Some(node);
        }
        
        // Sets the parent of the right child node of the given node to the given node
        if let Some(ref mut 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
    fn rotate_right(mut node: &mut Node<K, V>) {
        // Takes ownership of the left child node of the given node
        let mut 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
        if let Some(ref mut left) = node.left {
            left.parent = Some(node);
        }
        
        // Sets the parent of the right child node of the given node to the given node
        if let Some(ref mut 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
impl<K: Ord, V> RBTree<K, V> {

    // 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
    fn fix_after_insertion(
        mut node: &mut Node<K, V>,
        root: Option<&mut Box<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 {
            let parent = node.parent().unwrap();
            let grandparent = node.grandparent().unwrap();
            
            // Checks if the parent is the left child of its grandparent
            if parent == grandparent.left.as_ref().unwrap() {
                let uncle = 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 {
                let uncle = 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
    pub fn insert(&mut self, key: K, value: V) {
        // Creates a new node with the given key, value, and color 'Red'
        let mut new_node = Box::new(Node {
            key,
            value,
            color: Color::Red,
            left: None,
            right: None,
        });

        // Checks if the root node exists
        if let Some(ref mut root) = self.root {
            let mut 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 {
                    if let Some(ref mut left) = current.left {
                        current = left.as_mut();
                    } else {
                        current.left = Some(new_node);
                        break;
                    }
                } else if new_node.key > current.key {
                    if let Some(ref mut 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(&mut self.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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
// This function fixes the Red-Black Tree violations that may arise after a node deletion
fn fix_after_deletion(
    mut node: &mut Node<K, V>,
    root: Option<&mut Box<Node<K, V>>>,
) {
    while node != root.unwrap() && node.color == Color::Black {

        // Get the parent and sibling of the current node
        let parent = node.parent_mut().unwrap();
        let sibling = 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 {
            if let (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();
                    } else if 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
                if let Some(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
pub fn delete(&mut self, key: &K) -> Option<V> {
    let mut current = self.root.as_mut();

    while let Some(node) = current {
        if key < &node.key {
            current = node.left.as_mut();
        } else if 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
                let successor = 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
                let child = if node.left.is_some() {
                    node.left.take()
                } else {
                    node.right.take()
                };

                if node.color == Color::Black {
                    if let Some(ref c) = child {
                        RBTree::fix_after_deletion(c.as_mut(), Some(&mut self.root));
                    } else {
                        RBTree::fix_after_deletion(node, Some(&mut self.root));
                    }
                }

                return Some(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> {
    pub fn search(&self, key: &K) -> Option<&V> {
        let mut current = self.root.as_ref(); // Start search from the root of the tree.
        
        while let Some(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.
                return Some(&node.value);
            } else if 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.