红黑树平衡吗？
我正在研究红黑树，我正在读科门的“算法入门”一书。现在，我正在尝试创建数字1-10的红黑树，使用书中描述的伪代码-RB-插入-补丁(T，z)。这是截图
一切都很好，直到我把"6“号插入到树中。根据伪代码，我得到以下结果
正如你所看到的，所有的红黑树都满足了要求，但我很困惑，因为我知道红黑树应该在每一步上都保持平衡。
我可以手动执行“左旋转”程序与"2“和"4”，并改变颜色。在这种情况下，我将得到以下结果，这是适当平衡的
所以我的问题是：
有不平衡的树可以吗?还是我在插入节点时遗漏了什么？
回答 2
Stack Overflow用户
发布于 2015-02-15 21:04:52
这很好。红黑树是平衡的，但不一定完美。准确地说，红黑树的特性保证了通往叶子的最长路径(隐含的，没有显示在你的图片中)最多是最短路径的两倍。最短的叶长为2 (2 -> 1 ->叶)，最长的叶长为4 (2 -> 4 -> 5 -> 6 ->叶)，因此不变量保持不变。
Stack Overflow用户
发布于 2019-04-02 19:10:19
它们不平衡，因为它们不满足平衡树属性：
如果每个节点认为左子树中的内部节点数和右侧子树中的内部节点数最多相差1，则二叉树是平衡的。
有些书称其为“近似平衡”，因为它保证了对数时间的添加/删除/搜索操作。(平衡树是AVL树。)
https://stackoverflow.com/questions/28531044
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号