深入理解红黑树：Python红黑树实现详解（从零开始掌握红黑树数据结构）

为什么使用红黑树？

红黑树在很多系统中被广泛使用，例如 Linux 内核中的进程调度、C++ STL 的 map/set 等。它的主要优势在于：插入、删除、查找操作的时间复杂度均为 O(log n)，非常适合需要频繁动态更新的数据集合。

掌握红黑树数据结构不仅有助于提升算法能力，还能加深对平衡树机制的理解。

Python 实现红黑树

下面我们用 Python 从零开始实现一个简单的红黑树。我们将定义节点类和红黑树类，并实现插入操作及其所需的修复逻辑。

1. 定义节点类

class RBNode:    def __init__(self, val):        self.val = val           # 节点值        self.parent = None       # 父节点        self.left = None         # 左子节点        self.right = None        # 右子节点        self.color = 'RED'       # 初始为红色（插入时）

2. 定义红黑树类框架

class RedBlackTree:    def __init__(self):        self.NIL = RBNode(0)          # 创建哨兵 NIL 节点        self.NIL.color = 'BLACK'        self.NIL.left = None        self.NIL.right = None        self.root = self.NIL

3. 插入操作与修复

插入新节点后，可能会破坏红黑树的性质，因此我们需要进行“修复”（fix-up）。修复主要通过颜色翻转和树旋转（左旋/右旋）完成。

    def insert(self, val):        new_node = RBNode(val)        new_node.left = self.NIL        new_node.right = self.NIL        parent = None        current = self.root        # 找到插入位置（类似普通BST）        while current != self.NIL:            parent = current            if new_node.val < current.val:                current = current.left            else:                current = current.right        new_node.parent = parent        if parent is None:            self.root = new_node        elif new_node.val < parent.val:            parent.left = new_node        else:            parent.right = new_node        # 如果是根节点，直接设为黑色        if new_node.parent is None:            new_node.color = 'BLACK'            return        # 如果祖父不存在，无需修复        if new_node.parent.parent is None:            return        # 修复红黑树性质        self._fix_insert(new_node)

4. 修复函数（核心逻辑）

    def _fix_insert(self, node):        while node.parent.color == 'RED':            if node.parent == node.parent.parent.right:                uncle = node.parent.parent.left                if uncle.color == 'RED':                    # 情况1：叔叔是红色 → 变色                    uncle.color = 'BLACK'                    node.parent.color = 'BLACK'                    node.parent.parent.color = 'RED'                    node = node.parent.parent                else:                    if node == node.parent.left:                        # 情况2：节点是左孩子 → 先右旋                        node = node.parent                        self._right_rotate(node)                    # 情况3：节点是右孩子 → 左旋 + 变色                    node.parent.color = 'BLACK'                    node.parent.parent.color = 'RED'                    self._left_rotate(node.parent.parent)            else:                uncle = node.parent.parent.right                if uncle.color == 'RED':                    uncle.color = 'BLACK'                    node.parent.color = 'BLACK'                    node.parent.parent.color = 'RED'                    node = node.parent.parent                else:                    if node == node.parent.right:                        node = node.parent                        self._left_rotate(node)                    node.parent.color = 'BLACK'                    node.parent.parent.color = 'RED'                    self._right_rotate(node.parent.parent)            if node == self.root:                break        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 is 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, x):        y = x.left        x.left = y.right        if y.right != self.NIL:            y.right.parent = x        y.parent = x.parent        if x.parent is None:            self.root = y        elif x == x.parent.right:            x.parent.right = y        else:            x.parent.left = y        y.right = x        x.parent = y

完整使用示例

# 创建红黑树并插入元素rbt = RedBlackTree()for val in [10, 20, 30, 15, 25]:    rbt.insert(val)# 此时树已自动平衡，满足红黑树所有性质

总结

通过本教程，你已经掌握了如何用 Python 实现红黑树的基本插入功能。虽然完整的红黑树还包括删除操作（更为复杂），但理解插入修复机制是学习Python平衡二叉树的关键一步。

红黑树的难点在于各种情况的判断和旋转逻辑，建议你动手画图模拟每一步操作，加深理解。掌握红黑树插入删除算法后，你将能应对更复杂的算法面试题和系统设计场景。

提示：实际项目中可优先使用 Python 的 sortedcontainers 或 bisect 模块，但在学习数据结构时，手动实现红黑树极具价值。