第32课：红黑树

1. 学习目标

理解红黑树的核心性质：掌握红黑树节点着色规则及其对树平衡的影响。
掌握旋转操作：能够编写并理解左旋和右旋操作，这是调整树结构的基础。
掌握插入算法：重点理解插入新节点后的“修复”（Fix-Up）过程，包括颜色翻转和旋转的综合运用。
了解删除思路：了解红黑树删除操作的复杂性，明白为什么它通常比插入更复杂。
对比AVL树：理解红黑树与AVL树在平衡策略、实现复杂度和应用场景上的主要区别。

2. 核心概念

在上一课学习AVL树时，我们发现它通过严格的平衡因子（左右子树高度差不超过1）来保证查询效率，但这种“严格”也带来了插入/删除时频繁旋转的代价。红黑树则提供了一种更“宽松”的平衡方案，它不追求绝对平衡，而是通过颜色标记和旋转来维持一种近似平衡，从而在插入和删除操作上通常比AVL树更高效。

红黑树的五大性质（所有性质必须永久保持）：

每个节点非红即黑。
根节点是黑色。
每个叶节点（NIL节点，即空节点）是黑色。
如果一个节点是红色，则它的两个子节点都是黑色。（即，不能有两个连续的红色节点）。
对于任一节点，从该节点到其所有后代叶节点的路径上，均包含相同数目的黑色节点。（这个数称为“黑高”）。

性质4和5是核心。性质4防止了“红色路径”太长，性质5则保证了最长路径（红黑交替）不会超过最短路径（全黑）的两倍。因此，红黑树的高度最多是2log(N+1)，依然保证了O(log N)的操作效率。

旋转是局部调整树结构而不破坏二叉搜索树性质的操作。它是修复红黑树性质违规的主要工具。

左旋 (Left Rotate)：以一个节点为支点，将其“右孩子”提升为父节点，支点变为新父节点的左孩子，新父节点原来的左孩子变成支点的右孩子。
右旋 (Right Rotate)：与左旋镜像对称。

插入修复是本课的难点。当我们插入一个新节点（默认为红色）时，可能会破坏性质2（如果插入的是根）或性质4（新节点的父节点也是红色）。修复过程根据叔叔节点的颜色分为几种情况，可能涉及颜色翻转和一到两次旋转。

3. 代码示例

下面是一个简化的红黑树实现框架，重点演示插入和修复逻辑。为简化，我们将NIL节点表示为一个全局的黑色哨兵节点。

class RBNode:
    def __init__(self, key, color='RED'):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.NIL = RBNode(key=None, color='BLACK') # 哨兵节点，代表所有叶子
        self.root = self.NIL

    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 == None:
            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, y):
        x = y.left
        y.left = x.right
        if x.right != self.NIL:
            x.right.parent = y
        x.parent = y.parent
        if y.parent == None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        x.right = y
        y.parent = x

    def insert(self, key):
        # 1. 执行标准BST插入，新节点默认为RED
        new_node = RBNode(key)
        new_node.left = self.NIL
        new_node.right = self.NIL
        new_node.parent = None

        y = None
        x = self.root
        while x != self.NIL:
            y = x
            if new_node.key < x.key:
                x = x.left
            else:
                x = x.right
        new_node.parent = y
        if y == None:
            self.root = new_node
        elif new_node.key < y.key:
            y.left = new_node
        else:
            y.right = new_node

        # 2. 如果新节点是根，直接涂黑，否则需要修复
        if new_node.parent == None:
            new_node.color = 'BLACK'
            return

        # 3. 如果父节点是红色，才需要修复（破坏了性质4）
        if new_node.parent.parent == None: # 祖父节点不存在，说明父节点是根，但根应该是黑的，需要处理。
            # 这种情况在插入根节点的子节点时可能发生，修复会处理。
            pass
        self._fix_insert(new_node)

    def _fix_insert(self, z):
        # 循环修复，直到父节点为黑色（不破坏性质4）或到达根
        while z.parent != None and z.parent.color == 'RED':
            if z.parent == z.parent.parent.left:
                uncle = z.parent.parent.right
                # Case 1: 叔叔节点是红色
                if uncle.color == 'RED':
                    z.parent.color = 'BLACK'
                    uncle.color = 'BLACK'
                    z.parent.parent.color = 'RED'
                    z = z.parent.parent # 移动z到祖父节点继续检查
                else:
                    # Case 2: 叔叔是黑色，且z是右孩子（左右情况）
                    if z == z.parent.right:
                        z = z.parent
                        self.left_rotate(z)
                    # Case 3: 叔叔是黑色，且z是左孩子（左左情况）
                    z.parent.color = 'BLACK'
                    z.parent.parent.color = 'RED'
                    self.right_rotate(z.parent.parent)
            else: # 父节点是右孩子，镜像处理
                uncle = z.parent.parent.left
                if uncle.color == 'RED':
                    z.parent.color = 'BLACK'
                    uncle.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'

# 测试代码
rbt = RedBlackTree()
keys = [7, 3, 18, 10, 22, 8, 11, 26, 2, 6]
for key in keys:
    rbt.insert(key)
    print(f"插入 {key} 后根节点: {rbt.root.key}, 颜色: {rbt.root.color}")
print("插入完成。一个简单的红黑树构建完成。")

注意：为保持代码清晰和课件长度，此示例省略了删除操作和完整的打印/验证函数。真实生产环境中的实现（如Linux内核的rbtree）会复杂得多。

4. 实践练习

练习1：手动模拟插入 按照上述代码逻辑，手动模拟将节点序列 [5, 2, 8, 1, 4] 插入到一棵初始为空的红黑树中。画出每一步插入并修复后的树结构，并标注每个节点的颜色。重点关注插入4时引发的修复过程。

练习2：性质验证 在上面的测试代码基础上，编写一个函数 validate_rbt(node)，用于递归检查以node为根的子树是否满足红黑树的性质4和性质5。你可以先检查性质4（无连续红节点），然后通过计算从当前节点到其任意后代叶子的黑节点数是否一致来检查性质5。

练习3：思考题 - 删除的挑战 为什么红黑树的删除操作比插入复杂得多？从节点被删除后可能破坏哪些性质的角度思考。提示：如果删除的是一个黑色节点，可能会导致“黑高”不平衡，这就需要更复杂的旋转和重新着色来修复。

5. 常见错误

忽略哨兵节点（NIL）：忘记将叶子节点设为黑色的NIL节点，会导致性质检查和指针访问出错。
旋转后指针更新不完整：旋转操作中，忘记更新节点的parent指针，或者忘记处理子树转移时新旧父节点的连接关系。
插入修复逻辑不完整：只考虑了父节点是祖父节点左孩子的情况，没有实现其镜像情况（父节点是右孩子）。
混淆“叔叔”节点：在代码中错误地指定了叔叔节点（应该是父节点的兄弟节点）。
修复循环终止条件错误：导致死循环或过早退出修复。

6. 小结

红黑树通过五大性质（特别是无连续红节点和路径黑高相等）来维持近似平衡，保证了最坏情况下O(log N)的性能。
旋转（左旋、右旋）是调整树结构、恢复性质的基础操作。
插入新节点（默认为红） 后，主要可能破坏性质4（父子双红）。修复过程根据叔叔节点的颜色分为两种情况：叔叔为红则进行颜色上推；叔叔为黑则需要结合旋转。
与AVL树相比，红黑树在插入和删除频繁的场景下通常有优势，因为它牺牲了一点查询性能（树高度可能略高），但换来了更少的旋转次数。它是许多编程语言标准库（如C++ STL的map/set， Java的TreeMap）的底层实现。

练习编辑器

rust