重念一次早該補起來的「資料結構與演算法」。這篇筆記下 AVL Tree 是如何旋轉維持平衡的。
![[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74](https://smlpoints.com/wp-content/uploads/notes-theideaofalgorithm-javascript-1.jpg "[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74")
課程相關資訊
[連結]：https://hiskio.com/en/courses/572/lectures/146360
本篇範圍：Chapter 14
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Rotation 分為 4 種
1. 左旋轉 (Left Rotation, LL)
當某個節點的右子樹高度比左子樹高度大兩個以上時，需要進行左旋轉。
步驟：
- 讓右子節點成為新的根節點。
- 將新的根節點的左子節點變成原來根節點的右子節點。
- 將原來的根節點變成新的根節點的左子節點。
|
1 2 3 4 5 6 7 8 9 10 |
a \ b \ c 左旋轉後： b / \ a c |
2. 右旋轉 (Right Rotation, RR)
當某個節點的左子樹高度比右子樹高度大兩個以上時，需要進行右旋轉。
步驟：
- 讓左子節點成為新的根節點。
- 將新的根節點的右子節點變成原來根節點的左子節點。
- 將原來的根節點變成新的根節點的右子節點。
|
1 2 3 4 5 6 7 8 9 10 |
c / b / a 右旋轉後： b / \ a c |
3. 左右旋轉 (Left-Right Rotation, LR)
當某個節點的左子節點的右子樹高度比左子樹高度大時，需要先對左子節點進行左旋轉，再對根節點進行右旋轉。
步驟：
- 對左子節點進行左旋轉。
- 再對根節點進行右旋轉。
|
1 2 3 4 5 6 7 8 9 10 |
c / a \ b 左右旋轉後： b / \ a c |
4. 右左旋轉 (Right-Left Rotation, RL)
當某個節點的右子節點的左子樹高度比右子樹高度大時，需要先對右子節點進行右旋轉，再對根節點進行左旋轉。
步驟：
- 對右子節點進行右旋轉。
- 再對根節點進行左旋轉。
|
1 2 3 4 5 6 7 8 9 10 |
a \ c / b 右左旋轉後： b / \ a c |
