红黑树是否平衡
Is Red-Black tree balanced
我正在研究红黑树，我正在阅读 Cormen 的 "Introduction to Algorithms" 书。现在，我正在尝试使用书中描述的伪代码创建编号为 1-10 的红黑树 - RB-INSERT-FIXUP(T, z)。这是屏幕截图
一切都很好，直到我将数字“6”插入树中。根据伪代码我得到以下结果
如你所见，所有的红黑树要求都满足了，但我很困惑，因为我知道红黑树在每一步都应该是平衡的。
我可以用“2”和“4”手动执行 "left-rotate" 程序并更改颜色。在那种情况下，我将得到以下结果，该结果已适当平衡
所以我的问题是：
有不平衡的树可以吗？或者我在插入节点时遗漏了什么？
这很好。红黑树是平衡的，但不一定是完美的。确切地说，红黑树的属性保证到叶子的最长路径（隐含的，未显示在您的图片中）最多是最短路径的两倍。最短的长度为 2（2 -> 1 -> 叶子），最长的长度为 4（2 -> 4 -> 5 -> 6 -> 叶子），所以不变量成立。
不平衡，因为不满足平衡树属性:
A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
有些书称它为"approximately balanced"，因为保证了对数时间add/delete/search运算。 （平衡树是 AVL 树。）
我正在研究红黑树，我正在阅读 Cormen 的 "Introduction to Algorithms" 书。现在，我正在尝试使用书中描述的伪代码创建编号为 1-10 的红黑树 - RB-INSERT-FIXUP(T, z)。这是屏幕截图
一切都很好，直到我将数字“6”插入树中。根据伪代码我得到以下结果
如你所见，所有的红黑树要求都满足了，但我很困惑，因为我知道红黑树在每一步都应该是平衡的。
我可以用“2”和“4”手动执行 "left-rotate" 程序并更改颜色。在那种情况下，我将得到以下结果，该结果已适当平衡
所以我的问题是：
有不平衡的树可以吗？或者我在插入节点时遗漏了什么？
这很好。红黑树是平衡的，但不一定是完美的。确切地说，红黑树的属性保证到叶子的最长路径（隐含的，未显示在您的图片中）最多是最短路径的两倍。最短的长度为 2（2 -> 1 -> 叶子），最长的长度为 4（2 -> 4 -> 5 -> 6 -> 叶子），所以不变量成立。
不平衡，因为不满足平衡树属性:
A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
有些书称它为"approximately balanced"，因为保证了对数时间add/delete/search运算。 （平衡树是 AVL 树。）