在紅黑樹上旋轉

Question

我試圖找出在重新平衡完成時紅黑樹中的旋轉。我明白爲什麼輪換髮生，但我不明白它是如何完成的。此外，像LL，RR，LR和RL這樣的中間旋轉是如何完成的，直到結果爲止，並且如果有人告訴我關於何時執行這些旋轉中的任何一個的任何經驗法則，我也會感激。這裏是旋轉：

Rr(2) is the case when black node deficiency is in right child of "py" i.e. 
"y" and grandchild of "v" are 2 red nodes i.e. "b" and "x" 

Answer 1

您可以嘗試打破操作成不同的旋轉，以瞭解紅黑樹旋轉以更好的方式。左傾紅黑BST只有3種基本操作。操作按照本幻燈片中列出的順序執行。

此外，紅黑樹，你已經證明是不正確的，因爲它違反了一個紅黑樹的條件。即。從根到葉的每條路徑必須具有相同數量的黑色邊緣。但是在最終的樹中，從x到c的路徑有2個黑色邊，而從x到a的路徑有1個黑色邊。我建議您從here瞭解更多關於自我平衡BST和紅黑BST的信息。

PS。我不擁有幻燈片。它已經從Robert Sedgewick的coursera課程中學習。