深入理解红黑树
10 亿 数据量级, 只需 30 多次就能够 查到目标
O(h = log2 n)
没有1条路径 比 其他路径 长到 2 倍
2. 指针 NIL & 哨兵结点 T.nil
哨兵结点 / 叶结点 / 外部结点
黑高: 从 x 出发( 不含 x 和 叶 )
(2) 根 黑
(3) 叶(T.nil) 黑
(4) 红结点 2个子结点 均 黑 => 不能 连着 2 个 红
(5) 每个结点 到其 所有后代 叶结点 的 简单路径上, 黑结点个数相同
变色 / 旋转前后 黑色层数不变
把 高 和 黑高 联系起来
记住 左旋 思路
记住 4 点
z: 插入节点的指针, z 最终替换了某个 T.nil 的位置
记住 rb_transplant
1. 欲删结点 z
2. y 维持为
(1) z => y ( 最多 ) 只有 1 个 孩子 ( 左 or 右 )
(2) z 的后继 => y ( 最多 ) 只有 1 个 右孩子
3. y_original_color 记录 y 变色前 的颜色
y_original_color 为黑
破坏红黑性 -> 调整
4. x 指向 y 唯一孩子 或 T.nil
5. y 红 => y 被 删除 或 移动 时, 红黑性质不变
6. 归结为 2类 删除 / 移动
记住/理解 delete / transplant 图
若 y 为黑 (才需 恢复) -> 恢复红黑性质 的 func 入参: 删除后 的 x
1. y 黑色 下推 给 x , 原 红 或 黑 x 变为 红黑色 或 双重黑色
额外黑 是针对 x 的, 并不反映在 x 的 color上
2. 消除 额外黑
令 指针 x 表示 额外黑
额外黑/x 沿树上移 , until x == T.root
或
x.color = 红
while 外, x 涂 黑
while 内, 保持 指针 w 指向 x 的兄弟 . x 双黑 时 => w not T.nil
x 为右孩子时, 图对称画出
