algorithm - 是什么让这棵红/黑树变得沉重，它是否正确？

Question

所以我在搞乱红/黑树可视化器（https://www.cs.usfca.edu/~galles/visualization/RedBlack.html），并遇到了以下树（按 10、40 的顺序插入, 25, 35, 30, 45)。我知道 AVL 树不能在两条最短路径和最长路径之间存在高度差，但如果这同样适用于红/黑树，我会感到困惑。有人能指出使这棵树有效的特定属性，以便我加深对这种数据结构的理解吗？

Answer 1

红黑树的性质很简单：

1. 每个节点要么恰好有两个孩子，要么没有孩子。没有子节点的节点是叶节点，并且通常不会实际存储，因为它们没有标签。（在您的图表中，它们甚至没有显示出来。）
2. 根是黑色的。
3. 所有叶节点都是黑色的。
4. 红色节点的子节点是黑色的。
5. 每片叶子的黑色深度都是相同的。（黑色深度是指叶子路径中黑色节点的数量。）

这些特性足以保证最深的叶子不超过最浅叶子的两倍。这比 AVL 树的保证要宽松得多（其中两个叶子之间的深度差最多为一个），但足以保证最大深度是树的大小的对数。它是一个维护成本更低的不变量。