红黑树中的insert_rebalance

Question

rb_tree中的insert_rebalance大多需要两次旋转？

我不这么认为！

“1” 是最新的插入节点。情况1：当前节点是红色的，父亲是红色的，叔叔是红色的。所以我们把父亲的颜色设置为黑色，叔父的颜色为黑色，父亲的颜色为红色，并将父亲的父亲设置为当前节点，并继续前进。

经过上述操作，再次是情况1。让我们想象一下：如果它总是变成情况1，旋转的数量不会只是2，也许更多。

我上面的陈述是正确的？我想确认我的想法。

Answer 1

如果插入位置是随机的，那么两次旋转相当不寻常。

从0节点开始：

B（0％需要两个旋转）

b R（25％需要两个旋转）

b RR（0％需要两个旋转）

b BB R（20％需要两个旋转）

b B B R R（0％需要两个旋转）

在其中两个旋转是可能的，也可以以填充树，而无需第二旋转的步骤。如果插入位置始终是最大值而不是随机数，那么两次旋转插入的数量为0，但您将在大约50％的时间内旋转一次。