關於AVL旋轉

Question

我閱讀有關數據結構和算法AVL樹由馬克·艾倫Wesis

假設節點重新平衡是X.有4例，我們 可能必須解決（兩個是其他兩個鏡像）： 插入X的左側子樹的左側子樹中，插入 X的左側子樹的右側子樹，右側子樹的 子樹中的插入X ，或在X的右側子樹的右子樹 中插入。

平衡通過樹輪旋轉恢復。

以下是我對上述文本片段的疑問。

1. 作者用其他兩個鏡像表示的意思是什麼？
2. 什麼是單旋轉和雙旋轉的對稱情況？

感謝

Answer 1

假設要插入的節點是一書中說，有4例。讓我們以一個在那裏我是X的左子的左子：

X 
/\ 
    ? ? 
/\/\ 
I ? ? ? 

「鏡子」的，這是當我是X的右孩子的右子：

X 
/\ 
    ? ? 
/\/\ 
? ? ? I 

這是一個「鏡子」的原因是，你必須爲兩種情況做的旋轉是相同的，只是左右顛倒。另外兩種情況也是如此，其中我是X的右側孩子的左側孩子，而我是X的左側孩子的右側孩子。

至於你的第二個問題，這個想法是一樣的。在對稱情況下（即鏡像情況），您可以進行相同的旋轉，只需左右顛倒即可。