Question

红黑树删除后的调整疑问

我可以对先直接 color[w] = BLACK，
然后对 p[x] 执行一次左旋，但为何书上面说要交换 w 和 p[x] 的颜色，然后再旋变成
假设原来：经过 x 的子树黑高度为 3，经过w 的子树黑高度为 2
删除后：经过 x 的子树黑高度为 2,经过w 的子树黑高度为 2，少了一个黑结点，违反性质 5)。（图 1）
所以我的解决办法是：增加经过 x 的子树黑高度(如图 2 所示)， 只需先 color[w] = BLACK， 然后 Left-Rotate(p[x]) 即可达成。但为何《算法导论》和很多书上都说是先调换 w 和 p[x] 的颜色，然后再 Left-Rotate(p[x])，那也就是变成了下面的图 3，但是这样的话，经过 x 的子树黑高度还是为 2，根本就达不到效果，为何要做这样的旋转呢？请高手解答呀。小弟分不多，还望不吝赐教！

Answer 1

首先，如您所说，从图 1 调整成图 2 后，会让经过 x 的黑高度加 1， 但是会另原来经过
left[w] 结点的黑高度加 1，这是不符合你的目的的。另外，虽然从图 1 到图 3 没有让经过 x 的黑高度加 1，但在随后的调整中会达到这个目的。综上所述，您的想法不正确！