神刀安全网

直接理解红黑树旋转

只需要一张图

直接理解红黑树旋转

  1. 对于新插入的每个节点而言,它都是红色的,那么就有两种情况

    1. 他父亲是黑色(完美,啥都不用变)
    2. 他父亲是红色(需要调整了,从他自己开始,一路向 根节点 调整)
  2. 所以最外层可以用一个循环,来判断是否到了根,是否父节点是黑色。

  3. 无论是有接触到 root 节点,在最末尾都给他设置成黑色,这是最省事的做法,也不会有什么性能消耗。
  4. 红字中的: 左旋,右旋,是按照顺序的,且针对的目标不同,稍微看过的应该能很快知道

    1. 父为左子->伯父为黑->新点为右情况下: (先对父)左旋, 改颜色 ,(再对祖父)右旋。
      • 无论如何,先对某个节点的父节点进行单旋转,仅仅是改变这两个家伙的位置(只有在颜色相同时才会触发旋转)。
    2. 父为左子->伯父为黑->新点为左情况下: 改颜色 , (对祖父)右旋
  5. 下面的情况就是依此类推

  6. 改颜色 ,顾名思义就是,设置颜色的意思,并且将空节点(NULL节点)也 视为黑色的

以上所述

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 直接理解红黑树旋转

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮