为什么RB-Tree不能是列表？
我的 rb 树有问题。根据维基百科，rb-tree 需要遵循以下规则：
- 节点要么是红色，要么是黑色。
- 根是黑色的。 （这条规则在某些定义中使用，而在其他定义中则不使用。由于根总是可以从红色变为黑色，但不一定反之亦然，因此该规则对分析影响不大。）
- 所有叶子都是黑色的。
- 每个红色节点的两个子节点都是黑色的。
- 从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。
众所周知，rb 树需要平衡，并且高度为 O(log(n))。 但是，如果我们插入一系列递增的数字（1,2,3,4,5...），理论上我们将得到一棵看起来像列表的树，其高度为 O(n) 及其所有节点黑色，这与上面提到的 rb-tree 属性并不矛盾。那么，我哪里错了？？
谢谢。
I have a problem with the rb-trees. according to wikipedia, rb-tree needs to follow the following:
- A node is either red or black.
- The root is black. (This rule is used in some definitions and not others. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
- All leaves are black.
- Both children of every red node are black.
- Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
As we know, an rb-tree needs to be balanced and has the height of O(log(n)).
But, if we insert an increasing series of numbers (1,2,3,4,5...) and theoretically we will get a tree that will look like a list and will have the height of O(n) with all its nodes black, which doesn't contradict the rb-tree properties mentioned above. So, where am I wrong??
thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您的示例与属性号 5 相矛盾，因此它不是有效的红黑树。
我们拥有的树是：
因此，为了到达最后两个叶子（节点
5的子节点），我们必须访问五个黑色节点（由每个b表示），要到达节点4下的叶子，我们必须访问四个黑色节点等。这意味着从根到某些包含不同数量黑色节点的后代有简单的路径，这会导致无效财产5.Your example contradicts property number 5, so it's not a valid Red-Black tree.
The tree we have is:
so to get to the last two leaves (the children of node
5), we have to visit five black nodes (represented by eachb), to get to the leaf under node4we have to visit four black nodes, etc. That means that there are simple paths from the root to some of this descendants containing a different number of black nodes, which invalidates property 5.文章的进一步内容：
A bit further down in the article: