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

Question

red black tree - insertion - z's uncle is red

为什么运算后节点γ(gamma，最顶层节点)的黑色高度没有变化？

我知道怎么解释为什么T1-T4的黑色高度在操作后是一样的。但是对于伽玛，我完全没有头绪。

有人有想法吗？

Answer 1

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

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

请参阅上面的 wiki link 以获得颜色切换如何发生的完整解释以及为什么以及它如何帮助确定需要 rotation/s。