algorithm - 解释为什么插入（以及不同的情况）不会改变红黑树的黑色高度

Question

红黑树-插入-z的叔叔是红色的

为什么节点γ（gamma，最顶层节点）的黑色高度在操作后没有变化？

我知道如何解释为什么 T1 - T4 的黑色高度在操作后是相同的。但对于伽玛，我完全不知道。

有人有想法吗？

标签： algorithmbinary-treebinary-search-treered-black-treered-black-tree-insertion

Answer 1

好的，Alpha 的插入完成，它被编码为红色。现在插入后，RB 树插入代码将检查红色和黑色之间的不平衡，以确定是否必须进行旋转。检查后 Beta 节点变为黑色，Y 节点变为红色，gamma 节点变为黑色，从而保持树 RB 平衡，无需旋转。

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

请参阅上面的 wiki 链接以获取有关颜色切换如何发生以及它为什么以及如何帮助确定所需旋转/秒的完整说明。