删除的原理:
算法导论上的删除算法把两种情况同时进行处理,确实很有技巧。红黑树的删除除了最后需要根据对于删除结点的颜色来判断是否需要进行调整外,和普通的二叉查找树没有区别,这里稍微做一下分析。
复制代码 代码如下:
RB-DELETE(T, z) // 情况1 || 情况2
if left[z] = nil[T] or right[z] = nil[T] // z最多一个孩子时 || z有两个孩子时
then y ← z // 令y=z || 令y是z后继(此时y必然不是z的右孩子)
else y ← TREE-SUCCESSOR(z) //===============================================================================
if left[y] ≠ nil[T] // 令x为y的孩子或哨兵 || 令x是y的右孩子(x必然不为左孩子,否则y不可能是z的后继)
then x ← left[y] // || 将来x会代替y的位置
else x ← right[y] //================================================================================
p[x] ← p[y] //
if p[y] = nil[T] //
then root[T] ← x // x与x的新父亲之间建立关系
else if y = left[p[y]] //
then left[p[y]] ← x //
else right[p[y]] ← x //=================================================================================
if y !≠ z // ||
then key[z] ← key[y] // 删完后整体上移 || 替代,用于替代的原结点删除
copy y's satellite data into z // ||
if color[y] = BLACK // ||
then RB-DELETE-FIXUP(T, x) // ||
return y
删除后,如果删除的结点是黑色,可能会造成性质2、4、5的违反。调整算法思想是使得代替y的x多染一层黑色而成为红黑或二重黑色结点。这个处理只是用指针x标示,并不用改变结点color域的内容。调整算法按8种情况,其中两两对称,只描述4种。
用w表示x的兄弟。
情况1为w红。此时调整w为黑,p[x]为红,以p[x]左旋,w指向x的新兄弟,此时则成为情况2或3或4。
情况2为w黑,且w的两个孩子均黑。此时把w染红,令p[x]成为新的x。这相当于把x剥离了一层黑色,使这层黑色上移。
情况3为w黑,w的左孩子为红,右孩子为黑。这时交换w和左孩子颜色,并对w右旋,此时成为情况4。
情况4为w黑,w有孩子为红。这时使w成为p[x]的颜色,p[x]置为黑色,w的右孩子置为黑,对p[x]左旋。令x为根。这时相当于把原先x上的一重黑色传给了其父亲并于它一起下移,而w代替了其父亲原先的颜色和位置。这是不存在红黑结点或二重黑结点。
每次处理都判断x是否为根且x是否为黑。x不为根且为黑时才代表有红黑结点或二重黑结点,需要进行新一轮循环。循环结束后把根染黑就结束了。