08-红黑树

💡 核心结论

红黑树本质

  • 定义：自平衡二叉搜索树，通过颜色约束保持近似平衡

  • 性能：所有操作O(log n)，最坏情况有保证

  • 平衡性：最长路径 ≤ 2倍最短路径（比AVL宽松）

  • 核心：用颜色规则代替严格高度平衡，减少旋转次数

  • 应用：C++ STL、Java TreeMap、Linux内核

红黑树 vs AVL树

特性

红黑树

AVL树

平衡度

近似平衡

严格平衡

插入旋转

≤2次

≤2次

删除旋转

≤3次

O(log n)

查询性能

稍慢

最快

插入删除

最快

较慢

选择

插入删除多

查询多

五大性质（必背）

  1. 节点是红色或黑色

  2. 根节点是黑色

  3. 叶子节点（NIL）是黑色

  4. 红色节点的子节点都是黑色（无连续红色）

  5. 任一节点到叶子的所有路径包含相同数量的黑色节点

为什么这样设计

  • 性质4：避免连续红色，限制红色节点数量

  • 性质5：保证黑高度相同，确保平衡性

  • 结果：最长路径（红黑交替）≤ 2倍最短路径（全黑）

🌳 红黑树性质

五大性质

  1. 节点是红色或黑色

  2. 根节点是黑色

  3. 所有叶子节点（NIL）是黑色

  4. 红色节点的两个子节点都是黑色（不能有连续的红色节点）

  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

性质保证

  • 最长路径（红黑交替）≤ 最短路径（全黑）的2倍

  • 树的高度：h ≤ 2log(n+1)

  • 查找、插入、删除：O(log n)

🎯 红黑树 vs AVL树

特性

AVL树

红黑树

平衡性

严格平衡

近似平衡

平衡因子

高度差≤1

最长路径≤2倍最短路径

旋转次数

插入1-2次，删除O(log n)

插入≤2次，删除≤3次

查询性能

更快

稍慢

插入删除

较慢

更快

应用场景

查询密集

插入删除密集

实际应用

Windows NT内核

Linux内核、C++ STL

🔄 旋转操作

左旋

    x                y
   / \              / \
  a   y    =>      x   c
     / \          / \
    b   c        a   b

右旋

      y            x
     / \          / \
    x   c  =>    a   y
   / \              / \
  a   b            b   c

🎨 插入操作

插入步骤

  1. 按BST规则插入新节点（红色）

  2. 修复红黑树性质

  3. 情况分类处理

插入修复情况

情况1：叔叔是红色

  • 父亲和叔叔变黑

  • 爷爷变红

  • 爷爷作为新节点继续修复

情况2：叔叔是黑色，当前节点是右孩子

  • 左旋父节点

  • 转换为情况3

情况3：叔叔是黑色，当前节点是左孩子

  • 父亲变黑

  • 爷爷变红

  • 右旋爷爷

🗑️ 删除操作

删除步骤

  1. 按BST规则删除节点

  2. 如果删除的是黑色节点，需要修复

  3. 情况分类处理

删除修复情况

情况1：兄弟是红色

  • 父亲变红

  • 兄弟变黑

  • 左旋父亲

  • 转换为其他情况

情况2：兄弟是黑色，兄弟的两个孩子都是黑色

  • 兄弟变红

  • 父亲作为新节点继续修复

情况3：兄弟是黑色，兄弟的左孩子是红色，右孩子是黑色

  • 兄弟变红

  • 兄弟的左孩子变黑

  • 右旋兄弟

  • 转换为情况4

情况4：兄弟是黑色，兄弟的右孩子是红色

  • 兄弟颜色 = 父亲颜色

  • 父亲变黑

  • 兄弟的右孩子变黑

  • 左旋父亲

🔧 应用场景

C++ STL

  • std::map

  • std::set

  • std::multimap

  • std::multiset

Java

  • TreeMap

  • TreeSet

Linux内核

  • 完全公平调度器（CFS）

  • 虚拟内存管理

其他

  • epoll实现

  • nginx定时器

💡 实现要点

哨兵节点（NIL）

class NIL:
    """哨兵节点"""
    def __init__(self):
        self.color = BLACK
        self.left = self
        self.right = self
        self.parent = None

# 使用全局NIL节点
NIL_NODE = NIL()

颜色表示

RED = 0
BLACK = 1

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

📚 时间复杂度分析

操作

平均

最坏

查找

O(log n)

O(log n)

插入

O(log n)

O(log n)

删除

O(log n)

O(log n)

最小/最大

O(log n)

O(log n)

空间复杂度：O(n)

🎯 性能特点

优势

  1. 最坏情况性能保证 O(log n)

  2. 插入删除平均旋转次数少

  3. 实现相对简单（相比B树）

劣势

  1. 代码复杂度高于AVL树

  2. 常数因子较大

  3. 查询性能略逊于AVL树

📚 LeetCode练习

虽然LeetCode很少直接考察红黑树实现，但理解红黑树有助于：

  • 理解STL容器性能

  • 系统设计问题

  • 面试中的数据结构选择

💡 学习建议

  1. 先掌握BST和AVL树

  2. 理解五大性质的作用

  3. 画图理解旋转和变色

  4. 重点掌握插入过程

  5. 删除操作可以适当简化理解

  6. 了解实际应用场景

📚 参考资料

💻 完整代码实现

Python 实现

  1"""
  2红黑树实现
  3"""
  4
  5# 颜色常量
  6RED = 0
  7BLACK = 1
  8
  9
 10class RBNode:
 11    """红黑树节点"""
 12    
 13    def __init__(self, val, color=RED):
 14        self.val = val
 15        self.color = color
 16        self.left = None
 17        self.right = None
 18        self.parent = None
 19
 20
 21class RBTree:
 22    """红黑树实现"""
 23    
 24    def __init__(self):
 25        # 哨兵节点
 26        self.NIL = RBNode(0, BLACK)
 27        self.NIL.left = self.NIL
 28        self.NIL.right = self.NIL
 29        
 30        self.root = self.NIL
 31    
 32    def insert(self, val):
 33        """插入节点"""
 34        # BST插入
 35        new_node = RBNode(val, RED)
 36        new_node.left = self.NIL
 37        new_node.right = self.NIL
 38        
 39        parent = None
 40        curr = self.root
 41        
 42        while curr != self.NIL:
 43            parent = curr
 44            if val < curr.val:
 45                curr = curr.left
 46            else:
 47                curr = curr.right
 48        
 49        new_node.parent = parent
 50        
 51        if parent is None:
 52            self.root = new_node
 53        elif val < parent.val:
 54            parent.left = new_node
 55        else:
 56            parent.right = new_node
 57        
 58        # 修复红黑树性质
 59        self._insert_fixup(new_node)
 60    
 61    def _insert_fixup(self, node):
 62        """插入后修复"""
 63        while node.parent and node.parent.color == RED:
 64            if node.parent == node.parent.parent.left:
 65                uncle = node.parent.parent.right
 66                
 67                if uncle.color == RED:
 68                    # 情况1：叔叔是红色
 69                    node.parent.color = BLACK
 70                    uncle.color = BLACK
 71                    node.parent.parent.color = RED
 72                    node = node.parent.parent
 73                else:
 74                    if node == node.parent.right:
 75                        # 情况2：当前节点是右孩子
 76                        node = node.parent
 77                        self._left_rotate(node)
 78                    
 79                    # 情况3：当前节点是左孩子
 80                    node.parent.color = BLACK
 81                    node.parent.parent.color = RED
 82                    self._right_rotate(node.parent.parent)
 83            else:
 84                # 对称情况
 85                uncle = node.parent.parent.left
 86                
 87                if uncle.color == RED:
 88                    node.parent.color = BLACK
 89                    uncle.color = BLACK
 90                    node.parent.parent.color = RED
 91                    node = node.parent.parent
 92                else:
 93                    if node == node.parent.left:
 94                        node = node.parent
 95                        self._right_rotate(node)
 96                    
 97                    node.parent.color = BLACK
 98                    node.parent.parent.color = RED
 99                    self._left_rotate(node.parent.parent)
100        
101        self.root.color = BLACK
102    
103    def _left_rotate(self, x):
104        """左旋"""
105        y = x.right
106        x.right = y.left
107        
108        if y.left != self.NIL:
109            y.left.parent = x
110        
111        y.parent = x.parent
112        
113        if x.parent is None:
114            self.root = y
115        elif x == x.parent.left:
116            x.parent.left = y
117        else:
118            x.parent.right = y
119        
120        y.left = x
121        x.parent = y
122    
123    def _right_rotate(self, y):
124        """右旋"""
125        x = y.left
126        y.left = x.right
127        
128        if x.right != self.NIL:
129            x.right.parent = y
130        
131        x.parent = y.parent
132        
133        if y.parent is None:
134            self.root = x
135        elif y == y.parent.left:
136            y.parent.left = x
137        else:
138            y.parent.right = x
139        
140        x.right = y
141        y.parent = x
142    
143    def search(self, val):
144        """查找节点"""
145        curr = self.root
146        while curr != self.NIL and curr.val != val:
147            if val < curr.val:
148                curr = curr.left
149            else:
150                curr = curr.right
151        return curr if curr != self.NIL else None
152    
153    def inorder(self):
154        """中序遍历"""
155        result = []
156        self._inorder_helper(self.root, result)
157        return result
158    
159    def _inorder_helper(self, node, result):
160        """中序遍历辅助函数"""
161        if node != self.NIL:
162            self._inorder_helper(node.left, result)
163            result.append(node.val)
164            self._inorder_helper(node.right, result)
165    
166    def print_tree(self, node=None, level=0, prefix="Root: "):
167        """打印树结构"""
168        if node is None:
169            node = self.root
170        
171        if node != self.NIL:
172            color = "🔴" if node.color == RED else "⚫"
173            print(" " * (level * 4) + prefix + f"{color}{node.val}")
174            if node.left != self.NIL or node.right != self.NIL:
175                self.print_tree(node.left, level + 1, "L--- ")
176                self.print_tree(node.right, level + 1, "R--- ")
177
178
179def demo():
180    """演示红黑树的使用"""
181    print("=== 红黑树演示 ===\n")
182    
183    tree = RBTree()
184    
185    # 插入节点
186    values = [7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13]
187    print(f"插入节点: {values}\n")
188    
189    for val in values:
190        tree.insert(val)
191        print(f"插入 {val}:")
192        tree.print_tree()
193        print()
194    
195    # 中序遍历
196    print("中序遍历（应该是有序的）:")
197    print(tree.inorder())
198    print()
199    
200    # 查找
201    search_val = 10
202    result = tree.search(search_val)
203    if result:
204        color = "红色" if result.color == RED else "黑色"
205        print(f"找到节点 {search_val}，颜色: {color}")
206    else:
207        print(f"未找到节点 {search_val}")
208
209
210if __name__ == '__main__':
211    demo()
212

C++ 实现

  1/**
  2 * 红黑树实现（简化版，仅实现插入）
  3 * 完整实现较复杂，建议学习STL源码
  4 */
  5
  6#include <iostream>
  7
  8enum Color { RED, BLACK };
  9
 10struct RBNode {
 11    int val;
 12    Color color;
 13    RBNode* left;
 14    RBNode* right;
 15    RBNode* parent;
 16    
 17    RBNode(int v) : val(v), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
 18};
 19
 20
 21class RBTree {
 22private:
 23    RBNode* root;
 24    RBNode* NIL;  // 哨兵节点
 25    
 26    void leftRotate(RBNode* x) {
 27        RBNode* y = x->right;
 28        x->right = y->left;
 29        
 30        if (y->left != NIL) {
 31            y->left->parent = x;
 32        }
 33        
 34        y->parent = x->parent;
 35        
 36        if (!x->parent) {
 37            root = y;
 38        } else if (x == x->parent->left) {
 39            x->parent->left = y;
 40        } else {
 41            x->parent->right = y;
 42        }
 43        
 44        y->left = x;
 45        x->parent = y;
 46    }
 47    
 48    void rightRotate(RBNode* y) {
 49        RBNode* x = y->left;
 50        y->left = x->right;
 51        
 52        if (x->right != NIL) {
 53            x->right->parent = y;
 54        }
 55        
 56        x->parent = y->parent;
 57        
 58        if (!y->parent) {
 59            root = x;
 60        } else if (y == y->parent->left) {
 61            y->parent->left = x;
 62        } else {
 63            y->parent->right = x;
 64        }
 65        
 66        x->right = y;
 67        y->parent = x;
 68    }
 69    
 70    void insertFixup(RBNode* node) {
 71        while (node->parent && node->parent->color == RED) {
 72            if (node->parent == node->parent->parent->left) {
 73                RBNode* uncle = node->parent->parent->right;
 74                
 75                if (uncle->color == RED) {
 76                    // 情况1
 77                    node->parent->color = BLACK;
 78                    uncle->color = BLACK;
 79                    node->parent->parent->color = RED;
 80                    node = node->parent->parent;
 81                } else {
 82                    if (node == node->parent->right) {
 83                        // 情况2
 84                        node = node->parent;
 85                        leftRotate(node);
 86                    }
 87                    // 情况3
 88                    node->parent->color = BLACK;
 89                    node->parent->parent->color = RED;
 90                    rightRotate(node->parent->parent);
 91                }
 92            } else {
 93                RBNode* uncle = node->parent->parent->left;
 94                
 95                if (uncle->color == RED) {
 96                    node->parent->color = BLACK;
 97                    uncle->color = BLACK;
 98                    node->parent->parent->color = RED;
 99                    node = node->parent->parent;
100                } else {
101                    if (node == node->parent->left) {
102                        node = node->parent;
103                        rightRotate(node);
104                    }
105                    node->parent->color = BLACK;
106                    node->parent->parent->color = RED;
107                    leftRotate(node->parent->parent);
108                }
109            }
110        }
111        root->color = BLACK;
112    }
113    
114    void printTreeHelper(RBNode* node, int level, std::string prefix) {
115        if (node && node != NIL) {
116            std::string colorStr = (node->color == RED) ? "🔴" : "⚫";
117            std::cout << std::string(level * 4, ' ') << prefix 
118                      << colorStr << node->val << std::endl;
119            if (node->left != NIL || node->right != NIL) {
120                printTreeHelper(node->left, level + 1, "L--- ");
121                printTreeHelper(node->right, level + 1, "R--- ");
122            }
123        }
124    }
125
126public:
127    RBTree() {
128        NIL = new RBNode(0);
129        NIL->color = BLACK;
130        NIL->left = NIL->right = NIL->parent = nullptr;
131        root = NIL;
132    }
133    
134    void insert(int val) {
135        RBNode* newNode = new RBNode(val);
136        newNode->left = NIL;
137        newNode->right = NIL;
138        
139        RBNode* parent = nullptr;
140        RBNode* curr = root;
141        
142        while (curr != NIL) {
143            parent = curr;
144            if (val < curr->val) {
145                curr = curr->left;
146            } else {
147                curr = curr->right;
148            }
149        }
150        
151        newNode->parent = parent;
152        
153        if (!parent) {
154            root = newNode;
155        } else if (val < parent->val) {
156            parent->left = newNode;
157        } else {
158            parent->right = newNode;
159        }
160        
161        insertFixup(newNode);
162    }
163    
164    void printTree() {
165        printTreeHelper(root, 0, "Root: ");
166    }
167};
168
169
170int main() {
171    std::cout << "=== 红黑树演示 ===" << std::endl << std::endl;
172    
173    RBTree tree;
174    
175    std::vector<int> values = {7, 3, 18, 10, 22, 8, 11, 26};
176    std::cout << "插入节点: ";
177    for (int val : values) {
178        std::cout << val << " ";
179    }
180    std::cout << std::endl << std::endl;
181    
182    for (int val : values) {
183        tree.insert(val);
184        std::cout << "插入 " << val << ":" << std::endl;
185        tree.printTree();
186        std::cout << std::endl;
187    }
188    
189    return 0;
190}