red black tree - insertion - z's uncle is red
为什么运算后节点γ(gamma,最顶层节点)的黑色高度不变?
我知道怎么解释为什么T1-T4的黑色高度在操作后是一样的。但是对于 gamma,我完全没有头绪。
有人有想法吗?
最佳答案
好的,Alpha 的插入已经完成,它被编码为红色。现在插入后,RB 树插入代码将检查红色和黑色之间的不平衡以确定是否必须进行旋转。检查后Beta节点变黑,Y节点变红,gamma节点变黑,从而保持树RB平衡,无需旋转。
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
请查看上面的 wiki 链接以获取颜色切换如何发生、原因以及如何帮助确定所需旋转的完整解释。
关于algorithm - 解释为什么插入(以及不同的情况)不会改变红黑树的黑色高度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52796583/