Back to Posts

数据结构—红黑二叉树

Posted in dataStruct

继上一篇的23树,红黑二叉树实质上就是一个23树,在《算法》第四版开篇彩页中,将一颗红黑树展开(未展示nil节点),就是一个23树。

红黑树还是遵循了二叉树的约束,主要就将23树中变异的3-节点恢复成了二叉树中的标准节点——实际上是将3-节点中的左key提取折叠到右key的左子树位置并用红色链接表示;黑色链接代表是普通的1-节点。

对-3连接的折叠

一个红链接,实际上,就是一个-3连接节点中,前两个节点的折叠;比如一个-3节点,有BF两个键,红黑树中规定,左边的键需要降级成为右键的左子节点;
而原本-3节点的左和中节点,转变为了B的左子节点和右子节点。

原书对红黑树的一种等价定义(网上一搜红黑树出来的五个定义,是结论上的定义,这里的定义是从实现角度出发的):

红链接均为左链接;
没有任何一个节点同时和两条红链接相连;
该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同。

对于以上第一条,是一个约定,就像1+1为什么等于2;如果设定红链接都是右链接也没啥关系;
对于第二条,想想把红链接打开的情况:红链接连接的连个节点,在23树中本是平级的存在;如果存在两个连续的红链接,代表有三个节点在同一个级别;这违反了23树的定义;
红黑树既要 保证23树的定义也要保证二叉树的定义。
对于第三条,黑色节点,也就是普通节点,为了保证局部与整体的平衡,需要选装和变色来处理。

红黑树的旋转与变色

关于一二点、在红黑树中需要特别的去维护、如果红链接出现在了右链接,就需要左旋;如果出现了一个节点上有两个红链接,需要变色或是旋转

  • 变色
    如果一个节点有两个子节点,其链接都是红色,那么其子节点都转为黑色,自身转为红色并将其父链接转为红链接。
  • 旋转
    如果一个节点其与父节点和子节点的链接有两条红链接,需要视以下情况旋转:
    /\字形,如果两条红链接是这种形状,对其右旋或左旋即可;
    ><字形,如果是这种形状,需要先对中间层节点旋转;
    旋转过程同AVL,大概说一说行了。

插入和删除

以上强调的是红链接,原书中也是以链接来解释,能更好提现折叠,但是网上很多都上来直接说红节点和黑节点;
至于插入和删除;插入过程会不断出现违反上述 1,2性质的过程,需要不断旋转和变色,在AVL的旋转上再加些自身逻辑判断即可;
而删除的话,参考RedBlack.pdf吧……


对于删除的补充概括,删除一个节点,难处理的情况主要有两种:

  1. 删除的节点有子节点并且为红色(这里都不说nil),那么过程和AVL中的删除是一样的,寻找继任者复制待删除元素位置,再删除继任者即可;
  2. 删除的节点是黑色就恶心了,因为会违反上述第三条原则,红黑树的删除,主要是借鉴了23树的删除:删除3-或4-链接上的节点不会影响树的高度~
    之前已经说过,红黑树中的红链接(不说红节点避免晕菜)上的两个节点,对应23树中的3-节点;所以删除红链接上的节点,不会影响树的平衡;
    但是如果删除的是一个黑链接上的元素,会影响树的性质,能想到的方法就是将黑链接转为红链接,麻烦的是,红链接代表23数中的3-节点,黑链接代表2-节点,那么就得列举可能出现的情况,对之处理

根据Java的TreeMap的fixAfterDeletion方法,熟悉23树与红黑树后这里使用红节点的说法,将转换时对应的23树画出来:
以下情况,试待删除节点的左节点为current(当然也可以是右节点,这里先讨论待删除节点的左节点为current的情况),待删除节点的右节点为sibling;在变色和旋转之后,要保证current和sibling一直是兄弟关系——指的是对应23树中的兄弟关系;
对于如何移动current和sibling,就像那种早年的九宫格拼图游戏,有一个空白的,努力利用空白将拼图拼完整;这里就是利用红节点;sibling和current围绕红节点来移动保证平衡

  • 情况一 sibling为红色:

image

看到上述结构在23树中,C和E是一个3-节点, 只不过在红黑树中,将E节点描绘成了红色,这里先想办法将C转成红色,如果在23树中,其实很简单,只要将C往X上归并,C就可以变成红黑树中的红节点,如图:

image

在红黑树中,需要如何操作: 将E变为黑色普通节点,C变为红色节点即可。完整对应关系如下:
image

然后再对current的parent进行左旋,再将sibling移到current父节点的右节点。

  • 情况二 sibling为黑色,且其两个子节点为黑色:
    待删除节点C的两个节点AE都是黑色,并且右节点E的两个节点都是黑色,那就好说了,对应23树中可以将DEF提取到一个4-节点~ 如图:
    image

在红黑树中只要将sibling染红即可,然后将current移到current的父节点;这里解释一下为啥要将current往他的父节点移动:因为sibling变红了,代表sibling与其父节点在23树中是一个3-节点,是红黑中同级的的存在!所以要将current往他的父节点移动,以保证current和sibling还是兄弟不会乱伦。
虽然对应的红黑树中他们的关系变了,但是无所谓,红黑树只要保证平衡即可

  • 情况三 sibling为黑色,且sibling的右节点为黑色,也叫double black:
    • 先将sibling的左节点染黑
    • 将sib染红
    • 对sib做右旋
    • 将sibling移到current的parent的右节点 即可进入情况四
  • 情况四 sibling为红色,sibling的右节点为红色:
    • 将sibling染成与父节点一样的颜色
    • 将current的parent染成黑色
    • 将sibling的右节点染黑
    • 将current的parent进行左旋
    • 将current移到root(即终止循环结束调整)

以上是将要删除的节点的左节点视为current,如果将右节点视为current操作与上述的是对称的。 在上述各种情况中,最终需要的形态是4,与RedBlack.pdf的deleteMax情况相似;

  • sibling与current的关系如何保持 在上述的操作中,保持sibling和current是兄弟的操作:首先得看sibling是否为红色,如果是,那么current需要变为sibling的父节点,理由在上面有说;如果sibling是黑色,那么看current的,将sibling移到current的父节点的右节点上(这里是先视current为待删除节点的左节点而言);
  • 旋转 左旋和右旋何时需要?在一二三情况中:当sibling已经是红色了,需要再进一步转为情况4时;需要视情况将其进行旋转,使得情况能接近第四形态
  • 为啥要将123形态尽量转为第四形态
    第四形态,就是待删除节点的局部deleteMax标准形态,这种情况下删除不会影响整个树的平衡,所以123只是一个过渡,就像拼图过程中的一些技巧。

终上所述,delete就像是一个九宫格拼图,红色节点就是那一块空白,如何围绕这个空白,拼好这个拼图,前人都已经总结好了……

你看那个人好像一条狗啊

Read Next

数据结构—23树