Python 数据结构：红黑树（Red-Black Tree, RB Tree）基本结构

# /*
# Python 数据结构：红黑树（Red-Black Tree, RB Tree）基本结构
# --------------------------------------------------------
# 概念：
# 红黑树是一种自平衡二叉搜索树（BST），满足以下性质：
# 1) 节点是红色或黑色；
# 2) 根节点为黑色；
# 3) 所有叶子节点（NIL）为黑色；
# 4) 红色节点的子节点必须为黑色（即不能有连续红色节点）；
# 5) 从任一节点到其所有子孙叶子节点的路径上，黑色节点数相同。
#
# 红黑树保证在最坏情况下的树高为 O(log n)，从而保证插入、删除和查找的时间复杂度。
# */

# ========================================================
# 红黑树节点定义
# ========================================================
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):
        self.NIL = RBNode(key=None, color='black')  # 哨兵节点
        self.root = self.NIL

    # 创建新节点（默认红色）
    def create_node(self, key):
        node = RBNode(key=key, color='red', left=self.NIL, right=self.NIL, parent=None)
        return node

    # 基础插入（不含平衡调整，仅用于示意结构）
    def insert(self, key):
        new_node = self.create_node(key)
        parent = None
        current = self.root

        while current != self.NIL:
            parent = current
            if key < current.key:
                current = current.left
            else:
                current = current.right

        new_node.parent = parent
        if parent is None:
            self.root = new_node
        elif key < parent.key:
            parent.left = new_node
        else:
            parent.right = new_node

        # 插入后应进行修正保持红黑性质（未实现旋转/修复逻辑）
        # self.fix_insert(new_node)

    # 中序遍历（升序输出）
    def inorder_traversal(self, node=None):
        if node is None:
            node = self.root
        result = []

        def _inorder(n):
            if n != self.NIL:
                _inorder(n.left)
                result.append((n.key, n.color))
                _inorder(n.right)

        _inorder(node)
        return result

# ========================================================
# 示例演示
# ========================================================
rbt = RedBlackTree()
for val in [10, 20, 30, 15, 25]:
    rbt.insert(val)

print("红黑树中序遍历（节点值, 颜色）：", rbt.inorder_traversal())

# ========================================================
# 要点总结：
# --------------------------------------------------------
# 1) 红黑树是一种自平衡 BST，通过节点颜色约束平衡树高；
# 2) 插入和删除后可能需要旋转和重新着色保持红黑性质；
# 3) 根节点始终为黑色，叶子节点为 NIL 哨兵黑色节点；
# 4) 红色节点不能连续出现，保证路径黑色节点数量平衡；
# 5) 查找、插入、删除时间复杂度均为 O(log n)；
# 6) 是 AVL 树之外常用的平衡树，插入删除调整操作通常比 AVL 树更简单。
# */
#
# 红黑树中序遍历（节点值, 颜色）：
# [(10, 'red'), (15, 'red'), (20, 'red'), (25, 'red'), (30, 'red')]