[資料結構] CH8. AVL Trees

簡介

• AVL Trees是屬於Binary Search Trees的一種，也就是說，它必須符合Binary Search Trees的所有特性。
• 除了Binary Search Trees的特性外，AVL還必須符合以下特性：
  ※每一個node的左子樹高度-右子樹高度只能是-1、0、1。
  • 因為上述特性，AVL Trees是一種平衡樹。
• 由於整個樹不會長歪，在搜尋時的速度會更快。
• 一個AVL的例子：

實作AVL Trees

• 為了維持樹的平衡，在插入、刪除時需要進行調整。

插入

1.照一般Binary Search Trees的方法插入資料。
2.向上檢查高度是否符合AVL限制。
3.如果符合，結束。
4.如果不符合，旋轉。

• 前面的插入因為同前面章節的insert，故跳過。
• 從你插入資料的node開始檢查，如果到head node都沒問題就OK。
• 如發現該節點的子樹高度差>1，請往下找兩層，並根據這兩層的左右方向，進行LL/RR/LR/RL旋轉。

LL旋轉

• 下圖是一個LL旋轉的例子；插入一個新資料"6"之後，導致樹的不平衡。
• 經過向上檢查，18 OK、36 OK，然而在45的地方發現高度差大於一了。
• 檢查路徑後，因為走的路徑是左子樹+左子樹，判定該狀況為LL旋轉。

• 觀察一下45、36、18三個node，因為路徑為LL，所以代表45的位置一定最大，36其次，18最小。我們要做的事情就是將中間值往上提，較小較大放左右。
• 如此一來，便完成了AVL了平衡。

RR、LR、RL旋轉

• 由於概念與上面的LL相似，在此就只簡單圖片表示。
• 特別注意，我們都是將中間值往上提，較小較大放左右（因為很重要再說一次）。

• RR

• LR
  • A,B,C中，C是中間值！

• RL
  • A,B,C中，C是中間值！
  • 該繪圖語言的某些關係，這張圖我畫不出虛線。

刪除

• 刪除掉元素一樣會導致樹不平衡，我們一樣利用旋轉來維持平衡。

1.照一般Binary Search Trees的規則去刪除。
2.找任意樹葉往上檢查左右子樹高度差。
3.如果都符合，結束。
4.不符合，旋轉。
5.再次檢查，如不符合，再次旋轉。

• 旋轉的方法都和上面插入時的一樣，故不討論。
• 特別注意，根據選擇的樹葉不同，可能導致旋轉完之後依然不平衡。
  • 我不確定這邊應該回到旋轉前的樣子，選擇其他樹葉旋轉，還是直接再次旋轉。
  • 因為畫那些圖很累，我不想畫例子了。

tags: DS note