左右旋转后，为何要重新设置根节点的颜色？

来源：13-6 颜色翻转和右旋转

阿阳2017

2023-01-25

老师好，这节课的右旋转和左旋转操作后，都有一个维护节点颜色的操作：
x.color = node.color;
视频中讲解的是：新的根节点是x，其颜色应该和以前的根节点node的颜色一样。
这步操作不太明白。

写回答

1回答

liuyubobobo

2023-01-26

因为其实只有左旋转和右旋转两种情况，所以其实分类看着两种情况旋转后的心得根节点 x 的颜色就好。

==========

只有红节点在右子树才会左旋转。

左旋转以后，如果之前 node 是黑色，新的 x 也是黑色，这本质其实对应 2-3 树中的一个 3 节点，只不过子左倾红黑树中维持红色节点一定要在左边而已；

左旋转之后，如果之前的 node 是红色，新的 x 也是红色，此时，要进入右旋转继续进行调整，这本质对应了 2-3 树中产生了一个临时的 4 节点，向上继续调整。

右旋转的情况，只有黑节点的左孩子是红节点，这个左孩子的左孩子还是红节点的时候，才会发生。调整以后，新的 x 一定还是黑色，且其左右孩子是红节点，然后做 flip color。也就是右旋转之后做颜色翻转，完全对应了 2-3 树中对临时 4 节点的调整过程。

==========

课程中这张 ppt 的图非常好的总结了这两种旋转后树的局部形态（在第七小节）：在我看来这张图是红黑树（更准确地说是左倾红黑树）维持性质的关键：

//img.mukewang.com/szimg/63d2754109b3032d18941026.jpg

从上述分析可以看到：旋转以后（不管哪个旋转），最中心的根节点的颜色和之前根节点的颜色是一致的。

继续加油！：）

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 2

回答 1

回答 1

回答 2

回答 1