深入理解红黑树

时间:2021-7-3 作者:qvyue

本文分析 10亿数据量级,只需要30多次就能够查找到目标 的数据结构:红黑树

红黑树 作为 “平衡”搜索树的1种, 可以保证在最坏情况下, 基本动态集合操作的 时间复杂度为 O(h = log2 n)

1. 红黑树概述

1.1 几个要点

  1. 红黑树是1棵 平衡二叉搜索树, 它在每个节点上 增加1个存储位来表示 结点的颜色:红 或 黑

  2. 通过对 任意1条 从根到叶子 的简单路基上 各个结点的颜色 进行约束, 来保证 没有1条路径比其他路径 长到2倍, 因此是近似平衡的

  3. 树中每个结点有 5个属性:key, left, right, p, color

1.2 指针NIL & 哨兵结点T.nil:

  1. NIL

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

  1. T.nil

是1个结点, 称为 哨兵结点 / 叶结点 / 外部结点, 与树中key值有效的 内部结点的区别:
(1) 颜色为黑
(2) key值无效, 可以设为任意值或不设
(3) left / right / p 无效, 可以设为任意值, 即 从 T.nil 发出的3个指针可以忽略

  1. NIL 与 T.nil 的联系

若1个结点没有 左孩子 / 右孩子 / 双亲, 则其相应的指针 left / right / p 的值 设为 NIL 是合理的, 当然, 也可以设为 指向 结点T.nil 的指针

对所有 指针NIL, 可以用 同1个指向 哨兵结点 的指针 来代替

  1. 哨兵结点 T.nil 分成2类: (1)所有 叶结点 (2)根结点 root 的 父结点

  2. 用 T.nil 的好处 : 更便于处理 红黑树代码中的 边界条件

可以将 结点 x 的 NIL 孩子 视为1个普通结点, 其父为 x

通常, 我们把注意力放在 内部结点上, 而忽略 哨兵结点

2. 红黑树性质

结点 x 的 黑高 : 从 x 出发(不含x) 到达 任意1个叶结点任意1条简单路径 上 黑结点的个数, 记为 bh(x)
=> 红黑树的黑高是其 根结点的黑高 bh(root)

1. 每个结点 要么是红色, 要么是黑色
2. 根结点是 黑色
3. 每个叶结点(T.nil)是黑色
4. 红结点的2个子结点都是 黑色

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

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

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

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

思路:把 高 和 黑高 联系起来

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

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

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

  1. 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.right
    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. 插入

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
            x = x.right

    //2. 插入 z到 最初的叶节点位置: 即, 链接 z 和 y
    z.p = y
    if y == T.nil // 树为空
        T.root = z;
    else 
        if 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 与普通二叉搜索树的 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 的情况统一起来, 便于代码处理

// 用 以 v 为根的子树 来替换 以 u 为根的子树
// u 的双亲 变为 v 的双亲, v 变为 u 的双亲的相应孩子
rb_transplant(T, u, v)    // u 可== T.nil, v 可以 == T.nil
    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

    v.p = u.p     

6.2 rb_delete

rb_delete(T, z)
    y = z                           //1.1 y 的变化: z 有  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. 维持 y 为

(1)从树中 要删除的结点z, 当 z 有
(2)要移至树中的结点, 即 z 的后继, 当 z 有 2个孩子时

  1. y_original_color 记录 y变色前的颜色, 因为 y 可能变色;

当 z 有 2个孩子时, y 移至 z原始位置后, y 的颜色变为 z的颜色;

y_original_color 为黑色, 则
(1)删除y( z 有
或(2)移动y( z 有 2个孩子 )
会破坏红黑性, 此时要进行调整

  1. 记录 x 的踪迹, 使 x 移至 y原始位置。

x 指向 y的唯一子结点 或 T.nil

x移至y:
(1)z有
(2)z 有 2个孩子, 即 y 的右孩子 移至 y

  1. 若 y 红 => y(即z) 被删除 或 被移动时, 红黑性质不变, 原因为

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

  1. 归结为2类 删除/移动
1. z有 `x 移至 y`, 相当于 x 移至 z

2. z有2个孩子:
2.1 若 z的后继y 是 z的右孩子, 

(1)z被删除
 `y 移至 z`

2.2 若 z的后继y 不是 z的右孩子

(1)y被删除
 y的右孩子 `x 移至 y`

(2)z被删除
 `y 移至 z`
深入理解红黑树
image.png
深入理解红黑树
image.png

若y 为黑, 则产生3个问题

问题1/2 : 见 上图
性质2的恢复 :while外 最后 x 被涂黑 => 根红 恢复为 根黑
性质4的恢复:红色的 x 被附加了 额外的黑色, 变为 红黑色, 下一次循环会结束, 最后 x 被涂黑 => 连续红被恢复为 红黑

问题3:
删除y 或 移动y(至原z), 则原包含y的任一简单路径上黑结点数少1, y 的 任一祖先不满足性质5: 从每个结点 到其 所有后代叶结点的简单路径上, 黑结点数相同 (包含y 的祖先 到包含y的简单路径上, 和 到不包含y 的简单路径上, 黑结点数相差1

问题3的解决思路:

黑结点 y 删除 或 移动(指 z)时, 将其 黑色 "下推" 给 x, 原来为 红 或 黑 的 x 变为 红黑色 或 双重黑色. 性质5恢复, 但又违反性质1. note: 此时 x.color 仍为原来的 红 或 黑, 额外的 黑色 是针对 x 的, 并不反映在 x 的 color上

所谓的 额外黑 如何实现:
让 恢复红黑性质的函数 的入参 x 指针 始终指向当前具有额外黑的结点, 或者说 用指针 x 来代表额外黑, 通过while循环将 额外黑, 即 x 沿树上移, 直到 x 指向根(对根结点而言, 额外黑 是多余的, 直接认为没有这个额外黑就行) 或者 x 指向的结点的 color 为红( 即 x 为 红黑色 => 直接涂黑就行) 为止, while循环之外, 最后把 x 涂 黑, 以应对 x.color 为红( x 为 红黑)的情况

while 循环内, 保持指针 w 指向 x 的兄弟: 因为 x 是双黑, 所有 w 不可能是 T.nil, 否则 从 x.p 到 x 与 到 w 的简单路径上 黑结点数不相同

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

深入理解红黑树
image.png
深入理解红黑树
image.png
深入理解红黑树
image.png

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
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。