红黑BST的基本操作过程

红黑BST是2-3查找树的一种具体实现方式,它将2-3查找树中的3-节点视为两个相连的2-节点,并对链接设定了颜色(红,黑)属性以描述这些特殊的2-节点。这样就不用再为3-节点定义专门的数据结构,基础操作直接复用BST的逻辑即可,基于基础操作可方便地实现更多更高级的操作。

红黑BST的基本设定:

  • 红色链接一律为左链接
  • 不可出现同时与两条红链接相连的节点

《2-3查找树的基本操作过程》中讨论删除操作的时候,把3-节点视为两个2-节点相连,且规定后来的那个节点为子节点,于是得到了下图。此时的链接就不都是左链接。

一个节点与两条红色链接相连的情况,对应于2-3查找树来说,就是在插入节点时,结合出来的4-节点。它是一种临时状态,一旦出现,下一步就是将其拆解。

在插入节点的时候,红色右链和两条红链的情况会经常出现。将右链变为左链,将两条红链拆解,这些都需要所谓的“旋转”操作来完成。

下面还是使用一组key来分别演示各个操作过程,key:{ 9, 3, 8, 1, 2, 10, 4, 5, 7, 6 },红黑BST的基本操作中,除了put(key),del(key),get(key)之外,至少还要有“旋转”操作,其参数应该是旋转方向和待旋转的的节点(能够取到该节点的一个地址)。

rotate(node, direction):对某个节点进行旋转,其实是让这个节点“退位”,让其某个子节点“上位”,亲子地位对调。既然是旋转,就只有两个方向,顺时针(右旋),逆时针(左旋)。不同的旋转方向会让不同的孩子(左或右孩子)上位。

想让哪个孩子“上位”,就以哪个孩子为轴心进行旋转。

让左孩子“上位”:以左孩子为轴,做右旋转:

让右孩子“上位”:以右孩子为轴,做左旋转:

以上两种情况也分别是红色右链和双红链接的处理过程。当然,双红链接还有一种情况就是中间节点恰好是子树的root节点,此时不需要旋转,只要改变链接颜色即可。

put(key):插入一个键值为key的节点。在普通BST的插入逻辑(先找空链接,再将新节点挂入)中附加了链接颜色变化和旋转等操作。

依次插入上面的那10个key:

  • put(9)
    首个节点,没什么特别的地方。

  • put(3)
    找到空链接,挂入新节点,链接变色,产生3-节点。

  • put(8)
    找到空链接,挂入新节点,出现右红链接,旋转化解。又出现双红链接(4-节点),通过旋转,链接变色,进行化解。

  • put(1)
    找到空链接,挂入新节点,链接变色,产生3-节点。

  • put(2)
    找到空链接,挂入新节点,出现右红链接,旋转化解。又出现双红链接(4-节点),再次旋转,改变链接颜色。

  • put(10)
    找到空链接,挂入新节点,链接变色,产生3-节点。 此时出现了右红链接,旋转一次,进行化解。

  • put(4)
    产生3-节点,出现右红链接,旋转化解。

  • put(5)
    刚插入新节点的时候,出现双红链接的局面,此时中间节点恰好是子树的root节点,此时不需要旋转,只进行链接颜色转换即可。颜色转换完成后,即产生了一个右红链接,此时再进行旋转,将其化解掉。化解了红色右链之后,又出现了双红链接,此时再进行旋转,变色处理,得到最终形状。

  • put(7)
    产生3-节点,出现右红链接,旋转化解。

  • put(6)
    挂入新节点,出现右红链接,旋转化解。然后出现双红链接,再旋转,变色,进行化解。

    至此,这颗红黑BST就生长完成了,它与一颗2-3查找树相对应:

    将红链接视为内部链接,只看黑链接,红黑BST是完美平衡的。

del(key)和get(key)的操作方法与普通BST的一致,不再做操作演示

参考:《普通BST的基本操作过程》