红黑树（Red-Black Tree）核心知识点与面试高频问题

红黑树（Red-Black Tree）核心知识点与面试高频问题

一、红黑树的核心性质

红黑树是一种自平衡的二叉搜索树，通过以下规则确保平衡性：

1. 节点颜色：每个节点是红色或黑色。

2. 根节点：根必须是黑色。

3. 叶子节点（NIL）：所有叶子节点（空节点）视为黑色。

4. 红色节点限制：红色节点的子节点必须为黑色（即不能有连续的红色节点）。

5. 黑高平衡：从任意节点到其所有叶子节点的路径上，黑色节点的数量相同（称为黑高）。

二、红黑树的平衡操作

1. 旋转操作（核心面试点）

• 左旋：以某个节点为支点，将其右子节点提升为新的父节点。

• 右旋：以某个节点为支点，将其左子节点提升为新的父节点。

java

// 左旋伪代码示例
void leftRotate(Node x) {
    Node y = x.right;      // 保存x的右子节点y
    x.right = y.left;      // 将y的左子树变为x的右子树
    if (y.left != null) {
        y.left.parent = x; // 更新父节点
    }
    y.parent = x.parent;   // 将y连接到x的父节点
    // 更新父节点的子节点指向
    if (x.parent == null) {
        root = y;
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }
    y.left = x;            // 将x作为y的左子节点
    x.parent = y;
}

2. 插入后的平衡调整（5种情况）

插入的节点默认为红色，可能破坏红黑树性质，需通过变色+旋转恢复平衡：

• Case 1：叔叔节点是红色 → 变色（父、叔变黑，祖父变红）。

• Case 2-3：叔叔节点是黑色，且当前节点是“右-左”或“左-右”结构 → 先旋转父节点，转为Case 4/5。

• Case 4-5：叔叔节点是黑色，且当前节点是“左-左”或“右-右”结构 → 变色后旋转祖父节点。

3. 删除后的平衡调整（更复杂，7种情况）

删除黑色节点后可能破坏黑高平衡，需根据兄弟节点的颜色和子节点结构调整。

三、红黑树 vs AVL树

四、面试高频问题

1. 基础问题

• Q1：红黑树如何保证平衡？
  A：通过颜色约束和旋转操作，确保从根到叶子的最长路径不超过最短路径的2倍。

• Q2：为什么Java HashMap链表长度超过8会转红黑树？
  A：哈希冲突时，链表查询退化为O(n)，红黑树将其优化为O(log n)。

2. 手撕代码

• 实现红黑树的插入逻辑（需处理5种Case）：

  java

void fixAfterInsertion(Node x) {
    while (x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Node y = rightOf(parentOf(parentOf(x))); // 叔叔节点
            if (colorOf(y) == RED) {                 // Case 1
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {     // Case 2
                    x = parentOf(x);
                    leftRotate(x);
                }
                // Case 3
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rightRotate(parentOf(parentOf(x)));
            }
        }
        // 对称处理右子树情况...
    }
    root.color = BLACK;
}

3. 深度问题

• Q：红黑树的黑高如何影响其性能？
  A：黑高保证了最坏情况下路径长度不超过2log(n+1)，确保O(log n)时间复杂度。

• Q：为什么红黑树比AVL树更适合实现Map？
  A：红黑树在插入/删除时旋转次数更少，适合频繁修改的场景；AVL树适合读多写少的场景。

五、红黑树的可视化学习工具

• Red-Black Tree Visualizer：动态演示插入/删除过程。

• 调试技巧：用纸笔画出插入/删除后的树结构，逐步验证变色和旋转逻辑。