插入后红黑树黑高增加

Question

我知道，当红红违规传播到根部时，RB树的黑色高度在插入后会增加，然后根部会被着色为红色，然后重新着色为黑色，这会导致树的黑色高度增加。

但是我一直在尝试举出一些例子来证明上述内容，我能想到的唯一场景是一棵具有交替级别的完美树，从黑根开始（当然）并以红叶级别结束.

这种树是唯一在插入后经历黑色高度增加的树吗？如果没有，可以给我其他例子吗？

谢谢！

Answer 1

我能想到的唯一场景是一棵具有交替层次的完美树，

树不一定是完美的。从（黑色）根到插入的（红色）叶子的路径必须具有以下特征：

• 该路径上的节点具有交替颜色，除了插入的节点及其父节点均为红色。

• 该路径中的每个红色父节点都有一个红色兄弟节点。

所以下面的树也是一个例子，插入

R*

会导致黑高增加，尽管它不是完美的树：

          _______B______
         /              \
      __R__             _R_
     /     \           /   \
    B      _B_        B     B
   / \    /   \      / \   / \
  B   B  R     R    B   B B   B
        / \   / \
       B   B B   B
          / \
         R   R
          \
           R*

红色违规将在树上级联并导致：

          _______B______
         /              \
      __B__             _B_
     /     \           /   \
    B      _R_        B     B
   / \    /   \      / \   / \
  B   B  B     B    B   B B   B
        / \   / \
       B   R B   B
          / \
         B   B
          \
           R*