※ 引述《FRAXIS (喔喔)》之铭言:
: 删除其实也类似,先找到 safe node ,以下变色,然后旋转,
: 只是 safe node 的条件稍微复杂一些,有人想知道的话我再写
: 一篇吧。
在删除的时候,会先需要从 root 往下开始 traverse 去找要删除的节点,如果
要删除的节点有两个子节点,那就把删除节点的 successor 的资料复制到要删除
的节点上,接着再把 successor 删除,所以在不失一般性的情况下,可以假设
要被删除的节点只有一个子节点。
(在实务上不能把 successor 的资料复制到要删除的点上,然后把 successor
删除,原因是可能有指标(iterator)指向 successor ,这样作会导致这些指标
莫名其妙的就 invalid 了,所以需要多一些步骤,这也是为什么 CLRS 上的删除
比较复杂的原因)
为了讨论方便,我们把 root 到要删除节点的搜寻路径叫做 p ,而 safe node
就是在 p 上,距离删除节点最近的红色点,或是子代和孙代有红色点的黑点。
如果 p 上没有这种点的话,root 就是 safe node 。
当节点被删除时,如果删除节点有非 sentinel 的子节点,就把非 sentinel 子节
点上移,不然就把 sentinel 子节点上移,此时有几种情况:
删除节点颜色 子节点颜色
红 红 不存在
红 黑 子节点直接上移,不违反红黑树性质
黑 红 子节点上移之后变为黑色,不违反红黑树性质
黑 黑 子节点上移,但是因为黑色点减少,违反红黑树性质
因为只有最后一个情形才违反红黑树性质,所以我就只讨论这情况。在这个时候
因为删除节点的另一个子节点是 sentinel ,而上移的节点又是黑色,根据红黑
树的限制,上移的节点必为 sentinel 。换句话说,只有删除黑色的叶节点才可
能违反红黑树性质。
接下来可以把 p 画出来,有几种可能:
情况 1: safe node 是红点且有黑子黑孙
safe node 删除点
root - .. - 红 - 黑 - 黑 - 黑 - 黑 - .. 黑 - (黑) - 黑 (sentinel)
| | | | | | |
黑 黑 黑 黑 黑 黑 黑 (sentinel)
子 子 子 子 子
黑 黑 黑 黑 黑
孙 孙 孙 孙 孙
情况 2: safe node 是红点且有红孙
情况 3: safe node 是黑点且有红子或红孙
就不画了。
而调整的方式就是从 safe node 以下,先变色。
情况 1 ,变完色就成为
safe node
root - .. - 黑 - 黑 - 黑 - 黑 - 黑 - .. 黑 - 黑 (sentinel)
| | | | | |
红 红 红 红 红 红
这样就变成合法的红黑树了。而情况二和三则是变完色之后要再旋转,旋转的判断
有三个 case ,详情请参考 CLRS 。
: 这技巧也被用在 WAVL tree 上,有兴趣的可以研究。
: https://en.wikipedia.org/wiki/WAVL_tree
WAVL 在 Goodrich and Tamassia 的 Algorithm Design and Applications
有详细介绍。
WAVL 的复杂度与红黑树一模一样,只需要 O(1) 旋转,
rebalance 是 amortized O(1)。
稍有不同的地方是在旋转次数,插入时 WAVL 和红黑树
都顶多转两次,但是删除时红黑树最多转三次,WAVL
最多只会转两次。