精华内容
下载资源
问答
  • 红黑树旋转变色规则
    千次阅读
    2019-12-07 10:43:52

    一、红黑树性质

    1. 结点必须是红色或者黑色。
    2. 根节点必须是黑色。
    3. 叶节点(NIL)必须是黑色(NIL节点无数据,是空节点)。
    4. 红色结点不能连续。
    5. 从任一节点出发到其每个叶子节点的路径,黑色节点的数量必须相等。

    二、旋转变色规则

    已知插入根节点涂为黑色,其他节点都是涂红色;如果插入结点的父节点为黑色,就不需要进行旋转变色调整,其他情况都需要根据实际选择合适的处理策略进行调整,使其符合红黑树性质。最开始调整的时候是将插入结点作为当前节点。

    红黑树元素插入旋转变色规则
     实际情况处理策略
    第一种当前节点的父节点是红色,且其祖父节点的另一个子节点(叔叔节点)也是红色,祖父节点不是根节点。

    (1)将父节点和叔叔节点设为黑色。

    (2)将祖父节点设为红色。

    (3)将祖父节点作为新的当前节点。

    第二种当前节点的父节点是红色,叔叔节点也是红色,且当前节点在最边上(即每行最左边或最右边的节点),祖父节点是根节点。

    (1)将根节点作为新的当前节点,以根节点为支点进行左旋(插入的是右孩子)或者右旋(左孩子)。

    (2)旋转后将新的根节点变黑色,其他节点根据需要变色,只要保证不出现红红连续节点即可。

    (3)判断性质5是否已满足,不满足则以当前节点为支点进行一次左旋或右旋,旋转后依旧要保证不出现红红连续节点,否则进行变色。

    第三种其他所有情况,前提是当前节点的父节点是红色。

    (1)将父节点作为新的当前节点。

    (2)以新的当前节点为支点进行左旋(插入的是右孩子)或者右旋(左孩子)。

     

    更多相关内容
  • 红黑树变色旋转

    2021-03-12 16:24:10
    红黑树是自平衡的二叉查找树,所以了解红黑树之前我们需要先了解什么是二叉查找树。 二叉查找树 1.某节点的左子树节点值仅包含小于该节点的值 2.某节点的右子树节点值仅包含大于该节点的值 3.左右子树也...
            红黑树是自平衡的二叉查找树,所以了解红黑树之前我们需要先了解什么是二叉查找树。
     

    二叉查找树

     
         1.某节点的左子树节点值仅包含小于该节点的值
         2.某节点的右子树节点值仅包含大于该节点的值
         3.左右子树也必须是二叉查找树
     
              这样的数据结构的好处就在于,当我查询10这个节点时,10>9,查看右孩子13,10<13,查看左孩子11,10<11,查看左孩子10,发现10正是要查找的节点,大大提交查询效率,这种方式是二分查找的思想,查询所需的最大次数等同于二叉查找树的高度。
     

    二叉查找树的局限性

     
          当我们插入7,6,5,4,3时,我们会发现树结构是这样的。
             这样我们会发现也符合二叉树的结构,但是这样线性的结构会导致我们的查找性能大打折扣,所以我们需要解决二叉树多次插入新节点而导致的不平衡,红黑树就出现了。
     

    红黑树

     
         红黑树是自平衡的二叉树,除了满足二叉树的特性外,还应具备以下特性:
          1.每个节点只有黑红两色
          2.树的根节点是黑色的
          3.没有两个相邻的红色节点,即一个红色节点它的父节点和子结点中不能存在红色节点
          4.从节点(包括根节点)到其任何后代的NULL节点(每个叶子节点下面有两个空节点)的路径上黑色节点的数量是相同的
     
         当我们插入新节点时,新节点是红色的,应为黑色节点会导致第4条规则更难去调节子树。当新节点的父节点是黑色时,就不需要去变化了,但是当是红色时,我们需要对其进行处理。
    主要两大操作:
         1.recolor(变色)
         2.rotation(旋转)
     
          假设我们新插入节点为X
           1.将新插入的节点标记为红色
           2.如果x是根节点,则标记为黑色
           3.如果x的parent不是黑色,同时x也不是root
           x的uncle(叔叔)颜色不同,操作也分为两种情况
     

    (1) 变色

     
            如果x的uncle(叔叔)是红色
    •   将x的parent和uncle标记为黑色
    •   将x的祖父标记为红色
    •  让x颜色与x祖父的颜色相同,然后重复不走2,3直到符合红黑树的特性       
     
                
            跟着上面的公式走:
    1.  将新插入的x节点标记为红色
    2. 发现x的父节点p是红色,违反了红黑树的第3条特性
    3. 发现x的uncleu同样是红色
    4. 将p和u标记为黑色
    5. 将x的祖父标记为红色,此时g就是新的x,继续重复2和3的步骤
    6. 发现g是根节点,标记为黑色,结束
     

    (2)旋转

     
            如果x的叔叔是黑色,要考虑四种情况,左左,左右,右左,右右,主要演示旋转,第4条特性先忽略。
          

            左左

            这种情况很简单,想象这是一根绳子,手提起 P 节点,然后变色即可
     

            左右

            左旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的左孩子,然后再应用 左左情况
     

            右左

            右旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的右孩子,然后再应用 右右情况
         

     

           右右

             与左左情况一样,想象成一根绳子
     
     

     

    案例:

         在一个二叉树插入节点21:
    首先,我们需要做的是变色,把节点25及其下方的节点变色:
    此时节点17和节点25是连续的两个红色节点,那么把节点17变成黑色节点?恐怕不合适。这样一来不但打破了规则4,而且根据规则2(根节点是黑色),也不可能把节点13变成红色节点。 变色已无法解决问题,我们可以用到旋转。
    由于根节点必须是黑色节点,所以需要变色,变色结果如下:
    这样就结束了吗?并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4,其他路径的黑色节点个数是3,不符合规则5。
     
    这时候我们需要把节点13看做X,节点8看做Y,像刚才的示意图那样进行右旋转
    最后根据规则来进行 变色
    如此一来,我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂,经历了如下步骤:
     
    变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色
     
     

     
    展开全文
  • 红黑树变色规则

    千次阅读 2021-10-24 15:05:25
    红黑树变色规则

    什么是红黑树

    我们平时说的平衡二叉查找树一般指的是AVL树,在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。红黑树也是自平衡的二叉查找树,红黑树由自己的性质约束,通过变色和旋转保持相对平衡的结构。与AVL树相比,条件没那么苛刻,插入和删除数据时会用较少的时间,查询数据时也不会用慢太多。

    红黑树性质

    性质1. 结点是红色或黑色。

    性质2. 根结点是黑色。

    性质3. 所有叶子都是黑色。(叶子是NIL结点)

    性质4. 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)

    性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。

    这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。

    是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点,这就表明了没有路径能多于任何其他路径的两倍长。

    示例

      在线创建红黑树的网站:Red/Black Tree Visualization

    展开全文
  • 什么是红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定...

    什么是红黑树

    红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。——来自百度百科

    为什么需要红黑树?

    红黑树的使用极大的提高了搜索效率,传统的二叉树和二叉排序树有着明显的劣势,当我们插入的数据是有序的时候,底层的二叉排序树的数据结构是这样的:
    在这里插入图片描述
    可以看到,原本具有二分查找效率的二叉树退化成线性结构。这时我们就需要引入一种查询效率更高的二叉树。即红黑树。

    红黑树的性质(特点)

    红黑树(Red Black Tree)是一种自平衡的二叉树,除了符合二叉树的基本特性外,还具有以下附加特点:

    1. 每个结点不是黑色就是红色
    2. 不可能有连在一起的红色节点
    3. 根结点是黑色的(入度为0即是根结点)
    4. 每个红色结点的俩个子结点都是黑色,叶子结点默认黑色的(这里代表位置占据,并不显示出来,因为没有数据。)
    5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
      在这里插入图片描述

    红黑树的变换

    结合红黑树的性质,保证了红黑树的自平衡,使红黑树从根到叶子结点最长路径不会超过最短路径的2倍。当插入或删除结点的时候,红黑树的规则有可能被打破,这时就需要通过一些调整来维持这些特性:
    注意:默认后续插入的结点都是红色结点。
    如:

    • 调整的方法——变色
      为了重新符合红黑树的规则,尝试把红色节点变为黑色,或者把黑色节点变为红色。
      变色的情况:
      当前结点的父亲结点是红色,且父亲结点的兄弟节点也是红色。即
      在这里插入图片描述
      就可以进行变色
      步骤:
      ① 把父节点设为黑色
      ② 把父节点的兄弟结点也设为黑色
      ③ 把祖父也就是爷爷结点设为红色
      在这里插入图片描述
      如插入结点6
      在这里插入图片描述
      分析发现,满足红黑树的性质,不需要继续变色或转换。

    • 调整的方法——旋转
      当变色也无法解决问题时,就需要通过左旋转或右旋来解决问题。
      为了方便理解,在这里我们在分别在30、35的左子树加入结点32、34。以便更好的理解红黑树的旋转过程。

    • 左旋: 当前父节点是红色,父节点的兄弟结点是黑色时,且当前的结点是右子树。左旋,以父节点作为左旋:

    • 右旋: 当前父节点是红色,父节点的兄弟结点是黑色时,且当前结点是左子树右旋
      如插入结点37:
      在这里插入图片描述

    此时的红黑树已经不满足条件2和4,且也不满足换色的条件 (37的父节点的兄弟节点不为红色)
    在这里插入图片描述
    此时可以进旋转,根据条件可以得出当前的结点是右子树,所以需要左旋
    在这里插入图片描述
    结果:
    在这里插入图片描述
    然后我们发现,此时37结点的父亲和其父亲的兄弟结点都为红色,已经满足换色条件,但又因为根节点不能为红色,所以只能继续通过旋转来变换,且37结点在右子树,因而需要继续左旋:
    在这里插入图片描述
    到这里,我们发现根结点变为红色,此时只需要将其变为黑色,就完成了插入37时红黑树的调整过程。
    在这里插入图片描述

    总结

    以上是关于红黑树的介绍,红黑树的优点很明显,是一种二叉排序树的进一步完善,可以自动平衡结点,但它也有缺点,当数据表中的数据有几十万甚至上百万条时,查询的次数,也就是树的深度仍然很大。那时就可以使用到B Tree、B+tree。

    展开全文
  • 红黑树简介及左旋、右旋、变色

    千次阅读 2020-06-06 09:33:24
    红黑树简介及红黑树的左旋、右旋、变色
  • 红黑树是一种平衡二叉树,除了有二叉树的特点外,还有以下特点 节点是红色或者黑色 根节点是黑色 每个叶子的节点都是黑色的空节点(NULL) 每个红色节点的两个子节点都是黑色的。 从任意节点到其每个叶子的所有路径...
  • 红黑树的性质 1、每个节点不是红色就是黑色 2、不可能有连在一起的红色节点(这个性质后面要用,其他性质看一遍就够了) 3、根节点都是黑色的(什么是根节点:父节点为null,或者入度为0) 4、每个红色节点的两...
  • 红黑树的五个规则是什么? 节点是红色或黑色的; 根节点是黑色的; 每个叶子节点都是黑色的空节点(NIL节点); 每个红色节点的两个子节点都是黑色的(从每个叶子到根的所有路径上不可能有两个连续的红色节点); ...
  • 红黑树旋转

    2021-01-05 23:07:07
    如果对红黑树还不了解的,建议看上一篇博客。 https://blog.csdn.net/weixin_37909391/article/details/112252930 首先回顾以下红黑树的性质: 结点必须是红色或者黑色。 根节点必须是黑色。 叶节点(NIL)必须是...
  • 在学习红黑树之前,我们最好先学习一下AVLTree,并且这两个平衡二叉搜索树的难度差不多,学过了AVLTree之后,红黑树就会更加轻松一些。红黑树只是比较抽象一些,在调整方面较AVLTree要简单一些。......
  • 红黑树(一)旋转

    2019-10-06 08:31:50
    红黑树属于平衡二叉树,所以很多操作根二叉树是一样的。学习红黑树,首先要把二叉树理解,并能用代码实现。  我主要讲述我是怎么写一棵红黑树的,并不做过细的解释。我们主要学习旋转,插入,删除。其他操作根...
  • HashMap红黑树中,每插入一个节点,都要对红黑树平衡进行一个判断,是否需要调整,利用左旋转和右旋转来维护红黑树的平衡
  • 为解决这一问题,引入了**“平衡”二叉搜索树**,红黑树就是其中的一种。红黑树在树的基础上,为每个节点增加了一个颜色位,可以是RED,也可以是BLACK。通过对每条路径的颜色进行约束,保证红黑树处于近似平衡的状态...
  • 树是数据结构中经典的结构之一,也是面试中常问的面试题之一,最近复习了一个红黑树的知识,做一下整理 文章目录 前言 一、pandas是什么? 二、使用步骤 1.引入库 2.读入数据 总结 前言 提示:这里...
  • 特性(除了具备二叉查找树的特性外,还具备如下特性): (1)节点是红色或者黑色 (2)根节点是黑色 (3)每个叶子节点(也叫终端节点,简称“叶子”)都是黑色的空节点(NIL...红黑树从根到叶子的最长路径不会超...
  • 红黑树其实是由2-3树演变来的,如果想要理解红黑树,可以先看看2-3树 2-3树插入逻辑: 先找插入结点,若结点有空(即2-结点),则直接插入。如结点没空(即3-结点),则插入使其临时容纳这个元素,然后分裂此结点,把...
  • 红黑树特性及其变色旋转

    千次阅读 2019-04-12 20:16:09
    红黑树作为一种优秀的数据结构,因其高效的查找性能而广受好评~ 在JDK的集合类中TreeMap和TreeSet就是红黑树实现的 而在Java8之后,连HashMap也用到了红黑树红黑树的特性 红黑树是二叉查找树(BST)衍生出来的一...
  • 一、红黑树规则 二、红黑树的相对平衡 三、红黑树的变换 1.变色 2.旋转 (1).左旋转 (2).右旋转 四、红黑树的插入操作 1.情况一 2.情况二 3.情况三 4.情况四 5.情况五 一、红黑树规则 ...
  • 理解了这些,我们这节要学习的内容就是有关于二叉查找树以及有关红黑树。 二叉查找树 从这个名字,可以简单理解一下,他是为了解决什么被发明出来的。当然是查找了。因为名字自带查找。哈哈 开个玩笑。其实就是为了...
  • Java中红黑树规则:

    2020-11-09 11:27:53
    红黑树规则: 1.每个节点的颜色是红色或者黑色; 2.根节点必须是黑色; 3.不能出现两个红色节点相连的情况; 4.每个节点到其叶节点的简单路径上的黑色节点数量相同; 5.叶节点是黑色(没有子节点或者父节点的称为叶节点,用...
  • 一、在理解红黑树之前,先看一些二叉查找树 二叉查找树特性:左字数上所有的节点的值都小于或等于他的根节点上的值 右子树上所有节点的值均大于或等于他的根节点的值 左、右子树也跟别为平衡二叉树 举个...
  • 在HashMap中,我觉得最难的应该是红黑树了吧,我结合代码和画图软件研究了两天,终于总结出规律,现在分享给大家 一、红黑树的特点 下面是红黑树的5条性质,现在大家要对这些性质有印象,后面我会结合图
  • 手写Java红黑树

    2021-12-13 16:24:08
    红黑树左右旋转基本的规则4.纯手写红黑树旋转变色5.红黑树查询最大值 红黑树 1.红黑树基本的特征介绍 基本特征: 每个节点不是红色就是黑色 不允许两红相连 根节点都是黑色 每个红色节点的两个子节点都是黑色 ...
  • C++红黑树

    千次阅读 多人点赞 2022-03-26 18:13:48
    C++红黑树零、前言一、红黑树的概念及性质二、红黑树结点的定义三、红黑树的插入操作1、变色处理2、单旋+变色3、双旋+变色4、插入实现四、红黑树的验证五、红黑树的删除六、红黑树与**AVL**树的比较 零、前言 本...
  • 红黑树的变换规则3. 红黑树的Java实现(代码说明) 1. 红黑树的介绍 红黑树(Red-Black Tree 简称 R-B Tree),它是一种它一种特殊的二叉查找树。 红黑树是一种特殊的二叉搜索树,意味着它满足二叉查找树的特征(简书): ...
  • 红黑树介绍

    2022-05-26 12:19:33
    红黑树一、红黑树的概念红黑树的性质红黑树节点的定义红黑树结构二、使用步骤1.引入库2.读入数据总结 一、红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。...
  • Java之红黑树

    2022-04-28 09:44:00
    1、简介 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。...红黑树是一种平衡二叉查找树的变体,它的左右子树高差有可能大于 1,所以红黑树不是
  • 一文彻底理解红黑树

    2022-02-12 21:16:22
    红黑树?好熟悉,一文理解,走起! 什么是红黑树 首先,红黑树也是一种平衡二叉搜索树,也是一种平衡树,就是不会出现严重“瘸腿”的现象,出现了就会自动触发平衡操作来维持整棵树的平衡! 为了解决二叉搜索树的...
  • 红黑树,是一种平衡二叉搜索树,...因为红黑树旋转情况少于AVL树,使得红黑树整体性能略优于AVL树,不然map和set底层怎么会用红黑树呢,包括很多语言的库里面都用了红黑树。如果发明AVL树的人是天才的话,那么发明红
  • 硬核图解面试最怕的红黑树【建议反复摩擦】

    万次阅读 多人点赞 2020-11-05 09:26:58
    第三,算法导论中对于红黑树删除场景的阐述并不够具体,许多关键环节都用“经过一定的旋转变色处理”来带过,不利于新手的学习。(我花了很长时间还原具体过程)。 考虑到部分读者有充足的精力研究以2-3-4树为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,756
精华内容 702
热门标签
关键字:

红黑树旋转变色规则