algorithm - 为什么 RB-Tree 不能是列表？

Question

我对 rb-trees 有疑问。根据维基百科，rb-tree 需要遵循以下内容：

1. 一个节点要么是红色的，要么是黑色的。
2. 根是黑色的。（这条规则在某些定义中使用，在其他定义中不使用。因为根总是可以从红色变为黑色，但不一定反之亦然，这条规则对分析几乎没有影响。）
3. 所有的叶子都是黑色的。
4. 每个红色节点的两个孩子都是黑色的。
5. 从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

众所周知，一个 rb-tree 需要平衡，并且高度为 O(log(n))。但是，如果我们插入一个不断增加的数字序列（1,2,3,4,5...），理论上我们会得到一棵看起来像列表的树，并且它的所有高度都为 O(n)节点黑色，这与上面提到的 rb-tree 属性并不矛盾。那么，我哪里错了？？

谢谢。

Answer 1

文章再往下一点：

插入开始于像二叉搜索树插入一样添加节点并将其着色为红色。

Answer 2

您的示例与属性编号 5 相矛盾，因此它不是有效的红黑树。

我们拥有的树是：

b(1, nil, b(2, nil, b(3, nil, b(4, nil, b(5, nil, nil)))))

所以要到达最后两个叶子（ node 的孩子5），我们必须访问五个黑色节点（由 each 表示b），要到达节点下的叶子，4我们必须访问四个黑色节点，等等。这意味着有从根到包含不同数量黑色节点的某些后代的简单路径，这使属性 5 无效。