我正在研究红黑树，正在阅读Cormen的“算法简介”书。现在，我尝试使用书中描述的伪代码RB-INSERT-FIXUP(T，z)创建编号为1-10的红黑树。这是屏幕截图
一切正常，直到我在树中插入数字“6”。根据伪代码，我得到以下结果
如您所见，所有红黑树的要求都得到了满足，但是我感到困惑，因为我知道红黑树应该在每个步骤上保持平衡。
我可以使用“2”和“4”手动执行“向左旋转”过程并更改颜色。在这种情况下，我将得到以下结果，并得到适当的平衡
所以我的问题是:
拥有不平衡的树可以吗？还是在插入节点期间错过了某些东西？
最佳答案
这可以。红黑树是平衡的，但不一定完美。确切地说，红黑树的属性可确保到达叶子的最长路径(隐式，未在图片中显示)最长为最短路径的两倍。最短的一个长度为2(2-> 1->叶子)，最长的一个长度为4(2-> 4-> 5-> 6->叶子)，因此不变式成立。