技术栈

红黑树是一种自平衡的二叉搜索树，通过颜色属性和旋转操作维护平衡，确保插入、删除、查找等操作的时间复杂度为 O(log n)

一、红黑树的五大性质

颜色属性：
- 每个节点为红色或黑色。
根节点：
- 根节点必须是黑色。
叶子节点：
- 所有叶子节点（NIL节点，空节点）为黑色。
红色节点规则：
- 红色节点的子节点必须为黑色（不能有连续红色节点）。
黑高一致性：
- 从任一节点到其所有叶子节点的路径包含相同数量的 黑色节点（黑高相同）。

二、红黑树的插入操作

插入新节点时默认设为红色，若破坏规则则调整。

1. 插入流程

按二叉搜索树规则插入新节点，设为红色。
若父节点为黑色，直接完成。
若父节点为红色，需调整（分三种情况）。

2. 调整情况

Case 1：叔父节点为红色

将父节点和叔父节点变黑，祖父节点变红。
将祖父节点作为新当前节点，递归处理。

plaintext

     黑(G)                    红(G)
    /   \                   /   \
  红(P) 红(U)   →         黑(P) 黑(U)
  /                       /
红(N)                   红(N)

Case 2：叔父节点为黑色，且当前节点是父节点的右子

以父节点为支点左旋，转化为 Case 3。

plaintext

    黑(G)                  黑(G)
   /   \                 /   \
 红(P) 黑(U)   →       红(N) 黑(U)
   \                   /
   红(N)            红(P)

Case 3：叔父节点为黑色，且当前节点是父节点的左子
- 父节点变黑，祖父节点变红。
- 以祖父节点为支点右旋。
plaintext
```
    黑(G)                  黑(P)
   /   \                 /   \
 红(P) 黑(U)   →       红(N) 红(G)
 /                           \
```

红(N) 黑(U)


---

### 三、红黑树的删除操作
删除节点后可能破坏黑高，需通过旋转和颜色调整修复。

#### 1. **删除流程**
1. 按二叉搜索树规则删除节点。
2. 若删除的是 **红色节点**，直接完成。
3. 若删除的是 **黑色节点**，需调整（分四种情况）。

#### 2. **调整情况**
- **Case 1：兄弟节点为红色**  
- 将兄弟节点变黑，父节点变红。
- 对父节点左旋/右旋，转化为其他情况。
```plaintext
    黑(P)                   红(S)
   /   \                  /   \
 黑(N) 红(S)   →        黑(P) 黑(SR)
      /   \             /   \
  黑(SL) 黑(SR)      黑(N) 黑(SL)

Case 2：兄弟节点为黑色，且其子节点均为黑色

将兄弟节点变红，问题上移至父节点。

plaintext

    黑(P)                   黑(P)
   /   \                  /   \
 黑(N) 黑(S)   →        黑(N) 红(S)
      /   \                  /   \
   黑(SL) 黑(SR)          黑(SL) 黑(SR)

Case 3：兄弟节点为黑色，且左子红、右子黑

将兄弟节点变红，左子变黑。
对兄弟节点右旋，转化为 Case 4。

plaintext

    黑(P)                   黑(P)
   /   \                  /   \
 黑(N) 黑(S)   →        黑(N) 黑(SL)
      /   \                      \
   红(SL) 黑(SR)               红(S)

Case 4：兄弟节点为黑色，且右子红

交换父节点与兄弟节点的颜色。
兄弟节点的右子变黑。
对父节点左旋。

plaintext

    黑(P)                   黑(S)
   /   \                  /   \
 黑(N) 黑(S)   →        红(P) 黑(SR)
      /   \            /   \
    *     红(SR)    黑(N)    *

四、红黑树 vs AVL树

特性	红黑树	AVL树
平衡严格性	相对宽松（最长路径 ≤ 2倍最短路径）	严格（左右子树高度差 ≤ 1）
插入/删除速度	更快（旋转次数少）	较慢（频繁旋转）
查找速度	稍慢（平衡性略低）	更快（高度更平衡）
适用场景	频繁插入删除（如Map、Set）	频繁查找（如数据库索引）

五、红黑树的应用场景

关联容器：
- C++ std::map、Java TreeMap。
内存管理：
- Linux内核的进程调度用红黑树管理进程队列。
数据库索引：
- 某些数据库的索引结构（如InnoDB的辅助索引）。

六、代码示例（Python简化版）

python

class Node:
    def __init__(self, val, color='R'):
        self.val = val
        self.color = color  # 'R' 或 'B'
        self.left = None
        self.right = None
        self.parent = None


class RedBlackTree:
    def __init__(self):
        self.NIL = Node(None, 'B')  # 叶子节点
        self.root = self.NIL

    def insert(self, val):
        # 插入逻辑（需实现旋转和颜色调整）
        pass

    def delete(self, val):
        # 删除逻辑（需处理黑高修复）
        pass

以下是使用 Python 实现红黑树的详细代码和说明。红黑树的核心在于通过颜色规则和旋转操作维护平衡，确保插入、删除等操作的时间复杂度为 O(log n)。

一、红黑树节点定义

python

class RBNode:
    def __init__(self, key, color='R'):
        self.key = key  # 节点值
        self.color = color  # 颜色：'R'（红）或 'B'（黑）
        self.left = None  # 左子节点
        self.right = None  # 右子节点
        self.parent = None  # 父节点

    def is_red(self):
        return self.color == 'R'

    def is_black(self):
        return self.color == 'B'

    def set_red(self):
        self.color = 'R'

    def set_black(self):
        self.color = 'B'

二、红黑树类框架

python

class RedBlackTree:
    def __init__(self):
        self.NIL = RBNode(None, 'B')  # 叶子节点（NIL，黑色）
        self.root = self.NIL  # 根节点初始化为 NIL

    def insert(self, key):
        new_node = RBNode(key)
        new_node.left = self.NIL
        new_node.right = self.NIL
        self._insert_node(new_node)
        self._fix_insert(new_node)  # 插入后修复红黑树性质

    def _insert_node(self, node):
        # 类似二叉搜索树的插入逻辑
        parent = self.NIL
        current = self.root
        while current != self.NIL:
            parent = current
            if node.key < current.key:
                current = current.left
            else:
                current = current.right
        node.parent = parent
        if parent == self.NIL:
            self.root = node
        elif node.key < parent.key:
            parent.left = node
        else:
            parent.right = node

三、旋转操作（核心平衡手段）

1. 左旋

python

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

2. 右旋

python

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

四、插入后修复红黑树性质

python

def _fix_insert(self, node):
    while node.parent.is_red():  # 父节点是红色时需要修复
        if node.parent == node.parent.parent.left:
            uncle = node.parent.parent.right
            # Case 1: 叔父节点是红色
            if uncle.is_red():
                node.parent.set_black()
                uncle.set_black()
                node.parent.parent.set_red()
                node = node.parent.parent
            else:
                # Case 2: 当前节点是父节点的右子
                if node == node.parent.right:
                    node = node.parent
                    self._left_rotate(node)
                # Case 3: 当前节点是父节点的左子
                node.parent.set_black()
                node.parent.parent.set_red()
                self._right_rotate(node.parent.parent)
        else:  # 对称逻辑（父节点是右子）
            uncle = node.parent.parent.left
            if uncle.is_red():
                node.parent.set_black()
                uncle.set_black()
                node.parent.parent.set_red()
                node = node.parent.parent
            else:
                if node == node.parent.left:
                    node = node.parent
                    self._right_rotate(node)
                node.parent.set_black()
                node.parent.parent.set_red()
                self._left_rotate(node.parent.parent)
        # 根节点必须为黑色
        self.root.set_black()

五、红黑树可视化（辅助调试）

python

def print_tree(self, node=None, indent=0):
    if node is None:
        node = self.root
    if node == self.NIL:
        return
    self.print_tree(node.right, indent + 4)
    print(' ' * indent + f"{node.key}({node.color})")
    self.print_tree(node.left, indent + 4)

六、示例用法

python

if __name__ == "__main__":
    rbt = RedBlackTree()
    keys = [7, 3, 18, 10, 22, 8, 11, 26]
    for key in keys:
        rbt.insert(key)
    rbt.print_tree()

输出结果（树的中序表示）：

    26(B)
        22(R)
18(B)
            11(B)
        10(R)
            8(B)
7(B)
        3(B)

七、红黑树操作复杂度

操作	时间复杂度	说明
插入	O(log n)	最多两次旋转
删除	O(log n)	最多三次旋转
查找	O(log n)	与普通二叉搜索树相同
旋转	O(1)	仅调整指针

八、关键注意事项

根节点必须为黑色：每次插入修复后需显式设置根节点颜色。
NIL节点处理：所有叶子节点指向统一的黑色 NIL 节点。
颜色翻转与旋转：通过颜色翻转（父和叔变黑，祖父变红）减少旋转次数。
递归修复：插入后可能需从新节点向上递归修复性质。

通过上述代码可实现一个完整的红黑树结构。删除操作的实现更加复杂，需要处理多种情况，但核心思想与插入类似（通过颜色和旋转修复平衡）。实际应用中，红黑树广泛用于 C++ STL 的 map/set 和 Java 的 TreeMap/TreeSet。

一、红黑树的五大性质 ​

二、红黑树的插入操作 ​

1. 插入流程 ​

2. 调整情况 ​

四、红黑树 vs AVL树 ​

五、红黑树的应用场景 ​

六、代码示例（Python简化版） ​

一、红黑树节点定义 ​

二、红黑树类框架 ​

三、旋转操作（核心平衡手段） ​

1. 左旋 ​

2. 右旋 ​

四、插入后修复红黑树性质 ​

五、红黑树可视化（辅助调试） ​

六、示例用法 ​

输出结果（树的中序表示）： ​

七、红黑树操作复杂度 ​

八、关键注意事项 ​

一、红黑树的五大性质

二、红黑树的插入操作

1. 插入流程

2. 调整情况

四、红黑树 vs AVL树

五、红黑树的应用场景

六、代码示例（Python简化版）

一、红黑树节点定义

二、红黑树类框架

三、旋转操作（核心平衡手段）

1. 左旋

2. 右旋

四、插入后修复红黑树性质

五、红黑树可视化（辅助调试）

六、示例用法

输出结果（树的中序表示）：

七、红黑树操作复杂度

八、关键注意事项