红黑树：执法者

算法背后的故事：官僚的规则

想象一棵树，每个节点都被涂成 红色 或 黑色。 一位官僚递给你一本规则书：

1. 根规则： 国王（根节点）必须是黑色的。
2. 红色规则： 如果一个节点是红色的，它的孩子必须是黑色的（不能有两个连续的红色）。
3. 黑高规则： 从国王到最底层的每一条路径，必须经过完全相同数量的黑色节点。

这些规则看起来很随意。为什么是颜色？为什么要数黑色？ 但这些规则创造了一个数学保证：树中最长的路径，永远不会超过最短路径的两倍。 通过强迫树遵守这些法律，无论你输入什么数据，树都能保持大致的平衡 ($O(\log N)$)。

为什么需要它？

• Java 的 TreeMap / TreeSet： 内部使用红黑树。
• C++ STL std::map： 使用红黑树。
• Linux 内核： 使用红黑树进行进程调度（CFS 调度器）和内存管理。

算法是如何“思考”的

这个算法是一个修正者。 每当你插入一个节点，你把它涂成 红色。这可能会违反规则（例如，出现了两个连续的红色）。 算法随后使用两个工具来“修复”这棵树：

1. 重新着色 (Recoloring)： 将节点从红变黑（或反之）。
2. 旋转 (Rotation)： 物理扭转树的结构（左旋或右旋）来上下移动节点。

这就像玩魔方。你走了一步，打乱了它，然后执行一套固定的扭转序列来恢复秩序。

工程决策：AVL vs. 红黑树

• AVL 树： 严格检查平衡。每一次插入都会触发检查。它极其平衡，但写入速度慢。
  • 适用场景： 读多写少（字典）。
• 红黑树： 宽松检查平衡。它允许树稍微有点歪。这使得插入和删除快得多。
  • 适用场景： 通用负载（标准库）。

实现参考 (Python 概念版)

实现一个完整的红黑树需要 200 多行旋转逻辑。这里我们实现 左旋 (Left Rotate)，这是平衡的核心机制。

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

def left_rotate(tree, x):
    # 将节点 X 向左旋转
    y = x.right # 设定 y
    
    # 1. 将 y 的左子树变成 x 的右子树
    x.right = y.left
    if y.left:
        y.left.parent = x
    
    # 2. 将 y 链接到 x 的父亲
    y.parent = x.parent
    if not x.parent:
        tree.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    
    # 3. 将 x 放在 y 的左边
    y.left = x
    x.parent = y

# 注意：在真实实现中，你需要在每次插入后检查颜色
# 并在违反规则时调用 rotate()。

小结

红黑树教会我们：绝对的完美是昂贵的。与完美平衡的 AVL 树不同，红黑树接受“足够好”的平衡以换取速度。它提醒我们，在工程中，一个能稍微弯曲的刚性系统，往往比一个一折就断的完美系统更耐用。