数据结构-高级搜索树

高级搜索树

伸展树

• 局部性：刚被访问过的数据，极有可能很快地再次被访问
• BST 的局部性
  • 时间：刚被访问过的节点，极有可能很快地再次被访问
  • 空间：下一将要访问的节点，极有可能就在刚被访问过节点的附近
• 对于 AVL 的连续 $m \gg n$ 次查找，共需 $O(m\log n)$
  • 利用局部性加速：BST 的节点一旦被访问，随即调整到树根

单层伸展

• 节点 v 一旦被访问，随即被推送至根
  • 自下而上，逐层旋转
• 旋转次数呈周期性的算术级数（周期访问所有节点）
  • 每一周期结构会复原，累计 $\Omega(n^2)$ ，分摊 $\Omega(n)$

双层伸展

• 反复考察祖孙三代
  • g = parent(p), p = parent(v), v
  • 根据他们的相对位置，经 两次旋转，使 v 上升两层，成为子树根
    • zig-zag 操作本身就是平衡的，效果很好
    • 对于 zig-zig，先 p 后 g 只会拉长和移动访问路径，无法改善树的整体结构；而先 g 后 p 则能够“折叠”和“打散”访问路径
  • zig 和 zag 不同组合，共计 4 种
    • 可能会在 最后 进行一次单次旋转
• 节点访问之后，对应路径的长度随即 折半
  • 最坏情况显然 $O(n)$ ，但最坏情况不致持续发生
    • 分摊仅需 $O(\log n)$

算法实现

template<typename T> BinNodeposi<T> Splay<T>::splay(BinNodePosi<T> v) {
    BinNodePosi<T> p, q;
    while ((p = v->parent) && (g = p->parent)) {
        BinNodePosi<T> gg = g->parent;
        switch ((IsLChild(p) << 1) | IsLChild(v)) {
            case 0b00: /* zig-zig */;
            case 0b01: /* zig-zag */;
            case 0b10: /* zag-zig */;
            default:   /* zag-zag */;
        }
        if (!gg) v->parent = NULL;
        else (g == gg->lc) ? gg->attachLc(v) : gg->attachRc(v);
        g->updateHeight(); p->updateHeight(); v->updateHeight();
    }
    if (p = v->parent) {
        if (IsLChild(v)) { // zig
            p->attachLc(v->rc);
            v->attachRc(p);
        } else { // zag
            p->attachRc(v->lc);
            v->attachLc(p);
        }
        p->updateHeight(); v->updateHeight();
    }
    v->parent = NULL; return v; // 伸展完成, v 抵达树根
}

查找

• 与常规 BST::search() 不同，很可能会改变树的拓扑结构， 不再属于静态操作

template<typename T> BinNodePosi<T>& Splay<T>::search(const T &e) {
    BinNodePosi<T> p = BST<T>::search(e);
    _root = p ? splay(p) : _hot ? splay(_hot) : NULL; // 成功、失败、空树
    return _root;
}

插入

• Splay::search() 查找失败后，_hot 即为根
  • 直接在树根附近接入新节点

template<typename T> BinNodePosi<T> Splay<T>::insert(T const &e) {
    if (_root) { _size = 1; return _root = new BinNode<T>(e); }
    BinNodePosi<T> t = search(e);
    if (t->data == e) return t;
    if (t->data < e) {
        _root = new BinNode<T>(e, NULL, t, t->rc);
        t->rc = NULL;
    } else {
        _root = new BinNode<T>(e, NULL, t->lc, t);
        t->lc = NULL;
    }
    _size++; t->updateHeightAbove(); return _root;
} // 无论何时, 总有 _root-> data == e

删除

• 同插入，search() 后可直接在树根附近摘除节点

template<typename T> bool Splay<T>::remove(T const &e) {
    if (!root || e != search(e)->data) return false;
    BinNodePosi<T> L = _root->lc, R = _root->rc;
    delete _root;
    if (!R) {
        if (L) L->parent = NULL;
        _root = L;
    } else {
        _root = R; R->parent = NULL;
        search(e); // 查找必败, 是为了伸展最小节点作为新的根
        _root->attachLc(L);
    }
    _size--; if (_root) _root->updateHeight();
    return true;
}

总结

• 无需记录高度或平衡因子，编程实现简单，分摊复杂度 $O(\log n)$
• 局部性强，缓存命中率极高时（$k \ll n \ll m$）（$k$ 为访问范围）
  • 效率甚至可以更高，自适应的 $O(\log k)$
  • 任何 连续 的 $m$ 次查找，仅需 $O(m\log k + n\log n)$
• 若 反复地顺序 访问任意子集，分摊成本仅为常数
• 不能杜绝 单次最坏 情况，不适用于对效率敏感的场合

分摊分析

势能

• 任何一棵伸展树在任何时刻，都可假想地视作具有势能

  • $\Phi(S) = \log(\prod_{v \in S} size(v)) = \sum_{v \in S} \log(size(v)) = \sum_{v \in S} rank(v) = \sum_{v \in S} \log V$

• 越平衡/倾侧的树，势能越小/大

  • 单链

    $\Phi(S) = \log n! = O(n \log n)$

  • 满树

    $\begin{aligned}\Phi(S) &= \log \prod_{d = 0}^h (2^{h - d + 1} - 1)^{2^d} \le \log \prod_{d = 0}^k 2^{(h - d + 1) \cdot 2^d} \\ &= \sum_{d = 0}^h (h - d + 1) \cdot 2^d = (h + 1) \cdot (2^{h + 1} - 1) - [(h - 1)\cdot 2^{h + 1} + 2] \\ &= 2^{h + 2} - h - 3 = O(n) \end{aligned}$

总体关系推导

• 考察对伸展树 $S$ 的 $m \gg n$ 次连续访问（不妨仅考察 search() ）
• 记 $A^{(k)} = T^{(k)} + \Delta \Phi^{(k)}$ ，其中
  • $T^{(k)}$ ：第 $k$ 次操作的实际时间复杂度
  • $\Delta \Phi^{(k)} = \Phi_{after} - \Phi_{before}$ ：第 $k$ 次操作后势能函数的变化
• 则有 $T = \sum_{k = 1}^m T^{(k)} = \sum_{k = 1}^m (A^{(k)} - \Delta \Phi^{(k)}) = A - \Delta \Phi$
  • 其中 $\left\vert \Delta\Phi \right\vert \le O(n \log n)$
  • 故 $T = A \pm O(n \log n)$
• $T^{(k)}$ 的变化幅度可能很大，但可以证明 $A^{(k)}$ 都不致超过节点 $v$ 的势能变化量
  • $A^{(k)} = O(rank^{(k)}(v) - rank^{(k - 1)}(v)) = O(\log n)$

伸展操作分析

• 单旋到根（zig / zag）

  $\begin{aligned} A^{(k)}_i &= T^{(k)}_i + \Delta\Phi^{(k)}_i = 1 + \Delta rank_i(v) + \Delta rank_i(r) \\ &= 1 + [rank_i(v) - rank_{i - 1}(v)] + [rank_i(r) - rank_{i - 1}(r)] \\ &< 1 + [rank_i(v) - rank_{i - 1}(v)] \end{aligned}$

• 反向双旋（zig-zag / zag-zig），$(\log G_i + \log P_i) / 2\le \log ((G_i + P_i) / 2) < \log (V_i / 2)$

  $\begin{aligned} A^{(k)}_i &= T^{(k)}_i + \Delta\Phi^{(k)}_i = 2 + \Delta rank_i(g) + \Delta rank_i(p) + \Delta rank_i(v) \\ &= 2 + [rank_i(g) - \cancel{rank_{i - 1}(g)}] + [rank_i(p) - rank_{i - 1}(p)] + [\cancel{rank_i(v)} - rank_{i - 1}(v)] \\ &< 2 + rank_i(g) + rank_i(p) - 2 \cdot rank_{i - 1}(v) \\ &< 2 + 2 \cdot rank_i(v) - 2 - 2 \cdot rank_{i - 1}(v) \\ &= 2 \cdot(rank_i(v) - rank_{i - 1}(v)) \end{aligned}$

• 同向双旋（zig-zig / zag-zag），$(\log G_i + \log V_{i - 1}) / 2 \le \log ((G_i + V_{i - 1}) / 2) < \log (V_i / 2)$

  $\begin{aligned} A^{(k)}_i &= T^{(k)}_i + \Delta\Phi^{(k)}_i = 2 + \Delta rank_i(g) + \Delta rank_i(p) + \Delta rank_i(v) \\ &= 2 + [rank_i(g) - \cancel{rank_{i - 1}(g)}] + [rank_i(p) - rank_{i - 1}(p)] + [\cancel{rank_i(v)} - rank_{i - 1}(v)] \\ &< 2 + rank_i(g) + rank_i(p) - 2 \cdot rank_{i - 1}(v) \\ &< 2 + rank_i(g) + rank_i(v) - 2 \cdot rank_{i - 1}(v) \\ &< 2 + 2 \cdot rank_i(v) - rank_{i - 1}(v) - 2 + rank_i(v) - 2 \cdot rank_{i - 1}(v) \\ &= 3 \cdot(rank_i(v) - rank_{i - 1}(v)) \end{aligned}$

• 单次伸展总复杂度为

  $\begin{aligned} A^{(k)} &= \sum_i A^{(k)}_i \le 3 \cdot \sum_i (rank_i(v) - rank_{i - 1}(v)) \\ &= 3 \cdot (rank(root) - rank(v)) \le 3 \cdot \log n = O(\log n) \end{aligned}$

B-树

• 分级存储：利用数据访问的局部性

  • 常用的数据，复制到更高层、更小的存储器中
  • 找不到，才向更低层、更大的存储器索取

• 缓存的体现： 就地 循环位移的倒置版本

  void shift(int *A, int n, int k) {
      reverse(A, k);
      reverse(A + k, n - k);
      reverse(A, n);
  } // O(3n)

结构

• 等价变换：平衡的多路搜索树

  • 每 $d$ 代合并为超级节点
    • $m = 2^d$ 路，$m - 1$ 个关键码
  • 逻辑上与 BBST 完全等价

• IO 优化：多级 存储系统中使用 B-树，可针对外部查找，大大减少 I/O 次数

  • 利用外存的 批量访问，每下降一层，都以超级节点为单位，读入一组关键码
    • 适宜于在相对更小的内存中，实现对大规模数据的高效操作
  • $m = \left\vert page \right\vert / \left\vert key \right\vert$

外部节点+叶子

• $m$ 阶 B-树，即为 $m$ 路完全平衡搜索树（$m \ge 3$）
• 外部节点的深度 统一相等，并以此深度作为树高 $h$
  • 外部节点可看作 “可被插入的空隙”
  • 叶节点的深度统一相等（$h - 1$）

内部节点

• 各含有 $n \le m - 1$ 个关键码
• 各有 $n + 1 \le m$ 个分支
  • 反过来，分支数也不能太少
    • 树根：$2 \le n + 1$
    • 其余：$\lceil m / 2 \rceil \le n + 1 \le m$
  • 故亦称作 $(\lceil m / 2 \rceil, m)$-树

查找

算法

1. 从（常驻 RAM 的）根节点开始
2. 只要当前节点不是外部节点
   • 在当前节点中顺序查找（RAM 内部）
   • 若找到目标关键码，则返回查找成功
   • 否则，沿引用找到孩子节点，将其 读入内存
     • 外部节点不需要 IO
3. 返回查找失败

实现

template<typename T> BTNodePosi<T> BTree<T>::search(T const &e) {
    _hot = NULL;
    for (BTNodePosi<T> v = _root; v; ) {
        Rank r = v->key.search(e); // 在当前节点中, 找到不大于 e 的最大关键码
        // 对通常的_m, 顺序查找效率比二分高
        if (r != -1 && (e == v->key[r])) return v;
        _hot = v; v = v->child[r + 1]; // 沿引用转至对应的孩子节点(I/O)
    }
    return NULL;
}

性能

• 忽略内存中的查找，运行时间主要取决于 I/O 次数
• 在每一深度至多一次 I/O，故运行时间为 $O(\log n)$
• $\log_m (N + 1) \le h \le 1 + \lfloor \log_{\lceil m / 2 \rceil} \frac{N + 1}{2} \rfloor$
  • 树最高的情况
    • 对于内部节点，$n_k \ge 2 \times \lceil m / 2 \rceil ^{k - 1}, \quad \forall k > 0$
    • 考察外部节点所在高度 $h$，$N + 1 = n_h \ge 2 \times \lceil m / 2 \rceil ^{h - 1}$
    • $h \le 1 + \lfloor \log_{\lceil m / 2 \rceil} \frac{N + 1}{2} \rfloor = O(\log_m N)$

插入

template<typename T> bool BTree<T>::insert(const T &e) {
    BTNodePosi<T> v = search(e);
    if (v) return false;
    Rank r = _hot->key.search(e); // 在_hot 节点(叶子)中确定插入位置
    _hot->key.insert(r + 1, e);
    _hot->child.insert(r + 2, NULL); // 创建一个空子树
    _size++; solveOverflow(_hot); // 若上溢, 则分裂
    return true;
}

上溢修复

• 设上溢节点中的关键码依次为 $\{k_0, k_1, \dots, k_{m - 1}\}$
  • 取中位数 $s = \lfloor m / 2 \rfloor$ ，划分为 $\{k_0, \dots, k_{s - 1}\}$ 、$\{k_s\}$ 、$\{k_{s + 1}, \dots, k_{m - 1}\}$
  • 关键码分裂，$k_s$ 上升成为父节点的孩子，其余两部分成为它的左、右孩子
  • 此时左、右孩子的关键码数目，均满足 $m$ 阶 B-树条件
• 若父节点本已饱和，则继续上溢
  • 最坏情况 上溢持续 向上传播到根
    • 此时可令最后被提升的关键码自成节点，作为新的根
    • B-树因此增高
• 总体执行时间正比于分裂次数，$O(h)$
• 上溢也可采用旋转来修复

template<typename T> void BTree<T>::solveOverflow(BTNodePosi<T> v) {
    while (_m <= v->key.size()) {
        Rank s = _m / 2;
        BTNodePosi<T> u = new BTNode<T>();
        for (Rank j = 0; j < _m - s - 1; j++) {
            // 分裂出右侧节点 u
            u->child.insert(j, v->child.remove(s + 1));
            u->key.insert(j, v->key.remove(s + 1));
        }
        u->child.insert[_m - s - 1] = v->child.remove(s + 1); // 此时 v 最靠右的孩子
        if (u->child[0]) {
            for (Rank j = 0; j < _m - s; j++)
                u->child[j]->parent = u;
        }
        BTNodePosi<T> p = v->parent;
        if (!p) {
            _root = p = new BTNode<T>();
            p->child[0] = v, v->parent = p;
        }
        Rank r = 1 + p->key.search(v->key[0]); // p 中指向 u 的节点的指针的秩
        p->key.insert(r, v->key.remove(s));
        p->child.insert(r + 1, u); u->parent = p;
        v = p; // 如有必要继续分裂
    }
}

一棵存有 $N$ 个关键码的 $m$ 阶 B-树插入特定关键码后，引发 $\Theta(\log_m N)$ 次分裂的情况：

• 全树总规模为 $\hat{N} = \lceil m / 2 \rceil^{h - 1} + (m - 1) \cdot (\lceil m / 2 \rceil ^{h - 2} + \lceil m / 2 \rceil^{h-3} + \dots + \lceil m / 2 \rceil^{0})$
  • 对应高度可取为 $\begin{aligned}h = 1 + \log_{\lceil m / 2 \rceil}((\hat{N} \cdot (\lceil m / 2 \rceil - 1) + m - 1) / (m + \lceil m / 2 \rceil - 2)) =\Theta(\log_{\lceil m / 2 \rceil} \hat{N}) = \Theta(\log_{m} \hat{N})\end{aligned}$
  • 对于给定的 $N$，可由代入上式计算出 $h$ 进而估算出 $\hat{N} \le N$（多余的关键码散布至其他子树中）

图示某一黑关键码和对应白关键码构成的 高度 为 $k$ 的子树规模为 $\lceil m / 2 \rceil^k$

删除

• 若被删除元素非叶子，则先通过旋转 腾挪（与后继交换），使其位于最底层

template<typename T> bool BTree<T>::remove(const T &e) {
    BTNodePosi<T> v = search(e);
    if (!v) return false;
    Rank r = v->key.search(e);
    if (v->child[0]) { //非叶子
    	BTNodePosi<T> u = v->child[r + 1]; // 后继在右子树中
        while (u->child[0]) u = u->child[0];
        v->key[r] = u->key[0]; v = u, r = 0; // 交换
    }
    v->key.remove(r); v->child.remove(r + 1);
    _size--; solveUnderflow(); // 下溢, 需做旋转或合并
    return true;
}

下溢修复

• 非根节点 $v$ 下溢时，必恰有 $\lceil m / 2 \rceil - 2$ 个关键码和 $\lceil m / 2 \rceil - 1$ 个分支
  • 若左兄弟 L 存在，且至少包含 $\lceil m / 2 \rceil$ 个关键码（够借）
    • 将 P 中分界关键码 $y$ 移至 V 中（作为最小关键码）
    • 将 L 中最大关键码 $x$ 移至 P 中（取代 $y$）
    • 修复完成
  • 若右兄弟 R 存在，且至少包含 $\lceil m / 2 \rceil$ 个关键码
    • 同上处理
  • 若 L 和 R 或不存在，或均不足 $\lceil m / 2\rceil$ 个关键码
    • 即便如此 L 和 R 必有其一，且恰含有 $\lceil m / 2 \rceil -1$ 个关键码
    • 从 P 中抽出介于 L（R） 和 V 之间的关键码 $y$ ，三者合成一个新的节点，同时合并此前 $y$ 的孩子引用
    • 这可能导致 P 继续下溢，重复整个过程即可

template<typename T> void BTree<T>::solveUnderflow(BTNodePosi<T> v) {
    while ((_m + 1) / 2 > v->child.size()) {
        BTNodePosi<T> p = v->parent;
        if (!p) { /* 已到根节点 */ }
        Rank r = 0; while (p->child[r] != v) r++; // 确定 v 是 p 的第 r 个孩子
        if (r > 0 && (_m + 1) / 2 < p->child[r - 1]->child.size()) {
            /* 情况 1 */
        } else if (r < p->child.size() - 1 && (_m + 1) / 2 < p->child[r + 1]->child.size()) {
            /* 情况 2 */
        } else { /* 情况 3 */
            if (r > 0) { /* 与左兄弟合并 */ }
            else { /* 与右兄弟合并 */ }
        }
        v = p; // 如有必要继续旋转或合并
    }
}

红黑树

动机

• 并发性：对于 BST 而言，结构变化处需要加锁（产生访问延迟）
  • Splay 结构变化剧烈，最差 $O(n)$
  • AVL 插入 $O(1)$ 但删除 $O(\log n)$
• 持久性：支持对历史版本的访问
  • 蛮力保存，单次操作 $O(\log h + \log n)$ ，累计 $O(n \cdot h)$ 时间/空间
  • 压缩更新：大量共享，少量更新（仅支持对历史版本的读取）
    • 每个版本的新增复杂度，仅为 $O(\log n)$
    • 可进一步提高至总体 $O(n + h)$ 、单版本 $O(1)$
      • 为此，就树的 代数结构 而言，相邻版本之间的差异不能超过 $O(1)$

结构

• 红黑树：由红、黑两类节点组成的 BST；统一引入外部节点 NULL，形成 真二叉树。规则如下

  • 树根：必为黑色
  • 外部节点：必为黑色
  • 红节点：只能有黑孩子以及黑父亲
  • 外部节点：黑深度（黑的真祖先数目）相等
    • 亦即根（全树）的黑高度
    • 子树的黑高度，即为后代 NULL 的相对黑深度

• 红黑树 = （2,4）B-树

  • 将红节点提升至与其黑父亲等高，则可对应一棵 $(2, 4)$-树
    • 将黑节点和其红孩子视作关键码，合并为 B-树的超级节点

• 红黑树 $\in$ BBST

  • 设红/黑高度为 R/H，则

    • $H \le h \le H + R \le 2 \cdot H$
    • $H$ 即为对应 B-树 $T_B$ 的树高，而 $T_B$ 中的每个节点都 恰好 包含 一个 $T$ 的黑节点
      • $H \le 1 + \log_{\lceil m / 2 \rceil} \frac{n + 1}{2} = \log_2(n + 1)$

  • 包含 $n$ 个 内部 节点的红黑树，高度 $h = O(\log n)$

    • $\log_2(n + 1) \le h \le 2 \cdot \log_2(n + 1)$

    • 若 $h$ 为偶数，则对应 B-树高度至少为 $h / 2$

      • 至少包含 $N_{\min} = 2 \times (1 + 2 + 4 + \dots + 2^{h / 2 - 1}) = 2^{h / 2 + 1} - 2$ 个节点

        故 $h_{\max} = 2 \times (\lfloor \log_2(N + 2) \rfloor - 1)$

    • 若 $h$ 为奇数，则对应 B-树高度至少为 $(h + 1) / 2$

      • 至少包含 $N_{\min} = 2 \times (1 + 2 + 4 + \dots + 2^{(h - 1) / 2 - 1}) + 2^{(h + 1) / 2 - 1} = 3 \cdot 2^{(h - 1) / 2} - 2$ 个节点

        故 $h_{\max} = 2 \times \lfloor \log_2 (\frac{N + 2}{3}) \rfloor + 1$

  

插入

• 按 BST 规则插入新关键码 $e$
  • 除非是首个节点，否则 $x$ 的父亲 $p$ 必存在
  • 先将 $x$ 染红，条件 1、2、4 依然满足
  • 但可能出现双红，此时考查
    • 祖父 g = p->parent 必存在且为黑
    • 叔父 u = uncle(x) = sibling(p) ，无非两种情况

template<typename T> BinNodePosi<T> RedBlack<T>::insert(const T &e) {
    BinNodePosi<T> &x = search(e);
    if (x) return x;
    // 创建红节点 x, 以_hot 为父, 黑高度 = 0
    x = new BinNode<T>(e, _hot, NULL, NULL, 0); _size++;
    BinNodePosi<T> xOld = x;
    solveDoubleRed(x); return xOld;
}

双红修正

RR-1: u->color = B

• 此时，x、p、g 的四个孩子（可能是外部节点）全黑，且黑高度相同
• 可进行局部“3+4”重构，b 转黑，a 或 c 转红
  • 从 B-树的角度，相当于原三叉节点插入红关键码后，原黑关键码不再居中

RR-2: u->color = R

• 等效于在 B-树中，超级节点发生上溢
• 故可以让 p 和 u 转黑，g 转红
  • 等效于 节点分裂，关键码 g 上升一层
  • 所以可能将双红向上传播
    • 继续如法炮制即可
    • 直至不再双红，或抵达树根（整树黑高度+1）

复杂度

• 重构、染色均只需常数时间
• 故 RedBlack::insert() 仅需 $O(\log n)$ 时间
  • 期间至多 $O(\log n)$ 次重染色、$O(1)$ 次旋转
  • 分摊意义下，重染色次数为 $O(1)$

	旋转	染色	此后
u 为黑	1~2	2	调整随即完成
u 为红	0	3	可能再次双红，但必上升两层

删除

• 首先按 BST 常规算法进行删除 r = removeAt(x, _hot)
  • 实际被摘除的可能是 x 的前驱或者后继
• x 由其孩子 r 接替，此时另一孩子 k 必为 NULL
  • 但实际调整过程中，x 可能逐层上升
  • 故等效地理解为，k 是一棵 黑高度 与 r 相等的子树

• 此时条件 1、2 依然满足，但条件 3、4 未必

  • 其一为红

    • 若 x 为红，则 3、4 自然满足
    • 若 r 为红，则令其与 x 交换颜色 即可

  • 若 x 和 r 均黑，则此时全树黑深度不再统一

    • 等效于 B-树中 x 所属节点发生下溢

    • 在 新树 中，考查 r 的父亲，兄弟

      p = r->parent;
      s = sibling(r);

      无非四种情况，分别处理

template<typename T> bool RedBlack<T>::remove(const T &e) {
    BinNodePosi<T> &x = search(e);
    if (!x) return false;
    BinNodePosi<T> r = removeAt(x, _hot); // 删除_hot 的某孩子, r 指向其接替者
    if (!(--_size)) return true;
    if (!_hot) { // 删除的是根, 直接染黑
        _root->color = RB_BLACK; _root->updateHeight();
        return true;
    }
    if (BlackHeightUpdated(_hot)) return true;
    if (IsRed(r)) {
        r->color = RB_BLACK;
        r->height++; return true;
    }
    solveDoubleBlack(r); return true;
}

双黑修正

BB-1

• s 为黑，且至少有一个红孩子 t
• 进行“3+4”重构，r 保持黑，a、c 染黑，b 继承 p 的原色
  • 在 B-树中，等效于旋转修复下溢（够借）

BB-2R

• s 为黑，且两个孩子均为黑；p 为红
• r 保持黑，s 转红，p 转黑
  • 等效于下溢节点与兄弟节点合并
  • 同时因为 p 左右还有黑关键码，不会导致下溢传播

BB-2B

• s 为黑，且两个孩子均为黑；p 为黑
• r 保持黑，s 转红，p 转黑
  • 也等效于下溢节点与兄弟节点合并
  • 但合并前，p 和 s 均属于单关键码节点，故 父节点继续下溢
    • 继续处理即可，至多 $O(\log n)$ 步

BB-3

• s 为红（其孩子均为黑）
• 绕 p 单旋，s 由红转黑，p 由黑转红
  • 黑高度依然异常，但 r 有了新的（黑）兄弟
  • 且由于 p 转红，接下来的情况变为 BB-1 或 BB-2R
  • 再调整一轮，即可恢复
  • 道理是“存在红色就可以在子树中腾挪”，但需要先调整一下形态
    • 想在红黑树的等效 B-树节点中交换节点颜色（即在 B-树中改变与上层节点的联接），需要进行旋转

复杂度

• RedBlack<T>::remove 仅需 $O(\log n)$ 时间
  • 期间至多 $O(\log n)$ 次重染色、$O(1)$ 次旋转
  • 分摊意义下，重染色次数为 $O(1)$

	旋转	染色	此后
（1）黑 s 有红子 t	1~2	3	调整随即完成
（2R）黑 s 无红子，p 红	0	2	调整随即完成
（2B）黑 s 无红子，p 黑	0	1	必再次双黑，但上升一层
（3）红 s	1	2	转为（1）或（2R）