学习《算法导论》红黑树后的一些个人理解

前段时间看了算法导论红黑树这一章节,虽然能看懂RB-INSERT-FIXUP(T,z)和RB-DELETE-FIXUP(T,x)两个方法,但是过两天再回来看的时候又要自己从头推导起来了(毕竟insert操作有3三种情况,delete操作有四种情况,其实多看几次也就记住了),所以想总结一些更简单的规律以便于理解记忆,如果有错误的地方,希望大家指出来。

先贴上红黑树的性质,毕竟红黑树的核心FIXUP方法的作用就是让红黑树新增或者删除一个节点后重新满足红黑性质,所以一步一步跟着FIXUP方法走,看看操作的每一步破坏了哪些性质,又重新满足了哪些性质,有利于我们发现规律。

红黑性质:

  1. 每个节点或是红色的,或是黑色的。
  2. 根节点是黑色的。
  3. 每个叶节点(NIL)是黑色的。
  4. 如果一个节点是红色的,则他的两个子节点都是黑色的。
  5. 对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。

无论是RB-INSERT-FIXUP(T,z)方法还是RB-DELETE-FIXUP(T,x),结束while循环的条件有两种:

  1. 保证下层满足红黑性质的同时指针上移(z、x的指针),将问题抛给父节点或者爷节点。
  2. 通过旋转操作后满足了所有的红黑性质。

下面是《算法导论》中的原图:
image
image

第一种情况本身不难理解,具体表现为RB-INSERT-FIXUP(T,z)情况1和RB-DELETE-FIXUP(T,x)情况2:
RB-INSERT-FIXUP(T,z)情况1中当新增节点z的父节点和叔父节点均为红色节点时将他们置为黑色,并且将z的爷节点置为红色,一黑一红的变换是为了让原来的z节点与其父节点满足条件4并且保证不破坏性质5,至于将爷节点变为红色会不会让爷节点与上层节点产生新的性质4的问题,这个就是爷节点的事情了,所以最后将指针z指向爷节点。

RB-DELETE-FIXUP(T,x)情况2中,当x节点(实际被删除节点的后继节点)的兄弟节点w和w的两个自己子节点都为黑色时,将w置为红色,x指针上移指向x的父节点,将w节点由黑变红是为了让从root节点经过w到叶子节点的这条路径黑色节点数减1,这么做的目的是为了让x(x携带一个隐藏的黑色)指向父节点的时候,经过w的路径能够重新满足性质5(黑色节点减1后又加1),至于w变红会不会破坏红黑性质4,首先w的两个子节点都为黑,但是其父节点(新的x节点)可能会是红色,这个时候只需要将x隐藏的黑色显示出来,也就是直接将新的x节点由红变黑,然后删掉x指针就能满足所有的红黑性质了。

第二种情况:旋转+颜色变换
通过观察RB-INSERT-FIXUP(T,z)情况2、情况3,RB-DELETE-FIXUP(T,x)情况1、情况3我们可以发现,忽略颜色转变的话与普通平衡二叉树旋转操作无异,但是如加上颜色变换的话,又能发现都是红色节点取代父节点的位置和颜色,然后把父节点置为红色的过程,如下图所示:(RB-DELETE-FIXUP(T,x)情况4后面会单独解释)

灰色节点代表节点既可以为红色也可以为黑色,正方形节点代表除了本身颜色之外还含有一个隐藏的黑色(双色节点,即RB-DELETE-FIXUP(T,x)中x指针指向的节点)

image

如上图一般情况所示,A为红色,对B进行右旋,A取代B的颜色,并将被取代颜色了的B置为红色:
Right-Rotate(B);
A.color = B.color;
B.color = Red;

转换前从根节点到α、β、γ、δ节点路径上黑色节点个数为:
(X表示转换前根节点到B节点路径上的黑节点的个数,包括root节点不包括B节点)

int count(x){
return   x.color == blank ? 1 : 0;
}

α:X+count(B)+count(α)
β:X+count(B)+count(β)
γ:X+count(B)+count(C)+count(γ)
δ:X+count(B)+count(C)+count(δ)

转换后从根节点到α、β、γ、δ节点路径上黑色节点个数为:
α:X+count(A)+count(α)
β:X+count(A)+count(β)
γ:X+count(A)+count(C)+count(γ)
δ:X+count(A)+count(C)+count(δ)

对比上面转换前后黑色节点个数可以发现,旋转+红色子节点取代父节点颜色  的过程中性质5并不会被破坏,因为A取代了B的颜色,所以转换后count(A)等于转换前count(B)。至于会不会破坏性质4,取决于旋转+红色子节点取代父节点颜色 操作的时机,比如当B转换前就为红色(RB-INSERT-FIXUP(T,z)情况2),那么本身就不满足性质4,操作后不满足也正常;当C转换前为红色时,转换后也不满足性质4,但是仔细观察RB-INSERT-FIXUP(T,z)和RB-DELETE-FIXUP(T,x)就会发现,采取 旋转+红子节点取代父节点颜色 操作时,另一个子节点都是为黑色(RB-INSERT-FIXUP(T,z)情况3,RB-DELETE-FIXUP(T,x)情况1、3)。

通过上面两种情况分析,已经涵盖了七种情况中的六种,除了RB-DELETE-FIXUP(T,x)情况4,通过类比发现实际上这种情况采取的是 旋转+黑色子节点取代父节点颜色 操作,但我们还不知道这种操作会不会破坏红黑性质,所以我们先假设 旋转+黑色子节点取代父节点颜色 和 旋转+红色子节点取代父节点颜色 操作方式一模一样 。
image
如上图一般情况所示,A为黑色,对B进行右旋,A取代B的颜色,并将被取代颜色了的B置为红色:

Right-Rotate(B);
A.color = B.color;
B.color = Red;

转换前从根节点到α、β、γ、δ节点路径上黑色节点个数为:
α:X+count(B)+1+count(α)
β:X+count(B)+1+count(β)
γ:X+count(B)+count(C)+count(γ)
δ:X+count(B)+count(C)+count(δ)

转换后从根节点到α、β、γ、δ节点路径上黑色节点个数为:
α:X+count(A)+count(α)
β:X+count(A)+count(β)
γ:X+count(A)+count(C)+count(γ)
δ:X+count(A)+count(C)+count(δ)

对比上面转换前后黑色节点个数可以发现,旋转+黑色子节点取代父节点颜色  的过程中性质5被破坏了,从根节点经过α、β节点的路径黑色节点数减1。为了防止性质5被破坏,我们可以做如下操作:
image
给α、β一个隐藏的黑色节点能够保证性质5不被破坏,对应RB-DELETE-FIXUP(T,x)中的操作就是,既将x的指针指向α,又将x的指针指向β,然而此时好像并没有什么卵用,但是假如此时x也指向节点C的话,即C节点本身也是正方形节点的话,就不一样了:
image
上图变换思想主要就是父节点增加一个黑色,子节点减去一个黑色,保证性质5不被破坏。看起来好像还是没什么卵用,然而当我们回过头来看看RB-DELETE-FIXUP(T,x)情况4的时候,会发现x指向的A节点刚好是我们上面需要的那个被x指向的节点C:
image

为了对比起来更加的直观,下面给出进行 左旋+黑子节点取代父节点颜色 的转换图:
image
假设节点A本身也含有一个隐藏的黑色节点(x刚开始指向A):
image
通过对比发现:RB-DELETE-FIXUP(T,x)情况4操作后直接满足了所有的红黑性质,退出循环,但是旋转+黑子节点取代父节点这种方式只是将指针上移,与我们讨论的第一种情况将问题抛给上层节点差不多。看起来RB-DELETE-FIXUP(T,x)情况4的操作更加方便,但是RB-DELETE-FIXUP(T,x)情况4是有条件限制的,即刚开始x节点的兄弟节点的右子节点必须为红色,对照上图也就是δ节点刚开始必须为红,这也是RB-DELETE-FIXUP(T,x)情况4看起来不符合旋转+黑子节点取代父节点颜色的根本原因:如下图所示:
image
假设x刚开始指向A:
image
一个红色的正方形节点代表红色节点本身包含一个隐藏的黑色,所以可以直接将其置为黑色,不会破坏任何红黑性质。所以我们可以知道RB-DELETE-FIXUP(T,x)情况4的转换图如下:
image

           (黑子节点取代过程图)

所以,旋转+颜色取代的方式是可以解释RB-DELETE-FIXUP(T,x)情况4的,得到不同结果是因为其特殊的限定条件兄弟节点的右子节点必须为红色,导致向上传递隐藏黑色节点的过程中直接就能满足所有红黑性质,不需要接着循环了。

再回头来看RB-INSERT-FIXUP(T,z)、RB-DELETE-FIXUP(T,x)可以发现,除了RB-INSERT-FIXUP(T,z)情况1,RB-DELETE-FIXUP(T,x)情况2,其他情况都能通过旋转+颜色取代的方式来解释,不同的只是红子节点取代父节点还是黑子节点取代父节点。(实际上RB-DELETE-FIXUP(T,x)情况2也能通过旋转+黑子节点取代父节点颜色的方式处理,但是多一次旋转操作,增加了复杂度)

旋转+颜色取代的限制:

  1. 旋转+红子节点取代操作如果原本就满足所有的红黑性质的话,那么转换后也是满足的。无限制条件。
  2. 旋转+黑子节点取代操作想要跳出循环的话(RB-DELETE-FIXUP情况4的效果),如果是左旋那么取代子节点的右子节点必须为红,如果是右旋的话,那么其左子节点必须为红,否则如下图RB-DELETE-FIXUP(T,x)情况3所示:

image
RB-DELETE-FIXUP(T,x)情况3是进行旋转+红子节点取代父节点的操作转换成情况4,这里不能直接进行左旋B节点,D取代B的原因就是因为D的右子节点E不为红(这里不是不能直接黑子取代,而是黑子取代的意义不大),如果直接进行旋转+黑子节点取代父节点颜色 操作的话最终的结果是由于E本身就是黑色的无法显示我们附加给它的一个黑色颜色,但是也可以通过给C节点一个x指针的方式(同时不能将B节点隐藏的黑色节点显示出来)的方式将问题抛给上层节点解决。也就是上面的黑子节点取代过程图的最后一步,不将B、E节点转换成黑色,将这两个节点的正方形取消,同时给一个x指针指向D。

评论

暂无评论