AVL樹概念
- AVL樹是 帶有平衡條件的二叉查找樹 。這個平衡條件必須要 容易保持 。而且要保證它的深度是O(logN).
- AVL的條件是左右樹的高度差（ 平衡因子 ）不大於1；並且它的每個子樹也都是平衡二叉樹。
- 對於平衡二叉樹的最小個數， n0=0 ; n1=1 ; nk=n(k-1)+n(k-2)+1 ;(求法可以類比斐波那契！)
難點：AVL是一顆二叉排序樹，用什麼樣的規則或者規律讓它能夠在 複雜度不太高 的情況下 實現動態平衡 呢？
不平衡概況
如果簡單的以單節點看，大致有上面 四種 情形，並且他們的最後結果也是有的有所相近。只是：上下會變動。 該在左面的還在左面，改在右面的還在右面 。
這只是針對在底部，對於可能出現的平衡要首先搞清楚：
所以針對四種不平衡， 可能出現在底部，也可能出現在頭，也可能出現在某個中間節點導致不平衡。 而我們只需要研究其首次不平衡點， 解決之後整棵樹即繼續平衡 。當然，在實際解決肯定會帶上 遞歸 的思想解決問題。
#四種平衡旋轉方式
RR平衡旋轉(左單旋轉)
出現這種情況的原因是節點的 右側的右側較深 這時候 不平衡節 點需要 左旋 。再細看過程。
- 再左旋的過程中， root(oldroot) 節點下沉， 中間節點(newroot) 上浮.而其中 中間節點(newroot) 的右側依然不變。
- 它上浮左側所以需要指向 根節點(oldroot) (畢竟一棵樹)。但是這樣 newroot 原來左側節點 H 空缺。而我們需要仍然讓 整個樹完整並且滿足二叉排序樹的規則 。
- 而剛好 本來oldroot右側指向newroot變成oldroot被newroot左側指向 。所以 oldroot右側空缺 ，剛好這個位置 滿足 在oldroot的右側。在newroot的左側。 .所以我們將H插入在這個位置。
- 其中H可能為 NULL 。不過不影響操作！
而左旋的代碼可以表示為：
LL平衡旋轉(右單旋轉)
而右旋和左旋相反，但是思路相同，根據上述進行替換即可！
代碼：
RL平衡旋轉(先右後左雙旋轉)
產生不平衡的條件原因是：
- root節點右側左側節點的深度高些 ，使得 與左側的差大於1 .這個與我們前面看到的左旋右旋不同的是因為它的結構不能直接變一下就可以完成。
- 因為對於右左結構， 中間的最大，兩側的最小 。但是下面的比上面大( 下面在上面右側 )所以如果平衡的話，那麼 右左的R.L 應該在中間，而 R 應該 在右側 。原來的root在左側。
- 所以節點的變化浮動比較大，而且需要 妥善處理各個子節點的移動 使其滿足 二叉排序樹的 性質！
- 期間考慮樹高度變化即可！
這種雙旋轉其實也很簡單。不要被外表唬住。基於前面的單旋轉，雙旋轉有 兩種 具體 邏輯思路 。
思路1：兩次旋轉RR,LL
根據上圖所圈的，先對底部使得底部的大小關係變化，使其在滿足二叉平衡樹的條件下還滿足RR結構的二叉樹。所以只需要對 右節點R先進行右旋 ,再對ROOT進行左旋即可。
思路2：直接分析
根據初始和結果的狀態，然後分析各個節點變化順序。手動操作這些節點即可！
- 首先根據 ROOT,R,R.L 三個節點變化。R.L肯定要在最頂層。左右分別指向ROOT和R。那麼這其中 R.left，ROOT.right 發生變化(原來分別是R,L和R)暫時為空。而剛好根據 左右大小關係 可以補上 R.L的左右節點 。
- 這樣思考整棵樹也可以完成平衡，但是要考慮 樹的高度變化 。
代碼為：(注釋部分為方案1)
LR平衡旋轉(先左後右單旋轉)
根據上述RL修改即可
java代碼實現
- 首先對於節點多個 height 屬性。用於計算高度(平衡因子)
- 插入是 遞歸插入 。遞歸一個來回的過程，去的過程進行插入。 回的過程進行高度更新。和檢查是否平衡。 不要寫全局遞歸計算高度，效率太低下。事實上高度變化只和插入和平衡有關，仔細考慮即不會有疏漏！總結測試情況：
- AVL的理解需要時間，當然筆者的AVL自己寫的 可能有些疏漏 ，如果有問題還請各位 一起探討 ！
- 當然，除了插入，AVL還有 刪除 等其他操作，(原理相似。刪除後平衡)有興趣可以一起研究。