手写红黑树（Red-Black Tree）的实现

红黑树是一种自平衡的二叉搜索树，它通过特定的规则确保树的高度保持在O(log n)，从而保证查找、插入和删除操作的最坏情况时间复杂度为O(log n)。红黑树在Java的TreeMap、C++的STL map等中广泛使用。

红黑树的五条性质：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点）是黑色。
4. 如果一个节点是红色，则它的两个子节点都是黑色（即不能有连续的红色节点）。
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（黑色高度相同）。

红黑树的基本结构：

class Node:
    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 = Node(None, 'BLACK')  # 叶子节点（NIL）
        self.root = self.NIL

插入操作步骤：

1. 按照二叉搜索树规则插入：

   • 从根节点开始，比较键值大小，找到插入位置。
   • 创建新节点（颜色为红色），将其插入为叶子节点，左右子节点指向NIL。

2. 调整颜色和结构以满足红黑树性质：

   • 若插入后违反性质4（连续红色节点），需通过旋转和变色调整。
   • 调整分为三种情况（假设新节点为N，父节点为P，祖父节点为G，叔节点为U）：

   情况1：叔节点U是红色

   • 操作：将P和U变为黑色，G变为红色，然后将G作为新节点N递归调整。
   • 理由：通过颜色翻转保持黑色高度不变，但可能使G与它的父节点形成连续红色，需向上递归。

   情况2：叔节点U是黑色，且N是P的右子节点（P是G的左子节点）

   • 操作：对P进行左旋，转换为情况3。
   • 理由：将树结构调整为线性链，便于后续旋转。

   情况3：叔节点U是黑色，且N是P的左子节点（P是G的左子节点）

   • 操作：将P变为黑色，G变为红色，然后对G进行右旋。
   • 理由：通过旋转消除连续红色，同时保持黑色高度。

   （对称情况：P是G的右子节点时，操作方向相反。）

示例：插入序列[10, 20, 30]

1. 插入10：作为根节点，变为黑色。
2. 插入20：作为10的右子节点（红色），无冲突。
3. 插入30：
   • 初始插入后，20和30连续红色（违反性质4），且叔节点（10的左子节点，NIL）为黑色。
   • 属于情况2（N是P的右子节点）：对20左旋，转换为情况3。
   • 情况3：将20变黑，10变红，对10右旋。最终根节点为20（黑色）。

删除操作步骤：

1. 二叉搜索树删除：

   • 若删除节点有两个非NIL子节点，用后继节点替换其键值，然后删除后继节点。
   • 实际删除的节点至多有一个非NIL子节点。

2. 调整平衡：

   • 若删除的节点是红色，直接删除无需调整（黑色高度不变）。
   • 若删除的节点是黑色，需通过旋转和变色补偿黑色高度损失。调整分为四种情况（假设被删除节点的替代节点为N，兄弟节点为S）：
     • 情况1：S为红色
       • 操作：将S变黑，P变红，对P左旋（若N是左子节点），转换为情况2/3/4。
     • 情况2：S为黑色，且S的两个子节点均为黑色
       • 操作：将S变红，将P作为新的N递归调整。
     • 情况3：S为黑色，S的左子节点为红色，右子节点为黑色（N是左子节点）
       • 操作：将S变红，S的左子节点变黑，对S右旋，转换为情况4。
     • 情况4：S为黑色，S的右子节点为红色
       • 操作：将S的颜色设为P的颜色，P和S的右子节点变黑，对P左旋，调整完成。

   （对称情况类似。）

关键点：

• 插入和删除的调整均通过有限次旋转（O(log n)次）和变色完成。
• 旋转操作（左旋/右旋）与AVL树类似，但颜色调整规则不同。

红黑树通过相对宽松的平衡条件（允许部分高度不平衡，但黑色高度必须一致），减少了旋转次数，在实践中性能稳定。