红黑树平衡了吗 [英] Is Red-Black tree balanced

问题描述

我正在研究红黑树，正在阅读Cormen的算法简介这本书。现在，我尝试使用书中描述的伪代码RB-INSERT-FIXUP（T，z）创建数字1-10的红黑树。这是屏幕快照

一切都很好，直到我在树中插入数字 6。根据伪代码，我得到以下结果

我可以手动执行 2和 4的左旋转过程并更改颜色。在那种情况下，我将得到以下结果，该结果是适当平衡的

所以我的问题是：

是不平衡的树？还是在插入节点期间错过了什么？

解决方案

这很好。红黑树是平衡的，但不一定完美。确切地说，红黑树的属性可确保到叶子的最长路径（隐式，未在图片中显示）最长为最短路径的两倍。最短的一个具有长度2（2-> 1->叶子），最长的一个具有长度4（2-> 4-> 5-> 6->叶子），因此不变量确实成立。

I am studying red-black trees and I am reading the Cormen's "Introduction to Algorithms" book. Now I am trying to create red-black tree with numbers 1-10 by using the pseudo-code described in the book - RB-INSERT-FIXUP(T, z). Here is the screenshot

Everything was fine until I inserted number "6" into the tree. According to pseudo-code I get the following result

As you can see all red-black tree requirements met, but I am confused because I know that red-black tree should be balanced on each step.

I can manually perform "left-rotate" procedure with "2" and "4" and change the colours. In that case I will get the following result, which is balanced appropriately

So my question is:

Is that all right to have unbalanced tree?, or I missed something during insertion nodes?

解决方案

This is fine. Red-black trees are balanced, but not necessarily perfectly. To be precise, properties of red-black tree guarantee that the longest path to the leaf (implicit, not shown in your picture) is at most twice as long as the shortest. Shortest one has length 2 (2 -> 1 -> leaf), longest one has length 4 (2 -> 4 -> 5 -> 6 -> leaf), so the invariant does hold.

这篇关于红黑树平衡了吗的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！