跳到主要内容

数据结构 Tree 红黑树

1. 为什么需要红黑树？从问题出发​

1.1 普通二叉搜索树的问题​

问题场景： 假设你在开发一个学生成绩管理系统，需要按学号快速查找学生：

// 如果学号是按顺序插入：001, 002, 003, 004...
// 普通BST会退化成链表，查找时间从O(log n)变成O(n)
class Student {
    String id;      // 学号
    String name;    // 姓名
    int score;      // 成绩
}

// 最坏情况：查找学号"010"需要遍历10个节点
// 如果有10万学生，可能需要遍历10万次！

1.2 红黑树的解决方案​

红黑树通过颜色规则保证树的平衡，确保最长路径不会超过最短路径的2倍。

2. 红黑树的五大规则​

红黑树的五大铁律：​

  1. 根节点必须是黑色 - 就像"皇帝"必须穿黑色龙袍
  2. 叶子节点(NIL)都是黑色 - 边界统一为黑色
  3. 红色节点的子节点必须是黑色 - 红色不能相邻，避免"红色堆积"
  4. 从任意节点到叶子的所有路径包含相同数量的黑色节点 - 保证"黑高"一致
  5. 新插入的节点默认是红色 - 减少对黑高的影响

记忆口诀：根叶黑，红不邻，黑路同，新节红

3. 红黑树的关键操作​

3.1 左旋转操作​

左旋的应用场景： 当右子树过重时，通过左旋将右子树的根提升为新根。

// 左旋操作代码
private Node leftRotate(Node x) {
    Node y = x.right;        // y是x的右子节点
    x.right = y.left;        // β子树成为x的右子树
    if (y.left != null) {
        y.left.parent = x;
    }
    y.parent = x.parent;     // y替代x的位置
    if (x.parent == null) {
        root = y;            // y成为新根
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }
    y.left = x;              // x成为y的左子节点
    x.parent = y;
    return y;
}

3.2 右旋转操作​

4. 插入操作详解​

4.1 插入步骤流程图​

4.2 插入的三种情况详解​

情况1：叔叔节点是红色​

解决方案：重新着色

  • 父节点和叔叔节点变黑色
  • 祖父节点变红色
  • 继续向上检查祖父节点

情况2：叔叔节点是黑色，且是"一条线"（左-左或右-右）​

解决方案：

  1. 对祖父节点进行旋转（左-左情况右旋，右-右情况左旋）
  2. 交换父节点和祖父节点的颜色

情况3：叔叔节点是黑色，且是"之字形"（左-右或右-左）​

解决方案：

  1. 先旋转将"之字形"变为"一条线"
  2. 然后按情况2处理

5. 删除操作详解​

删除操作比插入更复杂，因为需要考虑被删除节点的颜色和子节点情况。

5.1 删除步骤​

5.2 删除修复的情况​

当删除黑色节点时，会破坏黑高平衡，需要进行修复：

// 删除修复的核心思想：
// 1. 如果删除红色节点 - 不影响黑高，无需修复
// 2. 如果删除黑色节点 - 影响黑高，需要修复
private void deleteFixup(Node x) {
    while (x != root && x.color == BLACK) {
        if (x == x.parent.left) {
            Node w = x.parent.right; // w是x的兄弟节点
            
            // 情况1：兄弟节点是红色
            if (w.color == RED) {
                w.color = BLACK;
                x.parent.color = RED;
                leftRotate(x.parent);
                w = x.parent.right;
            }
            
            // 情况2：兄弟节点是黑色，且兄弟的两个子节点都是黑色
            if (w.left.color == BLACK && w.right.color == BLACK) {
                w.color = RED;
                x = x.parent;
            } else {
                // 情况3：兄弟节点是黑色，兄弟的右子节点是黑色，左子节点是红色
                if (w.right.color == BLACK) {
                    w.left.color = BLACK;
                    w.color = RED;
                    rightRotate(w);
                    w = x.parent.right;
                }
                
                // 情况4：兄弟节点是黑色，兄弟的右子节点是红色
                w.color = x.parent.color;
                x.parent.color = BLACK;
                w.right.color = BLACK;
                leftRotate(x.parent);
                x = root;
            }
        } else {
            // 对称情况（x是右子节点）
            // ... 类似的处理逻辑
        }
    }
    x.color = BLACK;
}

6. 时间复杂度分析​

6.1 红黑树 vs 其他数据结构​

6.2 为什么是O(log n)？​

红黑树保证了最长路径不超过最短路径的2倍：

  • 最短路径：全是黑色节点
  • 最长路径：黑红交替

如果黑高为h，那么：

  • 最短路径长度：h
  • 最长路径长度：2h

因此树高被限制在2×log(n+1)以内。

7. 实际应用场景​

7.1 Java中的TreeMap/TreeSet​

// TreeMap内部就是红黑树实现
public class StudentManager {
    // 按学号排序的学生集合
    private TreeMap<String, Student> students = new TreeMap<>();
    
    // O(log n)时间内添加学生
    public void addStudent(String id, Student student) {
        students.put(id, student);  // 内部使用红黑树
    }
    
    // O(log n)时间内查找学生
    public Student findStudent(String id) {
        return students.get(id);
    }
    
    // 获取成绩前10名（利用红黑树的有序性）
    public List<Student> getTopStudents(int count) {
        return students.values().stream()
            .sorted((s1, s2) -> s2.score - s1.score)
            .limit(count)
            .collect(Collectors.toList());
    }
}

7.2 Linux内核中的进程调度​

// Linux CFS调度器使用红黑树管理进程
struct cfs_rq {
    struct rb_root tasks_timeline;  // 红黑树根节点
    struct rb_node *rb_leftmost;    // 最左节点（最需要CPU的进程）
};

// 按虚拟运行时间排序进程
// 虚拟时间越小，越需要CPU时间

7.3 数据库索引​

-- MySQL的B+树索引在某些情况下会退化为红黑树的变种
CREATE INDEX idx_student_score ON students(score);

-- 查询时能快速定位
SELECT * FROM students WHERE score BETWEEN 80 AND 95;
-- 时间复杂度：O(log n + k)，其中k是结果数量

8. 红黑树 vs AVL树​

选择建议：

  • 查找密集型应用：选择AVL树（如字典、静态数据）
  • 增删密集型应用：选择红黑树（如缓存、动态数据）

9. 常见面试问题​

9.1 为什么新节点是红色？​

// 如果新节点是黑色，会立即破坏黑高平衡
// 如果新节点是红色，只有当父节点也是红色时才违反规则
// 这样需要修复的情况更少，效率更高

public Node insert(int key) {
    Node newNode = new Node(key);
    newNode.color = RED;  // 默认红色
    // ... 插入逻辑
    return newNode;
}

9.2 红黑树如何保证平衡？​

通过颜色约束和旋转操作：

  1. 颜色约束：限制最长路径长度
  2. 旋转操作：在保持BST性质的同时调整结构
  3. 重新着色：修复颜色冲突

9.3 红黑树的实际性能​

// 百万数据测试
public class PerformanceTest {
    public static void main(String[] args) {
        TreeMap<Integer, String> rbTree = new TreeMap<>();
        long start = System.currentTimeMillis();
        
        // 插入100万数据
        for (int i = 0; i < 1000000; i++) {
            rbTree.put(i, "value" + i);
        }
        long insertTime = System.currentTimeMillis() - start;
        
        start = System.currentTimeMillis();
        // 查找10万次
        for (int i = 0; i < 100000; i++) {
            rbTree.get(i);
        }
        long searchTime = System.currentTimeMillis() - start;
        
        System.out.println("插入100万数据耗时: " + insertTime + "ms");
        System.out.println("查找10万次耗时: " + searchTime + "ms");
        
        // 典型结果：插入300ms，查找50ms
    }
}