精华内容
下载资源
问答
  • 红黑树插入场景.xmind

    2020-07-23 18:28:00
    红黑树Mind图——红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树是在1972年由Rudolf Bayer发明的,
  • 红黑树插入与删除

    2014-10-11 22:14:25
    主要讲述红黑树插入、查找、删除、并设计了测试程序去测试程序的正确性
  • 下面小编就为大家分享一篇基于红黑树插入操作原理及java实现方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 红黑树插入与删除各种情况,内容更正了之前版本的错误
  • 红黑树插入时的自平衡 红黑树实质上是一棵自平衡的二叉查找树,引入带颜色的节点也是为了方便在进行插入或删除操作时,如果破坏了二叉查找树的平衡性能通过一系列变换保持平衡。 红黑树的性质 每个节点要么是红色,...
  • 实验进行的是对红黑树进行插入操作的实现,主要方法按照《算法导论》中红黑树算法的描述及伪代码进行编码,采用的是c++。代码已经经过测试可用
  • 红黑树插入删除代码,一些关键地方有打注释,比较好理解 删除部分可以配合http://sunblog.72pines.com/rb-tree-erase/看
  • 严蔚敏《数据结构》红黑树插入的实现C代码
  • 中国科学技术大学的算法课程,红黑树插入算法实验报告
  • 红黑树插入删除详解

    万次阅读 多人点赞 2018-07-11 15:54:05
    红黑树插入删除操作的介绍转载自:红黑树 练习题转载自:红黑树练习 R-B Tree简介  R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,...

    红黑树插入删除操作的介绍转载自:红黑树

    练习题转载自:红黑树练习

    R-B Tree简介

        R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

    红黑树的特性:
    (1)每个节点或者是黑色,或者是红色。
    (2)根节点是黑色。
    (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
    (4)如果一个节点是红色的,则它的子节点必须是黑色的。
    (5)从一个节点到该节点的子孙外部节点的所有路径上包含相同数目的黑节点。

    注意
    (01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
    (02) 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

    红黑树示意图如下:

     

    红黑树的应用

    红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。
    例如,Java集合中的TreeSetTreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。

     

    红黑树的时间复杂度和相关证明

    红黑树的时间复杂度为: O(logn)
    下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

    定理:一棵含有n个节点的红黑树的高度至多为2log(n+1).

    证明:
        "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 转换一下就是 "高度为h的红黑树,它的包含的内节点个数至少为 2^(h/2)-1个"。
        我们只需要证明后面那个命题,即可证明原命题为真;即只需证明 "高度为h的红黑树,它的包含的内节点个数至少为 2^(h/2)-1个"

        从某个节点x出发(不包括该节点)到达一个它子孙外部节点的任意一条路径上,黑色节点的个数称为该节点的黑高度(x's black height),记为bh(x)。关于bh(x)有两点需要说明: 
        第1点:根据红黑树的"特性(5) ,即从一个节点到该节点的子孙外部节点的所有路径上包含相同数目的黑节点"可知,从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着,bh(x)的值是唯一的
        第2点:根据红黑色的"特性(4),即如果一个节点是红色的,则它的子节点必须是黑色的"可知,从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点,则可以得出结论"bh(x) >= h/2"。进而,我们只需证明 "高度为h的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"即可。

        到这里,我们将需要证明的定理已经由
    "一棵含有n个节点的红黑树的高度至多为2log(n+1)"
        转变成只需要证明
    "高度为h以x为根的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"。


    下面通过"数学归纳法"开始论证高度为h以x为根的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"。

    (01) 当树的高度h=0时,
        内节点个数是0,bh(x) 为0,2^bh(x)-1 也为 0。显然,原命题成立。

    (02) 考虑x的左右子节点,它们包含的节点个数至少为 2^(bh(x)-1)-1。推导理由如下:
        
    对于节点x(x为根节点),其黑高度为bh(x)。
        对于节点x的左右子树,当它们为红色时,黑高度为 bh(x);当它们为黑色时,黑高度为bh(x)-1。
        因此,x的左右子节点所包含的节点个数至少为2^(bh(x)-1)-1(因为黑高度最少为bh(x)-1)

    (03) 根据(02),我们已知 "x的左右子树,即高度为 h-1 的节点,它包含的节点至少为 2^(bh(x)-1)-1 个";

        所以,节点x所包含的节点至少为 (2^(bh(x)-1)-1 ) + (2^(bh(x)-1)-1) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2^bh(x)-1。
        因此,原命题成立。

        由(01)、(02)得出,"高度为h的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"。
        因此,“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

    红黑树与AVL树的差别

    AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多;
    红黑是弱平衡的,用非严格的平衡来换取增删节点时候旋转次数的降低;
    所以简单说,搜索的次数远远大于插入和删除,那么选择AVL树,如果搜索,插入删除次数几乎差不多,应该选择RB树。

    比如,下图是一个红黑树,但不是AVL树。

    红黑树的基本操作(一) 左旋和右旋

    红黑树的基本操作是添加删除。在对红黑树进行添加或删除之后,都会用到旋转方法。为什么呢?道理很简单,添加或删除红黑树中的节点之后,红黑树就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转,可以使这颗树重新成为红黑树。简单点说,旋转的目的是让树保持红黑树的特性。
    旋转包括两种:左旋右旋。下面分别对它们进行介绍。

     

    1. 左旋

    对x进行左旋,意味着"将x变成一个左节点"。


    左旋的伪代码《算法导论》:参考上面的示意图和下面的伪代码,理解“红黑树T的节点x进行左旋”是如何进行的。

    LEFT-ROTATE(T, x)  
    01  y ← right[x]            // 前提:这里假设x的右孩子为y。下面开始正式操作
    02  right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”,即 将β设为x的右孩子
    03  p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”,即 将β的父亲设为x
    04  p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
    05  if p[x] = nil[T]       
    06  then root[T] ← y                 // 情况1:如果 “x的父亲” 是空节点,则将y设为根节点
    07  else if x = left[p[x]]  
    08            then left[p[x]] ← y    // 情况2:如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
    09            else right[p[x]] ← y   // 情况3:(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
    10  left[y] ← x             // 将 “x” 设为 “y的左孩子”
    11  p[x] ← y                // 将 “x的父节点” 设为 “y”

     

    理解左旋之后,看看下面一个更鲜明的例子。你可以先不看右边的结果,自己尝试一下。

     

    2. 右旋

    对x进行左旋,意味着"将x变成一个左节点"。


    右旋的伪代码《算法导论》:参考上面的示意图和下面的伪代码,理解“红黑树T的节点y进行右旋”是如何进行的。 

    RIGHT-ROTATE(T, y)  
    01  x ← left[y]             // 前提:这里假设y的左孩子为x。下面开始正式操作
    02  left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”,即 将β设为y的左孩子
    03  p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”,即 将β的父亲设为y
    04  p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
    05  if p[y] = nil[T]       
    06  then root[T] ← x                 // 情况1:如果 “y的父亲” 是空节点,则将x设为根节点
    07  else if y = right[p[y]]  
    08            then right[p[y]] ← x   // 情况2:如果 y是它父节点的右孩子,则将x设为“y的父节点的左孩子”
    09            else left[p[y]] ← x    // 情况3:(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
    10  right[x] ← y            // 将 “y” 设为 “x的右孩子”
    11  p[y] ← x                // 将 “y的父节点” 设为 “x”

     

    理解右旋之后,看看下面一个更鲜明的例子。你可以先不看右边的结果,自己尝试一下。


    旋转总结

    (01) 左旋 和 右旋 是相对的两个概念,原理类似。理解一个也就理解了另一个。

    (02) 下面谈谈如何区分 左旋 和 右旋。
    在实际应用中,若没有彻底理解 左旋 和 右旋,可能会将它们混淆。下面谈谈我对如何区分 左旋 和 右旋 的理解。

     

    3. 区分 左旋 和 右旋

    仔细观察上面"左旋"和"右旋"的示意图。我们能清晰的发现,它们是对称的。无论是左旋还是右旋,被旋转的树,在旋转前是二叉查找树,并且旋转之后仍然是一颗二叉查找树。

     

     

    左旋示例图(以x为节点进行左旋):

                                   z
       x                          /                  
      / \      --(左旋)-->       x
     y   z                      /
                               y

    对x进行左旋,意味着,将“x的右孩子”设为“x的父亲节点”;即,将 x变成了一个左节点(x成了为z的左孩子)!。 因此,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”


    右旋示例图(以x为节点进行右旋):

                                   y
       x                            \                 
      / \      --(右旋)-->           x
     y   z                            \
                                       z

    对x进行右旋,意味着,将“x的左孩子”设为“x的父亲节点”;即,将 x变成了一个右节点(x成了为y的右孩子)! 因此,右旋中的“右”,意味着“被旋转的节点将变成一个右节点”

     

    红黑树的基本操作(二) 添加

    将一个节点插入到红黑树中,需要执行哪些步骤呢?首先,将红黑树当作一颗二叉查找树,将节点插入;然后,将节点着色为红色;最后,通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。详细描述如下:

    第一步: 将红黑树当作一颗二叉查找树,将节点插入。
           红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。
           好吧?那接下来,我们就来想方设法的旋转以及重新着色,使这颗树重新成为红黑树!

    第二步:将插入的节点着色为"红色"。
           为什么着色成红色,而不是黑色呢?为什么呢?在回答之前,我们需要重新温习一下红黑树的特性:
    (1) 每个节点或者是黑色,或者是红色。
    (2) 根节点是黑色。
    (3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
    (4) 如果一个节点是红色的,则它的子节点必须是黑色的。
    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
           将插入的节点着色为红色,不会违背"特性(5)"!少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。o(∩∩)o...哈哈

    第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。
           第二步中,将插入节点着色为"红色"之后,不会违背"特性(5)"。那它到底会违背哪些特性呢?
           对于"特性(1)",显然不会违背了。因为我们已经将它涂成红色了。
           对于"特性(2)",显然也不会违背。在第一步中,我们是将红黑树当作二叉查找树,然后执行的插入操作。而根据二叉查找数的特点,插入操作不会改变根节点。所以,根节点仍然是黑色。
           对于"特性(3)",显然不会违背了。这里的叶子节点是指的空叶子节点,插入非空节点并不会对它们造成影响。
           对于"特性(4)",是有可能违背的!
           那接下来,想办法使之"满足特性(4)",就可以将树重新构造成红黑树了。

    下面看看代码到底是怎样实现这三步的。

     

    添加操作的伪代码《算法导论》

    RB-INSERT(T, z)  
    01  y ← nil[T]                        // 新建节点“y”,将y设为空节点。
    02  x ← root[T]                       // 设“红黑树T”的根节点为“x”
    03  while x ≠ nil[T]                  // 找出要插入的节点“z”在二叉树T中的位置“y”
    04      do y ← x                      
    05         if key[z] < key[x]  
    06            then x ← left[x]  
    07            else x ← right[x]  
    08  p[z] ← y                          // 设置 “z的父亲” 为 “y”
    09  if y = nil[T]                     
    10     then root[T] ← z               // 情况1:若y是空节点,则将z设为根
    11     else if key[z] < key[y]        
    12             then left[y] ← z       // 情况2:若“z所包含的值” < “y所包含的值”,则将z设为“y的左孩子”
    13             else right[y] ← z      // 情况3:(“z所包含的值” >= “y所包含的值”)将z设为“y的右孩子” 
    14  left[z] ← nil[T]                  // z的左孩子设为空
    15  right[z] ← nil[T]                 // z的右孩子设为空。至此,已经完成将“节点z插入到二叉树”中了。
    16  color[z] ← RED                    // 将z着色为“红色”
    17  RB-INSERT-FIXUP(T, z)             // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转,让树T仍然是一颗红黑树

     

    结合伪代码以及为代码上面的说明,先理解RB-INSERT。理解了RB-INSERT之后,我们接着对 RB-INSERT-FIXUP的伪代码进行说明。

    添加修正操作的伪代码《算法导论》

    RB-INSERT-FIXUP(T, z)
    01 while color[p[z]] = RED                                                  // 若“当前节点(z)的父节点是红色”,则进行以下处理。
    02     do if p[z] = left[p[p[z]]]                                           // 若“z的父节点”是“z的祖父节点的左孩子”,则进行以下处理。
    03           then y ← right[p[p[z]]]                                        // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)”
    04                if color[y] = RED                                         // Case 1条件:叔叔是红色
    05                   then color[p[z]] ← BLACK                    ▹ Case 1   //  (01) 将“父节点”设为黑色。
    06                        color[y] ← BLACK                       ▹ Case 1   //  (02) 将“叔叔节点”设为黑色。
    07                        color[p[p[z]]] ← RED                   ▹ Case 1   //  (03) 将“祖父节点”设为“红色”。
    08                        z ← p[p[z]]                            ▹ Case 1   //  (04) 将“祖父节点”设为“当前节点”(红色节点)
    09                   else if z = right[p[z]]                                // Case 2条件:叔叔是黑色,且当前节点是右孩子
    10                           then z ← p[z]                       ▹ Case 2   //  (01) 将“父节点”作为“新的当前节点”。
    11                                LEFT-ROTATE(T, z)              ▹ Case 2   //  (02) 以“新的当前节点”为支点进行左旋。
    12                           color[p[z]] ← BLACK                 ▹ Case 3   // Case 3条件:叔叔是黑色,且当前节点是左孩子。(01) 将“父节点”设为“黑色”。
    13                           color[p[p[z]]] ← RED                ▹ Case 3   //  (02) 将“祖父节点”设为“红色”。
    14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3   //  (03) 以“祖父节点”为支点进行右旋。
    15        else (same as then clause with "right" and "left" exchanged)      // 若“z的父节点”是“z的祖父节点的右孩子”,将上面的操作中“right”和“left”交换位置,然后依次执行。
    16 color[root[T]] ← BLACK 

     

    根据被插入节点的父节点的情况,可以将"当节点z被着色为红色节点,并插入二叉树"划分为三种情况来处理。
    ① 情况说明:被插入的节点是根节点。
        处理方法:直接把此节点涂为黑色。
    ② 情况说明:被插入的节点的父节点是黑色。
        处理方法:什么也不需要做。节点被插入后,仍然是红黑树。
    ③ 情况说明:被插入的节点的父节点是红色。
        处理方法:那么,该情况与红黑树的“特性(5)”相冲突。这种情况下,被插入节点是一定存在非空祖父节点的;进一步的讲,被插入节点也一定存在叔叔节点(即使叔叔节点为空,我们也视之为存在,空节点本身就是黑色节点)。理解这点之后,我们依据"叔叔节点的情况",将这种情况进一步划分为3种情况(Case)。

     现象说明处理策略
    Case 1当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。

    (01) 将“父节点”设为黑色。
    (02) 将“叔叔节点”设为黑色。
    (03) 将“祖父节点”设为“红色”。
    (04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

    Case 2当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子

    (01) 将“父节点”作为“新的当前节点”。
    (02) 以“新的当前节点”为支点进行左旋。

    Case 3当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子

    (01) 将“父节点”设为“黑色”。
    (02) 将“祖父节点”设为“红色”。
    (03) 以“祖父节点”为支点进行右旋。

    上面三种情况(Case)处理问题的核心思路都是:将红色的节点移到根节点;然后,将根节点设为黑色。下面对它们详细进行介绍。

     

    1. (Case 1)叔叔是红色

    1.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。

    1.2 处理策略
    (01) 将“父节点”设为黑色。
    (02) 将“叔叔节点”设为黑色。
    (03) 将“祖父节点”设为“红色”。
    (04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

        下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
        “当前节点”和“父节点”都是红色,违背“特性(4)”。所以,将“父节点”设置“黑色”以解决这个问题。
        但是,将“父节点”由“红色”变成“黑色”之后,违背了“特性(5)”:因为,包含“父节点”的分支的黑色节点的总数增加了1。  解决这个问题的办法是:将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”。关于这里,说明几点:第一,为什么“祖父节点”之前是黑色?这个应该很容易想明白,因为在变换操作之前,该树是红黑树,“父节点”是红色,那么“祖父节点”一定是黑色。 第二,为什么将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”;能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”,既然这样,我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题; 但是,这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”,现在我们已知“叔叔节点”是“红色”,将“叔叔节点”设为“黑色”就能解决这个问题。 所以,将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”;就解决了该问题。
        按照上面的步骤处理之后:当前节点、父节点、叔叔节点之间都不会违背红黑树特性,但祖父节点却不一定。若此时,祖父节点是根节点,直接将祖父节点设为“黑色”,那就完全解决这个问题了;若祖父节点不是根节点,那我们需要将“祖父节点”设为“新的当前节点”,接着对“新的当前节点”进行分析。

    1.3 示意图(图120节点应该为黑色,140为红色。但是不影响这种情况。c表示当前节点)

     

    2. (Case 2)叔叔是黑色,且当前节点是右孩子

    2.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子

    2.2 处理策略
    (01) 将“父节点”作为“新的当前节点”。
    (02) 以“新的当前节点”为支点进行左旋。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          首先,将“父节点”作为“新的当前节点”;接着,以“新的当前节点”为支点进行左旋。 为了便于理解,我们先说明第(02)步,再说明第(01)步;为了便于说明,我们设置“父节点”的代号为F(Father),“当前节点”的代号为S(Son)。
    为什么要“以F为支点进行左旋”呢?根据已知条件可知:S是F的右孩子。而之前我们说过,我们处理红黑树的核心思想:将红色的节点移到根节点;然后,将根节点设为黑色。既然是“将红色的节点移到根节点”,那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)。 而S又是一个右孩子,因此,我们可以通过“左旋”来将S上移!
          按照上面的步骤(以F为支点进行左旋)处理之后:若S变成了根节点,那么直接将其设为“黑色”,就完全解决问题了;若S不是根节点,那我们需要执行步骤(01),即“将F设为‘新的当前节点’”。那为什么不继续以S为新的当前节点继续处理,而需要以F为新的当前节点来进行处理呢?这是因为“左旋”之后,F变成了S的“子节点”,即S变成了F的父节点;而我们处理问题的时候,需要从下至上(由叶到根)方向进行处理;也就是说,必须先解决“孩子”的问题,再解决“父亲”的问题;所以,我们执行步骤(01):将“父节点”作为“新的当前节点”。

    2.2 示意图(图有错,120为黑色,140为红色,c为当前节点)

     

    3. (Case 3)叔叔是黑色,且当前节点是左孩子

    3.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子

    3.2 处理策略
    (01) 将“父节点”设为“黑色”。
    (02) 将“祖父节点”设为“红色”。
    (03) 以“祖父节点”为支点进行右旋。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          为了便于说明,我们设置“当前节点”为S(Original Son),“兄弟节点”为B(Brother),“叔叔节点”为U(Uncle),“父节点”为F(Father),祖父节点为G(Grand-Father)。
          S和F都是红色,违背了红黑树的“特性(4)”,我们可以将F由“红色”变为“黑色”,就解决了“违背‘特性(4)’”的问题;但却引起了其它问题:违背特性(5),因为将F由红色改为黑色之后,所有经过F的分支的黑色节点的个数增加了1。那我们如何解决“所有经过F的分支的黑色节点的个数增加了1”的问题呢? 我们可以通过“将G由黑色变成红色”,同时“以G为支点进行右旋”来解决。

    2.3 示意图(图有错,120为黑色,140为红色,c为当前节点)

    原文的评论区有一个关于红黑树插入很精辟的总结:

    case1
    是为了一层一层向上递归 递归到根节点 直接黑掉根节点的红色

    case2
    这种情况不好处理,或者说仅仅为了从左到右的习惯,把这个棘手的右孩 子转为左孩子处理(可以这么理解、虽然这样不对)这样的结果就是变成了case3

    case3
    默认添加之前该树就是红黑树,这么一处理就对了,不需要再处理。循环到此结束!

    综上所述针对添加操作怎么复原红黑树?
    第一种情况:递归到根节点、直接黑掉根节点
    第二种情况:这种情况不处理,直接转成第三种情况
    第三种情况:一次到位。

    红黑树的基本操作(三) 删除

    将红黑树内的某一个节点删除。需要执行的操作依次是:首先,将红黑树当作一颗二叉查找树,将该节点从二叉查找树中删除;然后,通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。详细描述如下:

    第一步:将红黑树当作一颗二叉查找树,将节点删除。
           这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况:
           ① 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。
           ② 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。
           ③ 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。在这里,后继节点相当于替身,在将后继节点的内容复制给"被删除节点"之后,再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了,下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空,就意味着"该节点的后继节点"要么没有儿子,要么只有一个儿子。若没有儿子,则按"情况① "进行处理;若只有一个儿子,则按"情况② "进行处理。

    第二步:通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。
           因为"第一步"中删除节点之后,可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树,使之重新成为一棵红黑树。

     

    删除操作的伪代码《算法导论》

    RB-DELETE(T, z)
    01 if left[z] = nil[T] or right[z] = nil[T]         
    02    then y ← z                                  // 若“z的左孩子” 或 “z的右孩子”为空,则将“z”赋值给 “y”;
    03    else y ← TREE-SUCCESSOR(z)                  // 否则,将“z的后继节点”赋值给 “y”。
    04 if left[y] ≠ nil[T]
    05    then x ← left[y]                            // 若“y的左孩子” 不为空,则将“y的左孩子” 赋值给 “x”;
    06    else x ← right[y]                           // 否则,“y的右孩子” 赋值给 “x”。
    07 p[x] ← p[y]                                    // 将“y的父节点” 设置为 “x的父节点”
    08 if p[y] = nil[T]                               
    09    then root[T] ← x                            // 情况1:若“y的父节点” 为空,则设置“x” 为 “根节点”。
    10    else if y = left[p[y]]                    
    11            then left[p[y]] ← x                 // 情况2:若“y是它父节点的左孩子”,则设置“x” 为 “y的父节点的左孩子”
    12            else right[p[y]] ← x                // 情况3:若“y是它父节点的右孩子”,则设置“x” 为 “y的父节点的右孩子”
    13 if y ≠ z                                    
    14    then key[z] ← key[y]                        // 若“y的值” 赋值给 “z”。注意:这里只拷贝z的值给y,而没有拷贝z的颜色!!!
    15         copy y's satellite data into z         
    16 if color[y] = BLACK                            
    17    then RB-DELETE-FIXUP(T, x)                  // 若“y为黑节点”,则调用
    18 return y 

     

    结合伪代码以及为代码上面的说明,先理解RB-DELETE,y是被删除的节点,x是替代y的节点。理解了RB-DELETE之后,接着对 RB-DELETE-FIXUP的伪代码进行说明

    RB-DELETE-FIXUP(T, x)
    01 while x ≠ root[T] and color[x] = BLACK  
    02     do if x = left[p[x]]      
    03           then w ← right[p[x]]                                             // 若 “x”是“它父节点的左孩子”,则设置 “w”为“x的叔叔”(即x为它父节点的右孩子)                                          
    04                if color[w] = RED                                           // Case 1: x是“黑+黑”节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
    05                   then color[w] ← BLACK                        ▹  Case 1   //   (01) 将x的兄弟节点设为“黑色”。
    06                        color[p[x]] ← RED                       ▹  Case 1   //   (02) 将x的父节点设为“红色”。
    07                        LEFT-ROTATE(T, p[x])                    ▹  Case 1   //   (03) 对x的父节点进行左旋。
    08                        w ← right[p[x]]                         ▹  Case 1   //   (04) 左旋后,重新设置x的兄弟节点。
    09                if color[left[w]] = BLACK and color[right[w]] = BLACK       // Case 2: x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。
    10                   then color[w] ← RED                          ▹  Case 2   //   (01) 将x的兄弟节点设为“红色”。
    11                        x ←  p[x]                               ▹  Case 2   //   (02) 设置“x的父节点”为“新的x节点”。
    12                   else if color[right[w]] = BLACK                          // Case 3: x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。
    13                           then color[left[w]] ← BLACK          ▹  Case 3   //   (01) 将x兄弟节点的左孩子设为“黑色”。
    14                                color[w] ← RED                  ▹  Case 3   //   (02) 将x兄弟节点设为“红色”。
    15                                RIGHT-ROTATE(T, w)              ▹  Case 3   //   (03) 对x的兄弟节点进行右旋。
    16                                w ← right[p[x]]                 ▹  Case 3   //   (04) 右旋后,重新设置x的兄弟节点。
    17                         color[w] ← color[p[x]]                 ▹  Case 4   // Case 4: x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的。(01) 将x父节点颜色 赋值给 x的兄弟节点。
    18                         color[p[x]] ← BLACK                    ▹  Case 4   //   (02) 将x父节点设为“黑色”。
    19                         color[right[w]] ← BLACK                ▹  Case 4   //   (03) 将x兄弟节点的右子节设为“黑色”。
    20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4   //   (04) 对x的父节点进行左旋。
    21                         x ← root[T]                            ▹  Case 4   //   (05) 设置“x”为“根节点”。
    22        else (same as then clause with "right" and "left" exchanged)        // 若 “x”是“它父节点的右孩子”,将上面的操作中“right”和“left”交换位置,然后依次执行。
    23 color[x] ← BLACK   

     

    下面对删除函数进行分析。在分析之前,我们再次温习一下红黑树的几个特性:
    (1) 每个节点或者是黑色,或者是红色。
    (2) 根节点是黑色。
    (3) 每个外部叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
    (4) 如果一个节点是红色的,则它的子节点必须是黑色的。
    (5) 从一个节点到该节点的子孙外部节点的所有路径上包含相同数目的黑节点。


          前面我们将"删除红黑树中的节点"大致分为两步,在第一步中"将红黑树当作一颗二叉查找树,将节点删除"后,可能违反"特性(2)、(4)、(5)"三个特性。第二步需要解决上面的三个问题,进而保持红黑树的全部特性。
          为了便于分析,我们假设"x包含一个额外的黑色"(x原本的颜色还存在),这样就不会违反"特性(5)"。为什么呢?
          通过RB-DELETE算法,我们知道:删除节点y之后,x占据了原来节点y的位置。 既然删除y(y是黑色),意味着减少一个黑色节点;那么,再在该位置上增加一个黑色即可。这样,当我们假设"x包含一个额外的黑色",就正好弥补了"删除y所丢失的黑色节点",也就不会违反"特性(5)"。 因此,假设"x包含一个额外的黑色"(x原本的颜色还存在),这样就不会违反"特性(5)"。
          现在,x不仅包含它原本的颜色属性,x还包含一个额外的黑色。即x的颜色属性是"红+黑"或"黑+黑",它违反了"特性(1)"。

          现在,我们面临的问题,由解决"违反了特性(2)、(4)、(5)三个特性"转换成了"解决违反特性(1)、(2)、(4)三个特性"。RB-DELETE-FIXUP需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是:将x所包含的额外的黑色不断沿树上移(向根方向移动),直到出现下面的姿态:
    a) x指向一个"红+黑"节点。此时,将x设为一个"黑"节点即可。
    b) x指向根。此时,将x设为一个"黑"节点即可。
    c) 非前面两种姿态。

    将上面的姿态,可以概括为3种情况。
    ① 情况说明:x是“红+黑”节点。
        处理方法:直接把x设为黑色,结束。此时红黑树性质全部恢复。
    ② 情况说明:x是“黑+黑”节点,且x是根。
        处理方法:什么都不做,结束。此时红黑树性质全部恢复。
    ③ 情况说明:x是“黑+黑”节点,且x不是根。
        处理方法:这种情况又可以划分为4种子情况。这4种子情况如下表所示:

     现象说明处理策略
    Case 1x是"黑+黑"节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。

    (01) 将x的兄弟节点设为“黑色”。
    (02) 将x的父节点设为“红色”。
    (03) 对x的父节点进行左旋。
    (04) 左旋后,重新设置x的兄弟节点。

    Case 2x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。

    (01) 将x的兄弟节点设为“红色”。
    (02) 设置“x的父节点”为“新的x节点”。

    Case 3x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。(其实这里要区分,x是父节点的左子树还是右子树,x是左子树则按这里的规则处理;若x是右子树,则左变右,右变左)

    (01) 将x兄弟节点的左孩子设为“黑色”。
    (02) 将x兄弟节点设为“红色”。
    (03) 对x的兄弟节点进行右旋。
    (04) 右旋后,重新设置x的兄弟节点。

    Case 4x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色。(同上)

    (01) 将x父节点颜色 赋值给 x的兄弟节点。
    (02) 将x父节点设为“黑色”。
    (03) 将x兄弟节点的右子节设为“黑色”。
    (04) 对x的父节点进行左旋。
    (05) 设置“x”为“根节点”。

     

    1. (Case 1)x是"黑+黑"节点,x的兄弟节点是红色

    1.1 现象说明
    x是"黑+黑"节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。

    1.2 处理策略
    (01) 将x的兄弟节点设为“黑色”。
    (02) 将x的父节点设为“红色”。
    (03) 对x的父节点进行左旋。
    (04) 左旋后,重新设置x的兄弟节点。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”,从而进行进一步的处理。对x的父节点进行左旋;左旋后,为了保持红黑树特性,就需要在左旋前“将x的兄弟节点设为黑色”,同时“将x的父节点设为红色”;左旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。

    1.3 示意图(图有错,右边D是黑色,B是红色)

     

    2. (Case 2) x是"黑+黑"节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色

    2.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。

    2.2 处理策略
    (01) 将x的兄弟节点设为“红色”。
    (02) 设置“x的父节点”为“新的x节点”。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          这个情况的处理思想:是将“x中多余的一个黑色属性上移(往根方向移动)”。 x是“黑+黑”节点,我们将x由“黑+黑”节点 变成 “黑”节点,多余的一个“黑”属性移到x的父节点中,即x的父节点多出了一个黑属性(若x的父节点原先是“黑”,则此时变成了“黑+黑”;若x的父节点原先时“红”,则此时变成了“红+黑”)。 此时,需要注意的是:所有经过x的分支中黑节点个数没变化;但是,所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)!为了解决这个问题,我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可,那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
          经过上面的步骤(将x的兄弟节点设为红色),多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”,直接将“新的x节点”设为黑色,即可完全解决该问题;若“新的x节点”是“黑+黑”,则需要对“新的x节点”进行进一步处理。

    2.3 示意图(B的颜色可以是红+黑,也可以是黑+黑)

     

    3. (Case 3)x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的

    3.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。

    3.2 处理策略
    (01) 将x兄弟节点的左孩子设为“黑色”。
    (02) 将x兄弟节点设为“红色”。
    (03) 对x的兄弟节点进行右旋。
    (04) 右旋后,重新设置x的兄弟节点。

           下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
           我们处理“Case 3”的目的是为了将“Case 3”进行转换,转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋;为了保证右旋后,它仍然是红黑树,就需要在右旋前“将x的兄弟节点的左孩子设为黑色”,同时“将x的兄弟节点设为红色”;右旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。

    3.3 示意图

     

    4. (Case 4)x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色

    4.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色。

    4.2 处理策略
    (01) 将x父节点颜色 赋值给 x的兄弟节点。
    (02) 将x父节点设为“黑色”。
    (03) 将x兄弟节点的右子节设为“黑色”。
    (04) 对x的父节点进行左旋。
    (05) 设置“x”为“根节点”。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          我们处理“Case 4”的目的是:去掉x中额外的黑色,将x变成单独的黑色。处理的方式是“:进行颜色修改,然后对x的父节点进行左旋。下面,我们来分析是如何实现的。
          为了便于说明,我们设置“当前节点”为S(Original Son),“兄弟节点”为B(Brother),“兄弟节点的左孩子”为BLS(Brother's Left Son),“兄弟节点的右孩子”为BRS(Brother's Right Son),“父节点”为F(Father)。
          我们要对F进行左旋。但在左旋前,我们需要调换F和B的颜色,并设置BRS为黑色。为什么需要这里处理呢?因为左旋后,F和BLS是父子关系,而我们已知BL是红色,如果F是红色,则违背了“特性(4)”;为了解决这一问题,我们将“F设置为黑色”。 但是,F设置为黑色之后,为了保证满足“特性(5)”,即为了保证左旋之后:
          第一,“同时经过根节点和S的分支的黑色节点个数不变”。
                 若满足“第一”,只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”,而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1;现在,只需将S由“黑+黑”变成单独的“黑”节点,即可满足“第一”。
          第二,“同时经过根节点和BLS的分支的黑色节点数不变”。
                 若满足“第二”,只需要将“F的原始颜色”赋值给B即可。之前,我们已经将“F设置为黑色”(即,将B的颜色"黑色",赋值给了F)。至此,我们算是调换了F和B的颜色。
          第三,“同时经过根节点和BRS的分支的黑色节点数不变”。
                 在“第二”已经满足的情况下,若要满足“第三”,只需要将BRS设置为“黑色”即可。
    经过,上面的处理之后。红黑树的特性全部得到的满足!接着,我们将x设为根节点,就可以跳出while循环(参考伪代码);即完成了全部处理。

    至此,我们就完成了Case 4的处理。理解Case 4的核心,是了解如何“去掉当前节点额外的黑色”。

    4.3 示意图

    ============================================================================

    1、红黑树插入的例子

     

    情况1

    如果叔叔结点为红色。

    下图为插入N节点的情况。

    转换前:

     

    \

    转换后:

     

    \

    上图中将情况1转换为了情况2.

    情况2:

    叔叔节点为黑色:插入节点是父结点的右孩子。

    继续上图的转换,转换后:

    \

    这时情况2转换为了情况3:

    情况3

    叔叔节点为黑色:插入节点为左孩子。

    \

     

     

     

    2、红黑树删除的例子

     

    有一棵红黑树12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17,如图10

     

    \

    图10

    1.删除结点12

    结点12有两个非空子结点,首先调整为叶结点,与其后继结点13进行值交换,然后删除12;由于后继结点为黑色,删除后出现“双黑”,

    如图11

     

    \

    图11

    此时,属于第一种情况的A种,处理后结果如图12

     

    \

    图12

    2.删除1结点

    1结点有两个非空子结点,调整为叶子结点,与其后继结点2进行值 交换;此时,1结点只有一个非空子结点,则删除1结点后,将其子结点着为黑色,处理结果如图13

     

    \

    图13

    3.删除9

    9结点为根结点,调整为叶结点,与后继结点10值交换,由于后继结点为黑色,删除后9后,出现双黑,如图14

     

     

    \

    图14

    此时为双黑处理第二种情况,处理后,如图15

    \

    图15

    4.删除结点2

    结点2有两个非空子结点,与后继结点3值交换;后继结点为黑色,删除2后,出现双黑;如图16

    \

    图16

    此时,为双黑处理第二种情况,处理后,如图17

     

    \

    图17

    5.删除结点0

    结点0为红色结点,直接删除即可

    6.删除结点11

    结点11有一个非空子结点,为第二种情况,删除11 后,将其非空子结点着为黑色,如图18

     

    \

    图18

     

    7.删除结点7

    结点7有一个非空子结点,也为第二种情况,删除7后,将其非空子结点着为黑色;

    8.删除结点19

    结点19为叶子结点,且为黑色,删除后出现“双黑”,属于双黑处理的第一种情况,处理后如图19

     

    \

    图19

    9.删除结点4

    结点4有两个非空子树,与其后继结点5交换;后继结点为黑色,删除4后,出现双黑,此时为双黑处理第二种情况,处理后如图20

    \

    图20

    10.删除结点15

    结点15为叶子结点,删除后出现“双黑”,此时属于双黑处理第一种情况的B种,处理后如图21

    \

    图21

    11.删除结点18

    结点18为叶子结点,且为黑色,删除后出现双黑,属于双黑处理的第二种情况,处理后,如图22

     

    \

    图22

    12.删除结点5

    结点5有两个子结点,与其后继结点6交换;交换后,结点5只有一个非空子结点,属于第二种情况,直接删除,将非空子结点着黑色,如图23

    \

    图23

    13.删除结点14

    结点14有两个子树,与其后继结点16交换;后继结点为红色,交换后14 为红色,直接删除。

    14.删除结点13

    结点13为叶子结点,且为黑色,删除后出现“双黑”,属于双黑处理的第二种情况,处理后如图24

    \

    图24

    15.删除结点10

    结点10为根结点,与其后继16值交换;交换后10只有一个非空子结点,直接将10删除,将非空子结点着为黑色

    16.删除结点16

    结点16为根结点,与后继结点17值交换;交换后16为叶子结点,且为黑色,删除后出现双黑,属于双黑处理的第三种情况,处理后如图25

    \

    图25

    17.删除结点6

    结点6为根结点,与后继结点8值交换;交换后,结点6为红色,直接删除

    \

    18.删除结点3

    结点3为叶子结点,且为黑色,删除后出现“双黑”,属于双黑处理的第二种情况

    \

    删除8:

    \

    删除17:

    \

     

    展开全文
  • 红黑树插入操作的平衡调整

    千次阅读 2019-05-21 21:53:47
    红黑树规定,插入的节点必须是红色的。而且,二叉查找树中新插入的节点都是放在叶子节点上。 如果插入节点的父节点是黑色的,那我们什么都不用做,它仍然满足红黑树的定义。 如果插入的节点是根节点,那我们直接...

    参考来源:极客时间

     

    红黑树规定,插入的节点必须是红色的。而且,二叉查找树中新插入的节点都是放在叶子节点上。

    如果插入节点的父节点是黑色的,那我们什么都不用做,它仍然满足红黑树的定义。

    如果插入的节点是根节点,那我们直接改变它的颜色,把它变成黑色就可以了。

    除此之外,其他情况都会违背红黑树的定义,于是我们就需要进行调整,调整的过程包含两种基础的操作:左右旋转和改变颜色。

    新节点插入之后,如果红黑树的平衡被打破,那一般会有下面三种情况。我们只需要根据每种情况的特点,不停地调整,就可以让红黑树继续符合定义,也就是继续保持平衡。

     

    CASE 1:如果关注节点是 a,它的叔叔节点 d 是红色,我们就依次执行下面的操作:

    将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色;

    将关注节点 a 的祖父节点 c 的颜色设置成红色;

    关注节点变成 a 的祖父节点 c;

    跳到 CASE 2 或者 CASE 3。

    https://static001.geekbang.org/resource/image/60/40/603cf91f54b5db21bd02c6c5678ecf40.jpg

    CASE 2:如果关注节点是 a,它的叔叔节点 d 是黑色,关注节点 a 是其父节点 b 的右子节点,我们就依次执行下面的操作:

    关注节点变成节点 a 的父节点 b;

    围绕新的关注节点b 左旋;

    跳到 CASE 3。

    https://static001.geekbang.org/resource/image/44/ad/4480a314f9d83c343b8adbb28b6782ad.jpg

    CASE 3:如果关注节点是 a,它的叔叔节点 d 是黑色,关注节点 a 是其父节点 b 的左子节点,我们就依次执行下面的操作:

    围绕关注节点 a 的祖父节点 c 右旋;

    将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。

    调整结束。

    https://static001.geekbang.org/resource/image/04/12/04650d9470b1e67899f5b8b7b8e33212.jpg

     

     

    删除操作的平衡调整

     

    红黑树插入操作的平衡调整还不是很难,但是它的删除操作的平衡调整相对就要难多了。不过原理都是类似的,我们依旧只需要根据关注节点与周围节点的排布特点,按照一定的规则去调整就行了。

    删除操作的平衡调整分为两步,第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后,仍然满足最后一条定义的要求,也就是说,每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;第二步是针对关注节点进行二次调整,让它满足红黑树的第三条定义,即不存在相邻的两个红色节点。

    1. 针对删除节点初步调整

    这里需要注意一下,红黑树的定义中“只包含红色节点和黑色节点”,经过初步调整之后,为了保证满足红黑树定义的最后一条要求,有些节点会被标记成两种颜色,“红 - 黑”或者“黑 - 黑”。如果一个节点被标记为了“黑 - 黑”,那在计算黑色节点个数的时候,要算成两个黑色节点。

    在下面的讲解中,如果一个节点既可以是红色,也可以是黑色,在画图的时候,我会用一半红色一半黑色来表示。如果一个节点是“红 - 黑”或者“黑 - 黑”,我会用左上角的一个小黑点来表示额外的黑色。

    CASE 1:如果要删除的节点是 a,它只有一个子节点 b,那我们就依次进行下面的操作:

    https://static001.geekbang.org/resource/image/a6/c3/a6c4c347b7cbdf57662bab399ed36cc3.jpg

    删除节点 a,并且把节点 b 替换到节点 a 的位置,这一部分操作跟普通的二叉查找树的删除操作一样;

    节点 a 只能是黑色,节点 b 也只能是红色,其他情况均不符合红黑树的定义。这种情况下,我们把节点 b 改为黑色;

    调整结束,不需要进行二次调整。

    CASE 2:如果要删除的节点 a 有两个非空子节点,并且它的后继节点就是节点 a 的右子节点 c。我们就依次进行下面的操作:

    如果节点 a 的后继节点就是右子节点 c,那右子节点 c 肯定没有左子树。我们把节点 a 删除,并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异;

    然后把节点 c 的颜色设置为跟节点 a 相同的颜色;

    如果节点 c 是黑色,为了不违反红黑树的最后一条定义,我们给节点 c 的右子节点 d 多加一个黑色,这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”;

    这个时候,关注节点变成了节点 d,第二步的调整操作就会针对关注节点来做。

    https://static001.geekbang.org/resource/image/48/4e/48e3bd2cdd66cb635f8a4df8fb8fd64e.jpg

    CASE 3:如果要删除的是节点 a,它有两个非空子节点,并且节点 a 的后继节点不是右子节点,我们就依次进行下面的操作:

    找到后继节点 d,并将它删除,删除后继节点 d 的过程参照 CASE 1;

    将节点 a 替换成后继节点 d;

    把节点 d 的颜色设置为跟节点 a 相同的颜色;

    如果节点 d 是黑色,为了不违反红黑树的最后一条定义,我们给节点 d 的右子节点 c 多加一个黑色,这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”;

    这个时候,关注节点变成了节点 c,第二步的调整操作就会针对关注节点来做。

    https://static001.geekbang.org/resource/image/b9/29/b93c1fa4de16aee5482424ddf49f3c29.jpg

    2. 针对关注节点进行二次调整

    经过初步调整之后,关注节点变成了“红 - 黑”或者“黑 - 黑”节点。针对这个关注节点,我们再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。

    CASE 1:如果关注节点是 a,它的兄弟节点 c 是红色的,我们就依次进行下面的操作:

    围绕关注节点 a 的父节点 b 左旋;

    关注节点 a 的父节点 b 和祖父节点 c 交换颜色;

    关注节点不变;

    继续从四种情况中选择适合的规则来调整。

    https://static001.geekbang.org/resource/image/ac/91/ac76d78c064a2486e2a5b4c4903acb91.jpg

    CASE 2:如果关注节点是 a,它的兄弟节点 c 是黑色的,并且节点 c 的左右子节点 d、e 都是黑色的,我们就依次进行下面的操作:

    将关注节点 a 的兄弟节点 c 的颜色变成红色;

    从关注节点 a 中去掉一个黑色,这个时候节点 a 就是单纯的红色或者黑色;

    给关注节点 a 的父节点 b 添加一个黑色,这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”;

    关注节点从 a 变成其父节点 b;

    继续从四种情况中选择符合的规则来调整。

    https://static001.geekbang.org/resource/image/ec/ec/eca118d673c607eb2b103f3476fb24ec.jpg

    CASE 3:如果关注节点是 a,它的兄弟节点 c 是黑色,c 的左子节点 d 是红色,c 的右子节点 e 是黑色,我们就依次进行下面的操作:

    围绕关注节点 a 的兄弟节点 c 右旋;

    节点 c 和节点 d 交换颜色;

    关注节点不变;

    跳转到 CASE 4,继续调整。

    https://static001.geekbang.org/resource/image/44/af/44075213100edd70315e1492422c92af.jpg

    CASE 4:如果关注节点 a 的兄弟节点 c 是黑色的,并且 c 的右子节点是红色的,我们就依次进行下面的操作:

    围绕关注节点 a 的父节点 b 左旋;

    将关注节点 a 的兄弟节点 c 的颜色,跟关注节点 a 的父节点 b 设置成相同的颜色;

    将关注节点 a 的父节点 b 的颜色设置为黑色;

    从关注节点 a 中去掉一个黑色,节点 a 就变成了单纯的红色或者黑色;

    将关注节点 a 的叔叔节点 e 设置为黑色;

    调整结束。

    https://static001.geekbang.org/resource/image/5f/44/5f73f61bf77a7f2bb75f168cf432ec44.jpg

    展开全文
  • 红黑树插入和删除的各种情况分析

    千次阅读 2021-01-11 17:55:39
    1.红黑树的定义 红黑树是一种自平衡的二叉查找树,是一种高效的查找树。 一颗m阶的B树,或为空树,或者满足依稀阿特性的M叉树; 每个节点是红色或黑色 根是黑色 所有叶子都是黑色(叶子是NIL节点) 如果一个节点是...

    1.红黑树的定义

    红黑树是一种自平衡的二叉查找树,是一种高效的查找树,定义如下:

    1. 每个节点是红色或黑色
    2. 根是黑色
    3. 所有叶子都是黑色(叶子是NIL节点)
    4. 如果一个节点是红色的,则他的两个儿子是黑色的(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(简称黑高)

    2.红黑树的数据结构

    typedef int KEY_TYPE;
    
    //定义红黑树的节点
    typedef struct _rbtree_node {
    	unsigned char color;
    	struct _rbtree_node *right;
    	struct _rbtree_node *left;
    	struct _rbtree_node *parent;
    	KEY_TYPE key;
    } rbtree_node;
    
    //定义红黑树整棵树
    //root为根节点
    //所有的叶子节点指向nil(以前我也觉得没必要,后来发现这样判断叶子节点挺好用的)
    typedef struct _rbtree {
    	rbtree_node *root;
    	rbtree_node *nil;
    } rbtree;
    

    3.左旋和右旋分析

    在这里插入图片描述
    左旋步骤:
    1)修改X的"右儿子指针"指向b
    2)修改b的"父亲指针"指向X
    3)修改Y的"父亲指针"指向Z
    4)修改Z的"(左或者右)儿子指针"指向Y
    5)修改Y的"左儿子指针"指向X
    6)修改X的"父亲指针"指向Y
    代码如下:(注意:判断b是否为叶子和传入的节点是根节点还是左右节点)

    void rbtree_left_rotate(rbtree *T, rbtree_node *x) {
    	rbtree_node *y = x->right;  
    
    	x->right = y->left; //1 
    	if (y->left != T->nil) { //2
    		y->left->parent = x;
    	}
    
    	y->parent = x->parent; //3
    	if (x->parent == T->nil) { //4
    		T->root = y;
    	} else if (x == x->parent->left) {
    		x->parent->left = y;
    	} else {
    		x->parent->right = y;
    	}
    
    	y->left = x; //5
    	x->parent = y; //6
    }
    

    右旋步骤:
    1)修改Y的"左儿子指针"指向b
    2)修改b的"父亲指针"指向Y
    3)修改X的"父亲指针"指向Z
    4)修改Z的"(左或者右)儿子指针"指向X
    5)修改X的"右儿子指针“指向Y
    6)修改Y的”父亲指针“指向X
    代码如下:(注意:判断b是否为叶子和传入的节点是根节点还是左右节点)

    void rbtree_right_rotate(rbtree *T, rbtree_node *y) {
    
    	rbtree_node *x = y->left;
    
    	y->left = x->right;//1
    	if (x->right != T->nil) {//2
    		x->right->parent = y;
    	}
    
    	x->parent = y->parent;//3
    	if (y->parent == T->nil) {//4
    		T->root = x;
    	} else if (y == y->parent->right) {
    		y->parent->right = x;
    	} else {
    		y->parent->left = x;
    	}
    
    	x->right = y;//5
    	y->parent = x;//6
    }
    

    3.插入的情况分析

    1)根据要插入的key的值,找到叶子结点并插入。
    2)判断当前结点key的父节点是否为黑色,是则退出,否则进入第三步。
    3)判断当前结点key叔叔节点是否为红色,是则进去第四步,否则进入第五步。
    4)将当前结点key的祖父节点变红,key的父节点和叔叔节点变黑,在将当前结点指向祖父节点并回到第二步。(笔记:因为父亲是红色节点,所以祖父肯定不是红色节点,是黑色节点)
    5)判断当前结点key的父亲节点是否为祖父节点的左儿子,是则进入第六步,否则进入第八步。
    6)判断当前结点key是否为父亲节点的左儿子,是则进入第七步,否则对当前节点key的父亲节点进行左旋,再进入第七步。(注意:经过左旋后,当前节点上去了,曾经的父亲节点下来了,当前节点key指向的是下来的节点(曾经的父亲节点))
    7)将当前结点key的父亲节点变色为黑色,祖父节点变色为红色,最后将当前节点key指向祖父节点,对当前节点key进行右旋,并返回第二步。(笔记:经过右旋后,当前节点肯定是黑色,因为他是曾经的父亲节点旋转上来的)
    8)判断当前结点key是否为父亲节点的右儿子,是则进入第七步,否则对当前节点key的父亲节点进行右旋,再进入第九步。(注意:经过右旋后,当前节点上去了,曾经的父亲节点下来了,当前节点key指向的是下来的节点(曾经的父亲节点))
    9)将当前结点key的父亲节点变色为黑色,祖父节点变色为红色,最后将当前节点key指向祖父节点,对当前节点key进行左旋,并返回第二步。(笔记:经过左旋后,当前节点肯定是黑色,因为他是曾经的父亲节点旋转上来的)

    void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {
    	//步骤二
    	while (z->parent->color == RED) { 
    		//步骤五
    		if (z->parent == z->parent->parent->left) {
    			rbtree_node *y = z->parent->parent->right;
    			//步骤三
    			if (y->color == RED) {//步骤四
    				z->parent->color = BLACK;
    				y->color = BLACK;
    				z->parent->parent->color = RED;
    
    				z = z->parent->parent; 
    			} else {//步骤五
    
    				if (z == z->parent->right) {//步骤六
    					z = z->parent;
    					rbtree_left_rotate(T, z);
    				}
    
    				z->parent->color = BLACK;
    				z->parent->parent->color = RED;
    				rbtree_right_rotate(T, z->parent->parent);
    			}
    		}else {
    			rbtree_node *y = z->parent->parent->left;
    			//步骤三
    			if (y->color == RED) {//步骤四
    				z->parent->color = BLACK;
    				y->color = BLACK;
    				z->parent->parent->color = RED;
    
    				z = z->parent->parent; 
    			} else {//步骤五
    				if (z == z->parent->left) {//步骤八
    					z = z->parent;
    					rbtree_right_rotate(T, z);
    				}
    
    				z->parent->color = BLACK;
    				z->parent->parent->color = RED;
    				rbtree_left_rotate(T, z->parent->parent);
    			}
    		}
    		
    	}
    
    	T->root->color = BLACK;
    }
    
    
    void rbtree_insert(rbtree *T, rbtree_node *z) {
    
    	rbtree_node *y = T->nil;
    	rbtree_node *x = T->root;
    	//步骤一
    	while (x != T->nil) {
    		y = x;
    		if (z->key < x->key) {
    			x = x->left;
    		} else if (z->key > x->key) {
    			x = x->right;
    		} else { //Exist
    			return ;
    		}
    	}
    
    	z->parent = y;
    	if (y == T->nil) {
    		T->root = z;
    	} else if (z->key < y->key) {
    		y->left = z;
    	} else {
    		y->right = z;
    	}
    
    	z->left = T->nil;
    	z->right = T->nil;
    	z->color = RED;
    
    	rbtree_insert_fixup(T, z);
    }
    

    举个例子
    在下面的红黑树中插入4这个节点
    在这里插入图片描述
    步骤一:找到4的位置,并且插进去,颜色为红色,变为下图
    在这里插入图片描述
    步骤二:当前节点(4)的父亲节点(5)是红色的,进入第三步,
    步骤三:叔叔节点(8)是红色的,进入第四步,
    步骤四:将当前结点key的祖父节点(7)变红,key的父节点(5)和叔叔节(8)点变黑,在将当前结点指向祖父节点(7)并回到第二步,变为下图。

    在这里插入图片描述
    步骤二:当前节点(7)的父亲节点(2)是红色的,进入第三步,
    步骤三:叔叔节点(14)是黑色的,进入第五步,
    步骤五:当前节点(7)的父亲节点(2)是为祖父节点(11)的左儿子,进入第六步
    步骤六:当前节点(7)不是为父亲节点(2)的左儿子,当前节点的父亲节点(2)进行左旋,再进入第七步。(注意:经过左旋后,当前节点变为曾经的父亲节点(2)了)
    步骤七:将当前节点(2)的父亲节点(11)变色为黑色,祖父节点(11)变色为红色,最后将当前节点key指向祖父节点,对当前节点key进行右旋,并返回第二步。(笔记:经过右旋后,当前节点肯定是黑色,因为他是曾经的父亲节点旋转上来的),变为下图。
    在这里插入图片描述
    步骤七:将当前节点(2)的父亲节点(7)变色为黑色,祖父节点(11)变色为红色,最后将当前节点指向祖父节点(11),对当前节点key进行右旋,并返回第二步。(笔记:经过右旋后,当前节点肯定是黑色,因为他是曾经的父亲节点(7)旋转上来的),变为下图。
    在这里插入图片描述

    4.删除的情况分析

    1)
    2)
    4)
    5)
    6)

    展开全文
  • 红黑树插入,删除时各种状态的平衡操作。
  • 1. 被插入的节点是根节点。 2. 被插入的节点的父节点是黑色。 3. 被插入的节点的父节点是红色。 3.1 叔叔结点为红色 3.2 插入结点的父结点p是祖父结点pp的左子结点,插入结点的叔叔结点s不存在或为黑色 ...

    目录

    1. 被插入的节点是根节点。

    2. 被插入的节点的父节点是黑色。

    3. 被插入的节点的父节点是红色。

      3.1 叔叔结点为红色

      3.2  插入结点的父结点p是祖父结点pp的左子结点,插入结点的叔叔结点s不存在或为黑色

        3.2.1 插入结点是父结点p的左子结点

        3.2.2 插入结点是父结点p的右子结点

      3.3 插入结点的父结点p是祖父结点pp的右子结点,插入结点的叔叔结点s不存在或为黑色

        3.3.1插入结点是父结点p的右子结点

        3.3.2插入结点是父结点p的左子结点


    红黑树的插入和搜索二叉树一样,都需要先找到其插入位置。
    插入的节点默认是红色。(要是黑色的话,那所有性质都一直满足,皆大欢喜了,就不用再平衡了,肯定不对)
    然后再通过变色、左旋、右旋等满足其性质。

    插入的情况如下图所示:

    1. 被插入的节点是根节点。

        处理方法:直接把此节点涂为黑色。

    2. 被插入的节点的父节点是黑色。

        处理方法:什么也不需要做。节点被插入后,仍然满足红黑树性质。

    3. 被插入的节点的父节点是红色。

       处理方法:这种情况下有连续两个红色节点,不满足红黑树的性质,需要调整。简单分析一下,被插入节点的父节点是红色,那么其祖父节点肯定存在且一定是黑色。我们依据其叔叔节点(其父亲节点的兄弟节点)的情况,将这种情况进一步划分。

      3.1 叔叔结点为红色

    我们可以将父亲结点p和叔叔结点s变黑色,祖父结点变红色就能解决问题。但是只是局部的平衡,祖父结点变红色还可能引起不平衡,因此还需要将祖父结点pp作为插入结点继续向上的平衡。

    • 把祖父结点pp变红色
    • 把父结点p和叔叔结点变黑色
    • 把pp作为新的插入结点

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C8Y7tOoB-1583207277072)(D:\Chrome\ChromeDownloads\qingxing3.1.gif)]

      3.2  插入结点的父结点p是祖父结点pp的左子结点,插入结点的叔叔结点s不存在或为黑色

    这里可能会有疑问:既然父结点为红,为什么叔叔结点会为黑色,这样叔叔结点所在子树的黑色结点数目不就多一了吗?
    答:因为类似于上述3.1向上平衡的情况,因此插入结点的叔叔结点有可能是黑色的。

    这种情况意味着左边子树结点比右边少,我们就需要通过右旋向右子树去借节点。

        3.2.1 插入结点是父结点p的左子结点

         因为把pp右旋后是黑色破坏了黑色结点的数量,因此还需要将pp变红。p则需要变为原来pp的颜色,即黑色。

    • 对pp右旋
    • p变黑,pp变红

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2Lm0JDyI-1583207277073)(D:\Chrome\ChromeDownloads\qingxing3.2.1.gif)]

        3.2.2 插入结点是父结点p的右子结点

        这种情况我们发现对插入结点的父结点p进行左旋,就变成情况3.2.1了,然后按照3.2.1进行处理

    • 对p左旋
    • 转到情况3.2.1处理

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3s07O48m-1583207277074)(D:\Chrome\ChromeDownloads\qingxing3.2.2.gif)]

      3.3 插入结点的父结点p是祖父结点pp的右子结点,插入结点的叔叔结点s不存在或为黑色

    这种情况就是3.2情况的对称情况,这里有一个小技巧,把3.2的情况的左右对换就是3.3情况了

        3.3.1插入结点是父结点p的右子结点

        这种情况和3.2.1类似,因为是对称的,只要把左变成右,右变成左就行了。

    • 对pp左旋
    • p变黑,pp变红

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dfDLk9Xv-1583207277075)(D:\Chrome\ChromeDownloads\qingxing3.3.1.gif)]

        3.3.2插入结点是父结点p的左子结点

       这种情况是和3.2.2类似,我们对p右旋,转为情况3.3.1

    • 对p右旋
    • 转到情况3.3.1处理

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uklMrgiJ-1583207277076)(D:\Chrome\ChromeDownloads\qingxing3.3.2.gif)]

    展开全文
  • 红黑树 插入算法(一)

    千次阅读 2020-03-31 00:54:16
    红黑树在数据结构里面,是一种能自动平衡的树,它的查询速度很快,因为能够用到二分法,二分法的查询复杂度只有O(log2(N)),几万条的数据也就只需查十几次,不过要维持那么高的查询速度也是有代价,它的添加和删除节点都...
  • 大家如果有玩魔方,我相信是可以理解我说的东西的,转魔方就是先把第一面转出来,然后把第一面作为底面,然后根据遇见的情况来转魔方(是有公式的) ...【算法】红黑树插入数据(变色,左旋、右旋)(二):https://...
  • 在HashMap中,我觉得最难的应该是红黑树了吧,我结合代码和画图软件研究了两天,终于总结出规律,现在分享给大家 一、红黑树的特点 下面是红黑树的5条性质,现在大家要对这些性质有印象,后面我会结合图
  • 这里是目录预备知识点红黑树红黑树插入策略红黑树插入修正的4种情况红黑树插入修正的4种方式源码分析 预备知识点 进入代码分析之前简要介绍相关知识点,推荐一个视频,讲得很好: youtube:...
  • 红黑树维护算法及其区间树应用:实现红黑树插入删除算法,实现区间树上的重叠区间查找算法。由于一棵有n个结点的红黑树的高度为O(logn),因此RB-NSERT的第1~16行要花费O(logn)时间。在 RB-INSERT-FIXUP中,仅当情况1...
  • 红黑树-JAVA实现(红黑树插入和删除)

    千次阅读 2017-02-10 12:41:08
    AVL树由于实现比较复杂,而且插入和删除性能差,在实际环境下的应用不如红黑树红黑树(Red-Black Tree,以下简称RBTree)的实际应用非常广泛,比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等,...
  • 红黑树图文详解及其C++语言实现
  • 红黑树是平衡二叉查找树中的一种,最突出的特点是效率高。时间复杂度:O(log(n))红黑树有如下4个性质: 1).没个结点不是红色就是黑色; 2).根结点是黑色的; 3).每个红色结点的父亲是黑色的; 4).根结点到达每个...
  • 本节我们主要总结红黑树插入相关的知识。 二、红黑树插入 红黑树的插入包含两个步骤: 在树中查找插入的位置; 插入后自平衡; 查找流程: 从根节点开始查找; 若根节点为空,那么插入节点作为根节点,结束; 若...
  • 鉴于网上其它教程中对于红黑树插入操作的叙述并不十分清楚准确全面,所以本文主要是对插入过程进行介绍。参见第3节。 本文对于红黑树的定义、概念、性质、以及操作过程的图形化表述等内容的叙述较为简略,请参考...
  • 本人菜鸡一只,正在更新红黑树系列的文章。 该系列已经全部更完,有5篇文章: ...【算法】红黑树插入数据(变色,左旋、右旋)(二):https://blog.csdn.net/lsr40/article/details/85245027 【算法...
  • 红黑树的定义红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求: 性质1. 节点是红色或黑色。 性质2. 根是黑色。 性质3....
  • 红黑树插入和删除原理

    千次阅读 2014-10-04 11:00:01
    红黑树本质是一颗二叉查找树,增加了着色以及相关的性质,使得红黑树的查找,插入,删除的时间复杂度最坏为O(log n)。 一、红黑树相对二叉查找树来说,有以下五个性质。 a.红黑树的节点不是红色就是黑色 b.红黑树...
  • 引言:  目前国内图书市场上,抑或网上讲解红黑树的资料层次不... 而我们知道,即便在经典的算法导论一书上,也没有把所有的插入、删除情况一一道尽,直接导致了不少读者的迷惑,而我的红黑树系列第4篇文章:一步
  • 红黑树插入演示

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 83,297
精华内容 33,318
关键字:

红黑树的插入