Red-Black-Tree(zh-CN)

English Version

摘要

红黑树是一种自平衡的二叉搜索树，用于按排序顺序存储和检索元素，并具有O（log n）时间复杂度的所有主要操作。它们被设计为内存高效和平衡，使它们比其他平衡树如AVL树更高效。在本文中，我们讨论了在Rust中实现红黑树，这是一种为性能和安全性而设计的现代编程语言。我们讨论了树的结构，以及插入，删除和搜索的函数。此外，我们还讨论了修复函数，用于在每次插入和删除后恢复树的高度平衡和颜色平衡属性。最后，我们讨论了左旋和右旋函数，用于维护红黑树的平衡属性。通过使用Rust来实现红黑树，我们可以利用该语言的性能和安全性功能来创建高效且可靠的数据结构。

什么是红黑树（RBT）？

红黑树是一种二叉搜索树，其中每个节点都被着色为红色或黑色。节点的颜色用于平衡树，以使从根节点到任何叶子节点的最长路径不超过从根节点到任何其他叶子节点的最短路径的两倍。此属性称为高度平衡属性。

红黑树是按照以下规则构建的

1. 每个节点都是红色或黑色。
2. 根节点始终为黑色。
3. 每个叶子（NIL）节点都是黑色的。
4. 如果一个节点为红色，则它的两个子节点必须为黑色。
5. 从给定节点到其任何后代NIL节点的每条路径必须包含相同数量的黑色节点。

通过为每个节点分配颜色并限制连续的着色节点数量，RBT确保最长的分支永远不会超过最短分支的两倍大小，从而提供更稳定和有效的树。

以下是RBT的视觉表示：

当我们按顺序插入“1, 2, 3, 4, 5”时，以下是BST和RBT之间的比较，展示了为什么在插入排序元素时RBT远比BST有效：

很明显，当收到排序序列时，BST将变得非常低效。而RBT在此情况下可以更加平衡。

红黑树函数

红黑树支持以下函数：

1. 插入：要将新节点插入红黑树中，我们首先创建一个具有给定键和值的新节点。然后，我们遍历树以找到插入新节点的正确位置。如果树为空，我们将新节点简单地作为树的根。如果树不为空，我们将新节点的键与当前正在检查的节点的键进行比较。如果新节点的键小于当前节点的键，则移动到当前节点的左子节点。如果新节点的键大于当前节点的键，则移动到当前节点的右子节点。我们重复这个过程，直到我们找到一个可以插入新节点的空位置。

2. 删除：要从红黑树中删除节点，我们首先搜索具有给定键的节点。如果找不到节点，我们简单地返回而不做任何事情。如果找到节点，我们用其后继节点替换它，后继节点是节点右子树中键值最小的节点。然后，我们使用类似的过程从树中删除后继节点。

3. 搜索：在红黑树中搜索节点类似于在二叉搜索树中搜索。我们从根节点开始，将给定键与当前节点的键进行比较。如果键相等，我们返回当前节点的值。如果给定键小于当前节点的键，我们移动到左子节点。如果给定键大于当前节点的键，则移动到右子节点。我们重复这个过程，直到我们找到具有给定键的节点或到达叶子节点。

Rust中的红黑树代码

要在Rust中实现红黑树，我们首先定义一个Node结构来表示树中的每个节点。Node结构包含节点的键，值，颜色和左右子节点字段。

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
}

我们还定义了一个RBTree结构来表示整个红黑树。RBTree结构包含一个根节点和用于插入，删除和搜索树中元素的方法。

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
}

左旋和右旋

这些函数执行给定节点及其子节点的左旋或右旋操作。rotate_left函数接收一个可变引用到一个节点，并将其右子节点向左旋转，而rotate_right函数接收一个可变引用到一个节点，并将其左子节点向右旋转。

在每次旋转期间，适当的指针被更新以反映树的新结构。每个节点的大小也被更新以反映旋转过程中发生的任何更改。

这些旋转函数由fix_after_insertion和fix_after_deletion方法用于维护红黑树的平衡属性。

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();
    }
}

插入函数

插入函数遵循之前描述的插入函数相同的逻辑。我们创建一个具有给定键和值的新节点，并遍历树以找到插入新节点的正确位置。如果树为空，我们将新节点简单地作为树的根。如果树不为空，我们将新节点的键与当前正在检查的节点的键进行比较。如果新节点的键小于当前节点的键，则移动到当前节点的左子节点。如果新节点的键大于当前节点的键，则移动到当前节点的右子节点。我们重复这个过程，直到我们找到一个可以插入新节点的空位置。

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);
        }
    }
}   

删除函数

删除函数也遵循之前描述的删除函数相同的逻辑。我们搜索具有给定键的节点，并用其后继节点替换它，后继节点是节点右子树中键值最小的节点。然后，我们使用类似的过程从树中删除后继节点。

// 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
} 

搜索函数

搜索函数与之前描述的搜索函数类似。我们从根节点开始，将给定键与当前节点的键进行比较。如果键相等，我们返回当前节点的值。如果给定键小于当前节点的键，我们移动到左子节点。如果给定键大于当前节点的键，则移动到右子节点。我们重复这个过程，直到我们找到具有给定键的节点或到达叶子节点。

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

结论

红黑树是一种自平衡的二叉搜索树，用于按排序顺序存储和检索元素，所有主要操作的时间复杂度为O(log n)。它们旨在具有内存效率和平衡性，使其比其他平衡树如AVL树更有效率。Rust是一种现代编程语言，旨在提高性能和安全性，因此它是实现数据结构如红黑树的绝佳选择。