紅黑樹中的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％的時間內旋轉一次。