平衡树：AVL & 红黑树

AVL 树

AVL 树（1962）是最早的自平衡 BST，以平衡因子 bf = h(right) − h(left) 监控平衡性，插入/删除后若某节点 |bf| > 1 则立即通过旋转修复。

四种旋转情形

• LL（bf < −1，左孩子 bf ≤ 0）：对失衡节点右旋
• RR（bf > 1，右孩子 bf ≥ 0）：对失衡节点左旋
• LR（bf < −1，左孩子 bf > 0）：先左旋左孩子，再右旋失衡节点
• RL（bf > 1，右孩子 bf < 0）：先右旋右孩子，再左旋失衡节点

插入流程

1. 按 BST 规则找到插入位置，创建新节点
2. 回溯更新每个祖先的树高 h
3. 遇到第一个 |bf| > 1 的节点，判断情形并执行旋转

// AVL Tree — balanced BST with balance factor, O(log n) insert
struct N { int key, h; N *l, *r; N(int k):key(k),h(0),l(nullptr),r(nullptr){} };

int ht(N* n) { return n ? n->h : -1; }
void upd(N* n) { if (n) n->h = 1 + max(ht(n->l), ht(n->r)); }
int bf(N* n)  { return n ? ht(n->r) - ht(n->l) : 0; }

N* rotL(N* x) { N* y=x->r; x->r=y->l; y->l=x; upd(x); upd(y); return y; }
N* rotR(N* x) { N* y=x->l; x->l=y->r; y->r=x; upd(x); upd(y); return y; }

N* rebal(N* n) {
    upd(n);
    if (bf(n) > 1)  { if (bf(n->r) < 0) n->r = rotR(n->r); return rotL(n); }
    if (bf(n) < -1) { if (bf(n->l) > 0) n->l = rotL(n->l); return rotR(n); }
    return n;
}
N* ins(N* n, int k) {
    if (!n) return new N(k);
    if (k < n->key) n->l = ins(n->l, k);
    else if (k > n->key) n->r = ins(n->r, k);
    return rebal(n);
}
void inorder(N* n, vector<int>& v) {
    if (!n) return;
    inorder(n->l, v); v.push_back(n->key); inorder(n->r, v);
}

适用场景：读多写少（数据库历史索引）；高度严格 ≤ 1.44 log₂ n，查找比红黑树略快，但写入时旋转次数偏多。

红黑树

红黑树（1978）通过节点染色替代精确平衡，插入最多 2 次旋转，删除最多 3 次，是 std::map / std::set / Linux CFS 的底层结构。

5 条不变量

1. 每个节点为红色或黑色
2. 根节点为黑色
3. 所有叶节点（NIL 哨兵）为黑色
4. 红色节点的两个子节点均为黑色（无相邻红节点）
5. 任意节点到后代 NIL 叶的路径包含相同数量的黑色节点（黑高相等）

插入修复（叔父颜色驱动）

• Case 1：叔父红 → 父/叔染黑，祖父染红，z 上移到祖父，递归处理
• Case 2：叔父黑，z 为内侧孩子（折形）→ 旋转父节点，转化为 Case 3
• Case 3：叔父黑，z 为外侧孩子（直线）→ 旋转祖父 + 重染色，结束

删除修复（4 种情形）

• Case 1：兄弟红 → 旋转父节点，转化为 Case 2–4
• Case 2：兄弟黑，两侄子均黑 → 兄弟染红，x 上移
• Case 3：兄弟黑，近侄子红/远侄子黑 → 旋转兄弟，转化为 Case 4
• Case 4：兄弟黑，远侄子红 → 旋转父节点 + 重染色，结束

// Red-Black Tree — insert + fix-up, O(log n)
struct RBN { int key; bool red; RBN *l, *r, *p; };
RBN* NIL; // global black sentinel — NIL->l = NIL->r = NIL->p = NIL

void rotL(RBN*& root, RBN* x) {
    RBN* y = x->r; x->r = y->l;
    if (y->l != NIL) y->l->p = x;
    y->p = x->p;
    if (x->p == NIL) root = y;
    else if (x == x->p->l) x->p->l = y; else x->p->r = y;
    y->l = x; x->p = y;
}
void rotR(RBN*& root, RBN* x) {
    RBN* y = x->l; x->l = y->r;
    if (y->r != NIL) y->r->p = x;
    y->p = x->p;
    if (x->p == NIL) root = y;
    else if (x == x->p->r) x->p->r = y; else x->p->l = y;
    y->r = x; x->p = y;
}
void fixIns(RBN*& root, RBN* z) {
    while (z->p->red) {
        bool onLeft = (z->p == z->p->p->l);
        RBN* u = onLeft ? z->p->p->r : z->p->p->l;
        if (u->red) {                               // Case 1: uncle red
            z->p->red = u->red = false;
            z->p->p->red = true;
            z = z->p->p;
        } else {
            if (onLeft ? z == z->p->r : z == z->p->l) { // Case 2: inner child
                z = z->p;
                onLeft ? rotL(root, z) : rotR(root, z);
            }
            z->p->red = false; z->p->p->red = true;     // Case 3: outer child
            onLeft ? rotR(root, z->p->p) : rotL(root, z->p->p);
        }
    }
    root->red = false;
}
void rbInsert(RBN*& root, int k) {
    RBN* z = new RBN{k, true, NIL, NIL, NIL};
    RBN* y = NIL, *x = root;
    while (x != NIL) { y = x; x = (k < x->key) ? x->l : x->r; }
    z->p = y;
    if (y == NIL) root = z;
    else if (k < y->key) y->l = z; else y->r = z;
    fixIns(root, z);
}

关键实现细节：使用全局哨兵 NIL（颜色固定为黑）代替 nullptr；所有空子节点均指向 NIL；根节点最终置为黑色。

对比与选型

四种常见自平衡 BST 的核心差异：