前言

在進入下一章紅黑樹前，我們要先帶一下 AVL Tree，告訴大家怎麼調整 Unbalanced 的狀況，本章節應該是要放在前面一點講解的，不小心安排錯ㄌQQ

緣由

我們在學習 BST 的時候，曾經提過 BST 的結構長相會因為資料插入的順序而有所不同，當 BST 太過於頻繁的插入即刪除，容易退化成 Skewed BST，導致 search/insert/delete 等等的操作都變成 O(n)，變非常慢
因此，要如何去動態改變 BST 的結構，讓 Search/Insert/delete，都保持在O(logn)，即為 AVL Tree 出現的緣由

定義

AVL Tree 為 BST 且滿足

1. 左子樹與右子樹高度差≤1 即
2. 左右子樹也都是 AVL Tree

Unbalanced 狀況

以不平衡的點往下看，我們可以將 Unbalanced 的狀況分為以下四種 RR,LL,RL,LR

1. RR
   
2. LL
   
3. RL
   
4. LR
   

調整

由於其是 BST，可以先根據位置去判斷三點之大、中、小

1. 把中間值往上拉變成三點之Root，大的放右，小的放左即可
2. 若有孤兒，則將孤兒放入調整後之適當位置

怕大家不懂第二點，以下圖為例，解釋若有剩下的怎麼處理

我們先將紅色欲調整的中間值往上拉，小的放左邊，大的放右邊後，會剩下 16，再將 16 放置到適當位置即可