红黑树是平衡的
Ash*_*yan 2 algorithm tree binary-tree red-black-tree
我正在研究红黑树,我正在阅读Cormen的"算法导论"一书.现在我尝试使用书中描述的伪代码 - RB-INSERT-FIXUP(T,z)创建数字为1-10的红黑树.这是截图
一切都很好,直到我在树中插入数字"6".根据伪代码我得到以下结果
你可以看到所有的红黑树要求都满足了,但我很困惑,因为我知道每一步都应该平衡红黑树.
我可以用"2"和"4"手动执行"左旋"程序并更改颜色.在这种情况下,我将得到以下结果,这是适当平衡的
所以我的问题是:
有没有不平衡的树可以吗？或者我在插入节点期间遗漏了什么？
这可以.红黑树是平衡的,但不一定完美.确切地说,红黑树的属性保证到叶子的最长路径(隐含的,未在图片中显示)最多是最短路径的两倍.最短的一个长度为2(2 - > 1 - >叶子),最长的长度为4(2 - > 4 - > 5 - > 6 - >叶子),因此不变量确实成立.
小智 5
它们不平衡，因为它们不满足平衡树属性：
如果对于每个节点，左子树中的内部节点数和右子树中的内部节点数最多相差 1，则二叉树是平衡的。
有些书称其为“近似平衡”，因为保证了添加/删除/搜索操作的对数时间。（平衡树是 AVL 树。）