红黑树

优势

并发性

并发操作的主要时间瓶颈在 lock & unlock 操作，耗时取决于结构变化处数量：

Splay：最坏 $O (n)$
AVL：insert $O (1)$ ，remove $O (lo g n)$
红黑树： $O (1)$

持久性

支持对历史版本的访问。蛮力实现：空间复杂度 $O (nh)$ 能否将空间复杂度控制在 $O (n + h lo g n)$ 内？

结构 & 规则

由红、黑两类节点构成。
树根为黑色
引入外部节点 nullptr，成为真二叉树，外部节点为黑色
红节点只能有黑孩子（和黑父亲）
从同一节点到其每个 nullptr 后代，沿途经过的黑节点一样多，这个数目（不计自身）叫做黑高度 红节点对黑高度没有贡献，直观理解，可以将红节点提升一层，与黑父亲同层：
每颗红黑树唯一对应于一颗 (2,4) - 树（4 阶 B 树）
但是每个(2,4) - 树可能对应多颗红黑树：
- 对于只有 1 个或 3 个关键码的节点，只能唯一对应一种红黑树的节点情况
- 但对于 2 个关键码的节点，可以让其中之一为红另一为黑，若有 $n$ 个 2 关键码节点，则可对应 $2^{n}$ 颗红黑树
! 在三个关键码的超级节点中，黑色节点必须处于中间！

红黑树也是 BBST：也就是说高度 $h = O (lo g n)$ 黑高度记为 $b$ ，即对应的 B 树高度从根触发，在抵达任一 NULL 前，会经过恰好 $b$ 个黑节点，以及 $r \leq b$ 个红节点，因此 $h = b + ma x {r} - 1 < 2 b = O (lo g n)$ 常系数约为 2

插入 & 双红

按 BST 规则插入并染红。若出现双红情况（当前节点和父节点都为红），其祖父必然为黑（插入前必然满足红黑树规则），视祖父的另一个孩子 u 的颜色分别处理，进行双红修复。

双红修复

若 u 为黑，视为 B 树，相当于 x,p,g 超级节点中黑节点不居中，只需旋转后重新染色即可立即完成修复

- 若 u 为红，视为 B 树，相当于 x,p,g,u 超级节点上溢，将 g 上移一层。从红黑树的视角，**不存在旋转**，只需将 g 转红，将 p,u 转黑。染色过程可能向上传递 $O(\log n)$ 次

#### 时间复杂度重构和染色均只需常数时间，故 - 时间复杂度为 $O(\log n)$ - 至多做 $O(\log n)$ 次染色、1-2 次旋转（双旋则 2 次，单旋则 1 次） ![[Pasted image 20260105132110.png]] ### 删除 & 双黑先按 BST 规则进行删除，设 p 的孩子 x 被删除，替代者为 r。 - 若 x 为红色，不会影响树的平衡性，直接返回。 - 若 x 为黑色且其子节点 r 为红色，只需令 r 染色为黑色即可。 - 若 x 和 r 均为黑色，进行**双黑修复** #### 双黑修复根据 p 和 x 的兄弟 s 和它的孩子的染色情况分别处理，总共 4 种情况： - s 为黑，且至少有一个红孩子 t，看作 B 树，相当于 x 超级节点下溢，且有一兄弟有多余关键码。 - 若 p 为红，则 p 超级节点中必存在一个黑关键码 - 若 p 为黑，则必自成一个节点，只需令 s 继承 p 的染色，进行旋转，并将 t 和 p 染黑即可，**修复完成**。