本文分析

10 亿 数据量级, 只需 30 多次就能够 查到目标

的 数据结构: 红黑树

红黑树 最坏情况下, 
基本动态集合操作 时间复杂度

O(h = log2 n)

1 红黑树: 平衡 二叉排序树

1. 几个要点

(1) 每结点
`增加1个存储位 表示 结点颜色: 红或黑`

(2) 通过 `约束` 任意1条 
`从根到叶子 的简单路径上 各结点颜色`, 
来保证 

没有1条路径 比 其他路径 长到 2 倍

=> 平衡 

(3) 每结点 `5个属性: key, left, right, p, color`

2. 指针 NIL & 哨兵结点 T.nil

(1) NIL

1) 是1个指针, 可视为 C语言中的 NULL指针
2) 左孩子/右孩子/双亲 不存在时, 
指针 left / right / p 值设为NIL

(2) T.nil

是1个结点, 称为 

哨兵结点 / 叶结点 / 外部结点

与 ( 有效 ) 内部结点 `区别`:
1) 颜色为黑
2) key 值无效
3) left / right / p 无效, 可设为任意, 
即 `从 T.nil 发出的3个指针可忽略`

(3) NIL 与 T.nil 联系

`若1个结点没有 左孩子 / 右孩子 / 双亲, 
则其 left / right / p` 设为
 `NIL` 或 `指向 T.nil 指针` 均合理

对所有 指针 `NIL`, 可用 `指向 哨兵结点 T.nil 的指针` 代替

(4) `2种 哨兵结点:`

1) 叶结点 
2) root 的 父结点

(5) T.nil 好处 : 
更便于处理 红黑树 code 中 `边界条件`

2 红黑树 性质

结点 x 的 

黑高: 从 x 出发( 不含 x 和 叶 )

到达 `任意1个叶结点` 的 `任意1条简单路径` 上 
黑结点的个数, 记为 bh(x)

=> 红黑树的黑高是其 根结点的黑高 bh(root) 

(1) 结点 要么红, 要么黑

(2) 根 黑
(3) 叶(T.nil) 黑
(4) 红结点 2个子结点 均 黑 => 不能 连着 2 个 红

=> 
从根 (不含根) 到叶 的任意1条简单路径上, 
至少有1半结点为黑色

(5) 每个结点 到其 所有后代 叶结点 的 简单路径上, 黑结点个数相同

=> 

变色 / 旋转前后 黑色层数不变

3 引理 : n 个内部结点的红黑树 高度 至多为 2 log2( n +1 )

思路: 

把 高 和 黑高 联系起来

1. 要证引理, 只要证
高为 h 的红黑树 结点数 n >= 2^(h/2) - 1

2.高为 h => 
黑高 bh(root) >= h / 2 => h/2 <= bh(root)

因为, 从根(不包括根结点) 到叶结点 的任意1条简单路径上, 至少有1半结点为黑色

3. 1&2 => 只要证 n >= 2^bh(root) - 1

只要用 数学归纳法证明: 
以结点 x 为根的子树 至少包含 2^bh(x) - 1 个内部结点

当 x 高度为0时, x 必为叶结点（NULL）且 bh(x)  = 0, 
则以 x 为根的子树至少包含  
2^bh(x) - 1 = 2^0 - 1 = 0 个内部结点;

当 x 高度 >0, 且有 2个子结点时, 
每个子结点的 黑高为 bh(x) 或 bh(x) - 1, 
由归纳假设知, 若每个子结点至少有 2^( bh(x) - 1 ) - 1 个内部结点 
=>
 x 为根的子树至少包含 
2* [ 2^( bh(x) - 1 ) - 1 ] + 1 = 2^bh(x) - 1 
个结点, 证毕

4 旋转: 不考虑颜色

image.png

`alpha / beta / gama 代表任意子树`

记住 左旋 思路

//note: x y 等 实际上是 指向结点的指针, 
// 伪代码中 可以当指针或对象用, 取成员都用

//------左旋
left_rotate(T, x)
    //1. 取 x的右孩子
    y = x.right

    //2. 把 y 的左孩子 作为 x 的右孩子: 
    //(1) 孩子 链到 父
    //(2) 父 链到 孩子
    if y.left != T.nil
        y.left.p = x    //(1) y.left -> x
    x.right = y.left   //(2) x.right -> y.left 

    //3. y 作 原x 父节点的孩子: 要判 原x 是x父节点 的左孩子还是右孩子
    y.p = x.p;
    if x.p == T.nil
        T.root = y
    else if x == x.p.left
        x.p.left = y
    else if x == x.p.right
        x.p.right = y

    //4. x 作 y 的左节点
    x.p = y
    y.left = x

//------右旋 : 根据左旋, 可以很容易对称得到
right_rotate(T, y)
    //1. 取 y的左孩子
     x = y.right

    //2. 把 x的右孩子 作为 y的右孩子: 
    if x.right != T.nil
        x.right.p = y  
    y.right = x.right

    //3. 把 x 作为 原y父节点的孩子
    x.p = y.p
    if y.p == T.nil
        T.root = x
    else if y == y.p.left
        y.p.left = x
    else if y == y.p.right
        y.p.right = x

    //4. 把 y 作为 x的右节点
    y.p = x
    x.right = y

5 插入

记住 4 点

, 即可 心中有 `树`

1. 找 初始插入的 叶节点位置

2. 插入 z

3. 着 `红色`

4. `变色/旋转 ( 前后 黑色层数不变 ): 以保持红黑性质`

    父 黑 -> donothing
    
    插入点 z 循环上移
        `父红 => 祖父 必存在 且 黑`
            `父红 且 为左孩子`
                `父叔 ( 上一层 ) 都红`
                    父/祖父/叔 `3 者 变色` + (红) `z 上移 2 层` ( 继续 循环)
                
                `父红 叔黑`
                    `z/父/祖父 3代 1 条线` -> 父/祖父 `2 者 变色` +  祖父 ( 合适 ) 旋转 (循环结束)
        
                    else: z `上移 1 层` + 父 (合适) 旋转 -> z/父/祖父 3代 1 条线
                    
            父红 且 右: 父红且左 -> 对称得到

具体:

z: 插入节点的指针, z 最终替换了某个 T.nil 的位置

叶结点 nil 的 left == right == NULL, color = Black

image.png image.png

`父红且右: 是 父红且左的对称, 
可由父红且左的图对称画出`

image.png

//插入节点的指针 : z
//设2个指针: x y
//x: 当前遍历节点的指针, 
//   从根开始, 
//   根据 z.key 是否 < 当前遍历节点x.key, 往左或往右走 
//y: 作为 旧x 的指针, 即 新x的父节点的指针
//   从 NULL开始, 一直记录 新x的父节点的指针
rb_insert(T, z)
    x = T.root
    y = T.nil

    //1. 寻找 插入的叶节点位置
    while x != T.nil //循环结束时, x = T.nil, 即 插入的叶节点位置
        y = x;
        if z.key < x.key
            x = x.left
        else // z.key >= x.key
            x = x.right

    //2. 插入 z到 最初的叶节点位置: 即, 链接 z 和 y
    z.p = y
    if y == T.nil // 树为空
        T.root = z;
    else 
        if z.key < y.key
            y.left = z
        else // z.key >= y.key
            y.right = z

    //3. z的左右孩子置nil, 并着为红色
    z.left = T.nil
    z.right = T.nil
    z.color = Red

    //4. 调整 颜色和结构: 为保持红黑性质, 对相关节点重新着色和旋转
    rb_insert_fixup(T, z)

// 叶结点 nil 的 left == right == NULL, color = Black

//z: 插入节点的指针
//   最初指向某个 叶节点/nil : color = Black
//   旋转时, 由于要维持红黑性质, 可能改变位置 而变成内部结点的指针
rb_insert_fixup(T, z)

    // 若父黑, 为
    //(1)黑色内部结点    => 调整函数no-op 
    //或(2)黑色叶结点nil => z为根结点 => 根结点着为黑色

    //父红 => 父 z.p 是内部结点, 且 父必然不是根 
    //        => 祖父z.p.p 必然存在, 且为内部结点
    while z.p.color == Red 
        //1. 父左 : 父为祖父的左孩子
        if z.p == z.p.p.left 
            y = z.p.p.right  // 取出叔y : 必然为祖父的右孩子
            
            //case1: 叔红 , 又 父红 => 祖父 黑
            if y.color == Red
                z.p.color = Black //(1)父变黑
                y.color = Black   //(2)叔变黑
                z.p.p.color = Red //(3)祖父变红: 以保持性质5 <=> 变色/旋转前后 黑色层数不变
                z = z.p.p         //(4)z 上升2层, 作为新的插入节点指针 => 对新z: z.p.cloor 可能为红

            //case2: 叔黑 & z为右孩子 =>转换为 case3
            else if z == z.p.right
                z = z.p           //z上升1层到父结点
                left_rotate(T, z) //父/新z 左旋 : 新z 下降1层, 恢复到来层

            //case3: 叔黑 & z为左孩子
            else if z == z.p.left
                z.p.color = Black      //父变黑   => 下一次循环结束
                z.p.p.color = Red      //祖父变红
                right_rotate(T, z.p.p) //祖父右旋

        //2. 父为祖父的右孩子 : 对照父为祖父的左孩子 对称处理
        else if z.p == z.p.p.right 
            y = z.p.p.left //取出叔
            if y.color == Red
                z.p.color = Black 
                y.color = Black   
                z.p.p.color = Red 
                z = z.p.p        
            else if z == z.p.left
                z = z.p            
                right_rotate(T, z)
            else if z == z.p.left
                z.p.color = Black     
                z.p.p.color = Red     
                left_rotate(T, z.p.p) 
    T.root.color = Black

6 删除

6.1 rb_transplant(T, u, v)

记住 rb_transplant

// 用 以 v 为根的子树 来替换 以 u 为根的子树
// 操作完, 不 care 以 u 为根的子树 
rb_transplant(T, u, v)    // u v 均可 == T.nil
    // (1) 从 u.p -> v
    if u.p == T.nil       // u 为根 root
        T.root = v
    else if u == u.p.left // below: u.p != T.nil <=> u 不为根
        u.p.left = v
    else // if u == u.p.right
        u.p.right = v
    
    // (2) 从 v -> u.p
    v.p = u.p    

rb_transplant 与 普通二叉搜索树的 transplant 的 区别 :

(1) transplant 中的 NIL, 换成了 T.nil
(2) v.p = u.p 无条件指向, 因为 当 v = T.nil 时, 也 能 给 v.p 赋值
(3) `由伪代码看, u 也可以 == T.nil, 因为 对 u.p == T.nil 可以有 T.nil.p = T.nil, 
但除非特殊考虑, 不要给 u 以 T.nil 的入参, 很容易混乱, 待考究`
=>rb_delete 中 必有 u != T.nil

note: 
因为 T.nil 只有1个, 所以, 依次执行 T.nil.p = x1 / x2 / ... / xn 时, 
T.nil.p 最终指向 xn, 
`我们并不care T.nil.p 到底指向哪个结点, 
只是 v.p = u.p 可以把 v == T.nil 和 v != T.nil 统一起来, 
便于代码处理`

6.2 rb_delete

rb_delete(T, z)
    y = z                           //1.1 y 的变化: z 有 <= 1 个孩子时, y 指向 要删除的 z
    y_original_color = y.color      //2.1 y_original_color:y被赋值时, 立即更新
    if z.left == T.nil
        x = z.right                 //3.1 x: z 有 <= 1 个孩子时, x 指向 有的那个孩子 或 T.nil
        rb_transplant(T, z, z.right)
    else if z.right == T.nil        // below: z.left != T.nil
        x = z.left                  //3.2 x: z 有 <= 1 个孩子时, x 指向 有的那个孩子 或 T.nil
        rb_transplant(T, z, z.left)
    else  // z.left != T.nil && z.right != T.nil
        y = tree_minimum(z.right)  //1.2 y : z有2个孩子时, y 指向 z的后继
        y_original_color = y.color //2.2 y_original_color：y被赋值时, 立即更新
        x = y.right                //3.3  x: z有2个孩子时, x 指向 y 的右孩子
        if y.p == z
            x.p = y                //这一步多余 <=> y.right.p = y, 这本来就成立
        else // y.p != z
            rb_transplant(T, y, y.right)
            y.right = z.right      // 链接 y.right <-> z.right
            y.right.p = y
        rb_transplant(T, z, y)
        y.left = z.left            // 链接 y.left(初始指向T.nil) <-> z.left
        y.left.p = y
        y.color = z.color          //4. note: y.color :  z有2个孩子时, 最后要 更新为 z.color, 以使得 y 为红色时, 黑色的z被删除后, 原红黑树的黑高不变(z的颜色给y)
    if y_original_color == BLACK   //2.3 y_original_color: 根据其是否为黑色, 决定 是否恢复红黑性质
        rb_delete_fixup(T, x)      //3.4 x : 恢复红黑性质

rb_delete 与 tree_delete区别：

1. 欲删结点 z

2. y 维持为

(1) z => y ( 最多 ) 只有 1 个 孩子 ( 左 or 右 )

, 当 z 有 <= 1 个孩子
    => `删 y`

(2) z 的后继 => y ( 最多 ) 只有 1 个 右孩子

, 当 z 有 2个孩子
    => `y 移至 原 z -> y 色 变 z 色`

3. y_original_color 记录 y 变色前 的颜色

y_original_color 为黑

时, 
(1) 删除 y
(2) 移动 y 
会 

破坏红黑性 -> 调整

4. x 指向 y 唯一孩子 或 T.nil

`记录 x 踪迹 -> x 移至 原 y`

5. y 红 => y 被 删除 或 移动 时, 红黑性质不变

原因为

(1) 树 黑高不变
(2) 若 y 红 => x 黑, x 移至 y 不会形成2个连续红
(3) 若 y 红 => y 不是根 => 根仍黑

6. 归结为 2类 删除 / 移动

1) z 有 <=1个孩子
    删 z
    <=> 删 y
    <=> `x 移至 y`

2) z 有 2个孩子 => y ( 最多 ) 只有 1 个 右孩子
    y 是 z 右孩子
        (1) 删 z 
        <=> `y 移至 z`

    else
        (1) 删 y
        <=> `x 移至 y`

        (2) 删 z
        <=> `y 移至 z`    

记住/理解 delete / transplant 图

image.png image.png

`7. 删除 /移动 y 后, 恢复红黑性质, 记住思路`

若 y 为黑 (才需 恢复) -> 恢复红黑性质 的 func 入参: 删除后 的 x

1) `原 y 黑 前 后均 红` 
=> 删 y -> 连续红 ( `性质4 破坏` )

2) 原含 y 的任一简单路径上 黑结点数少1 -> 

y 祖先 `性质5 破坏`

解决

1. y 黑色 下推 给 x, 原 红 或 黑 x 变为 红黑色 或 双重黑色

-> 性质4/5恢复, 但又 `破坏性质1` (要么红 要么黑)

note: 
此时 x.color 仍为 原 红 或 黑,

额外黑 是针对 x 的, 并不反映在 x 的 color上

2. 消除 额外黑

`额外黑` 如何 `实现:`

`step1:`

令 指针 x 表示 额外黑

`step2:`

额外黑/x 沿树上移, until x == T.root

(对 root, 额外黑 多余 => while 外 直接涂黑 ) 

或

x.color = 红

( x 红黑 => while 外 直接涂黑 ) 

`step3:`

while 外, x 涂 黑

x = root 变红 ( `性质2被违反` ) 或 x.color = 红`

->

恢复: 涂黑

`step4:`

while 内, 保持 指针 w 指向 x 的兄弟. x 双黑 时 => w not T.nil

, 否则 从 x.p 到 x 与 到 w 不满足性质5

`如下图 肯定时 记不住, 也就不用记了, 理解上述 思路`
需要时 就能画出

image.png image.png image.png

`4种 case下, 如何保证红黑性质5:`
`思路: 从子树到 alpha beita ... 这6个子树之间
黑结点个数 (包括 x 的额外黑) 在变换前后 保持不变, 
由图中变换前后的计算容易得到`

x 为右孩子时, 图对称画出

, 其实 直接对称写出 代码即可

根据上述4中case, 易得 伪代码如下：

rb_delete_fixup(T, x)
    while x != T.root && x.color == BLACK
        if x == x.p.left
            w = x.p.right // 取出 x 的兄弟
            if w.color == RED
                x.p.color = RED
                w.color = BLACK
                left_rotate(T, x.p)
                w = x.p.right
            //below : w.color == BLACK
            if w.left.color == BLACK && w.right.color == BLACK
                w.color = RED
                x = x.p
            else if w.right.color == BLACK // right BLACK && left RED
                w.left.color = BLACK
                w.color = RED
                right_rotate(T, w)
                w = x.p.right
            else // right RED && left RED or BLACK
                w.color = x.p.color
                x.p.color = BLACK
                w.right.color = BLACK
                left_rotate(T, x.p)
                x = T.root
        else // x == x.p.right, 与 x == x.p.left 对称写出即可
            w = x.p.left // 取出 x 的兄弟
            if w.color == RED
                x.p.color = RED
                w.color = BLACK
                right_rotate(T, x.p)
                w = x.p.right
            //below : w.color == BLACK
            if w.left.color == BLACK && w.right.color == BLACK
                w.color = RED
                x = x.p
            else if w.left.color == BLACK // left BLACK && right RED
                w.right.color = BLACK
                w.color = RED
                left_rotate(T, w)
                w = x.p.left
            else // left RED && right RED or BLACK
                w.color = x.p.color
                x.p.color = BLACK
                w.left.color = BLACK
                right_rotate(T, x.p)
                x = T.root
    x.color = BLACK