红黑树的最大不平衡度是多少？是高度/2吗？

Question

红黑树结构的目标是拥有一棵近似平衡的树。最大可能的不平衡程度是多少？

我认为它会是 1，因为如果我们在叶子之前的节点有红色节点，则会出现最大差异？

Answer 1

红黑树的一个属性是任何根到叶路径上的黑色节点的数量是常数。这个常数称为树的黑高度。

另一个属性是红色节点不能有红色子节点。这意味着，如果红黑树的黑色高度为 𝑘，那么最短可能的根到叶路径将有 𝑘（全黑）节点（包括黑色根），并且最长可能的根到叶路径同一棵树中的路径（因此也具有黑色根）将有 2𝑘 节点，其中黑色和红色节点交替，以红色（真实）叶子结束。

例如，这是一棵红黑树，黑色高度等于3：

              __B__
             /     \
           _R_      B
          /   \    / \
         B     B  B   B
        / \   / \
       R   B B   B
      / \
     B   B
    /
   R

最长的根到叶路径不能更长，除非我们在顶部添加红色根，但这也会使最短路径更长。

最后，我们应该注意，height的定义计算从根到叶的edges，而black height计算节点。

因此，如果黑红树的 height 给定为 ℎ，那么所有根到叶路径的长度（计算边）将至少为 ⌈(ℎ+1)/2⌉−1，即⌊ℎ/2⌋（最多 ℎ）