红黑树原理及实现

什么是红黑树

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在1972年由鲁道夫·贝尔发明。红黑树通过在节点上增加一个颜色属性（红色或黑色）来维护树的平衡性，确保最坏情况下的查找、插入和删除操作的时间复杂度都为 O(log n)。

红黑树在计算机科学中有着广泛的应用，比如：

• C++ STL 中的 std::map、std::set
• Java 中的 TreeMap、TreeSet
• Linux 内核的进程调度器
• 数据库索引结构

红黑树的特性

一棵有效的红黑树必须满足以下五个特性：

1. 颜色特性：每个节点要么是红色，要么是黑色
2. 根节点特性：根节点必须是黑色
3. 叶子节点特性：所有叶子节点（NIL节点）都是黑色
4. 红色节点特性：如果一个节点是红色，那么它的两个子节点都必须是黑色（即红色节点不能连续）
5. 路径特性：从任意节点到其每个叶子节点的所有路径上，黑色节点的数量相同

这些特性确保了红黑树的关键性质：从根节点到最远叶子节点的路径长度不会超过从根节点到最近叶子节点路径长度的2倍。

红黑树的旋转操作

为了维持红黑树的特性，在插入和删除操作中需要进行旋转和颜色调整。旋转操作有两种：

左旋转（Left Rotate）

左旋转用于将某个节点的右子树提升为父节点，原节点成为新父节点的左子树。

def left_rotate(tree, x):
    """左旋转操作"""
    # 设置 y 为 x 的右子节点
    y = x.right
    
    # 将 y 的左子树设置为 x 的右子树
    x.right = y.left
    if y.left != tree.nil:
        y.left.parent = x
    
    # 更新 y 的父节点
    y.parent = x.parent
    if x.parent == tree.nil:
        tree.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    
    # 将 x 设置为 y 的左子节点
    y.left = x
    x.parent = y

右旋转（Right Rotate）

右旋转是左旋转的镜像操作，用于将某个节点的左子树提升为父节点。

def right_rotate(tree, x):
    """右旋转操作"""
    # 设置 y 为 x 的左子节点
    y = x.left
    
    # 将 y 的右子树设置为 x 的左子树
    x.left = y.right
    if y.right != tree.nil:
        y.right.parent = x
    
    # 更新 y 的父节点
    y.parent = x.parent
    if x.parent == tree.nil:
        tree.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    
    # 将 x 设置为 y 的右子节点
    y.right = x
    x.parent = y

红黑树的插入操作

插入操作分为两个阶段：

1. 标准的BST插入：按照二叉搜索树的规则插入新节点，并初始化为红色
2. 修复红黑树特性：通过旋转和重新着色来修复可能违反的特性

插入后的修复主要关注以下情况：

• 如果新插入节点的父节点是黑色，不需要修复
• 如果父节点是红色，违反了红色节点特性，需要修复

修复时需要处理三种主要情况：

def rb_insert_fixup(tree, z):
    """插入后修复红黑树特性"""
    while z.parent.color == 'RED':
        # 情况1：父节点是祖父节点的左子节点
        if z.parent == z.parent.parent.left:
            y = z.parent.parent.right  # 叔父节点
            if y.color == 'RED':  # 情况1.1：叔父节点是红色
                z.parent.color = 'BLACK'
                y.color = 'BLACK'
                z.parent.parent.color = 'RED'
                z = z.parent.parent
            else:
                if z == z.parent.right:  # 情况1.2：z是右子节点
                    z = z.parent
                    left_rotate(tree, z)
                # 情况1.3：z是左子节点
                z.parent.color = 'BLACK'
                z.parent.parent.color = 'RED'
                right_rotate(tree, z.parent.parent)
        else:  # 情况2：父节点是祖父节点的右子节点（对称处理）
            y = z.parent.parent.left
            if y.color == 'RED':
                z.parent.color = 'BLACK'
                y.color = 'BLACK'
                z.parent.parent.color = 'RED'
                z = z.parent.parent
            else:
                if z == z.parent.left:
                    z = z.parent
                    right_rotate(tree, z)
                z.parent.color = 'BLACK'
                z.parent.parent.color = 'RED'
                left_rotate(tree, z.parent.parent)
    
    tree.root.color = 'BLACK'

完整的红黑树实现

下面是一个完整的红黑树Python实现：

class RBNode:
    """红黑树节点"""
    def __init__(self, key, color='RED', left=None, right=None, parent=None):
        self.key = key
        self.color = color  # 'RED' 或 'BLACK'
        self.left = left
        self.right = right
        self.parent = parent

class RedBlackTree:
    """红黑树"""
    def __init__(self):
        # NIL节点：所有叶子节点都指向这个黑色哨兵节点
        self.nil = RBNode(None, 'BLACK')
        self.root = self.nil
    
    def insert(self, key):
        """插入节点"""
        z = RBNode(key)
        z.left = self.nil
        z.right = self.nil
        z.color = 'RED'
        
        y = self.nil
        x = self.root
        
        # 标准的BST插入过程
        while x != self.nil:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        
        z.parent = y
        if y == self.nil:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
        
        # 修复红黑树特性
        self._insert_fixup(z)
    
    def _insert_fixup(self, z):
        """插入后修复"""
        while z.parent.color == 'RED':
            if z.parent == z.parent.parent.left:
                y = z.parent.parent.right
                if y.color == 'RED':
                    z.parent.color = 'BLACK'
                    y.color = 'BLACK'
                    z.parent.parent.color = 'RED'
                    z = z.parent.parent
                else:
                    if z == z.parent.right:
                        z = z.parent
                        self._left_rotate(z)
                    z.parent.color = 'BLACK'
                    z.parent.parent.color = 'RED'
                    self._right_rotate(z.parent.parent)
            else:
                y = z.parent.parent.left
                if y.color == 'RED':
                    z.parent.color = 'BLACK'
                    y.color = 'BLACK'
                    z.parent.parent.color = 'RED'
                    z = z.parent.parent
                else:
                    if z == z.parent.left:
                        z = z.parent
                        self._right_rotate(z)
                    z.parent.color = 'BLACK'
                    z.parent.parent.color = 'RED'
                    self._left_rotate(z.parent.parent)
        
        self.root.color = 'BLACK'
    
    def _left_rotate(self, x):
        """左旋转"""
        y = x.right
        x.right = y.left
        if y.left != self.nil:
            y.left.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y
    
    def _right_rotate(self, x):
        """右旋转"""
        y = x.left
        x.left = y.right
        if y.right != self.nil:
            y.right.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.right = x
        x.parent = y
    
    def search(self, key):
        """搜索节点"""
        x = self.root
        while x != self.nil and key != x.key:
            if key < x.key:
                x = x.left
            else:
                x = x.right
        return x
    
    def inorder_traverse(self, node=None, result=None):
        """中序遍历"""
        if result is None:
            result = []
        if node is None:
            node = self.root
        
        if node != self.nil:
            self.inorder_traverse(node.left, result)
            result.append((node.key, node.color))
            self.inorder_traverse(node.right, result)
        
        return result


# 使用示例
if __name__ == '__main__':
    rb_tree = RedBlackTree()
    
    # 插入节点
    keys = [7, 3, 18, 10, 22, 8, 11, 26]
    for key in keys:
        rb_tree.insert(key)
    
    # 中序遍历
    print("中序遍历结果:", rb_tree.inorder_traverse())
    
    # 搜索节点
    node = rb_tree.search(10)
    if node != rb_tree.nil:
        print(f"找到节点: {node.key}, 颜色: {node.color}")

红黑树的删除操作

删除操作比插入更复杂，同样分为两个阶段：

1. 标准的BST删除：找到要删除的节点并用其子节点或后继节点替换
2. 修复红黑树特性：通过旋转和重新着色修复

删除后的修复需要考虑多种情况，主要关注被删除节点的替代节点的颜色。

时间复杂度分析

• 查找：O(log n) - 由于树的高度最多是2*log(n+1)
• 插入：O(log n) - 插入节点O(log n)，修复过程最多需要O(log n)次旋转
• 删除：O(log n) - 删除节点O(log n)，修复过程最多需要O(log n)次旋转

红黑树 vs AVL树

特性	红黑树	AVL树
平衡标准	较宽松（最长路径不超过最短路径2倍）	严格（左右子树高度差不超过1）
查找性能	O(log n)	O(log n)（稍好）
插入/删除性能	O(log n)（较好，旋转次数少）	O(log n)（旋转次数多）
适用场景	需要频繁插入删除的场景	查找为主，插入删除较少的场景

总结

红黑树是一种优秀的自平衡二叉搜索树，通过五个特性的约束和旋转操作，在保证查找效率的同时，也能高效地支持动态插入和删除操作。理解红黑树的原理和实现，对于深入理解数据结构和算法设计具有重要意义。

---

参考资料：

• 《算法导论》（Introduction to Algorithms）
• 《数据结构与算法分析》