<code>avl</code> 平衡二叉樹
<code>avl</code> 樹：adelson-velsky and landis tree。是計算機科學中最早被發明的自平衡二叉樹，在 <code>avl</code> 樹中，任意兩個節點之間的高度差不會超過 1，是以 <code>avl</code> 樹也被稱之為高度平衡樹。<code>avl</code> 樹的插入、删除、查找操作在平均和最壞的時間複雜度都為 \(o(log_2n)\) 級别的時間複雜度
在這裡，我們給定 <code>avl</code> 樹的高度差門檻值為 1，當有節點的高度差大于這個門檻值時，執行相應的操作以實作樹的平衡。
<code>avl</code> 樹的平衡也是通過旋轉節點來實作平衡的，分别對以下四種情況進行讨論
左左情況
這種情況是指目前處理的節點的左子節點的左子節點的節點高度差大于給定門檻值的情況，如下圖所示：
如圖所示，目前的 10 節點和底部的 3節點之間的高度差已經大于我們給定的門檻值 1了，是以這種情況下需要對 10 節點進行一次右旋轉，使得這棵樹依舊是滿足給定的高度差門檻值的。
進行右旋轉之後：
右右情況
這種情況就是目前節點的右子節點的右子節點之間節點的高度差大于給定的門檻值的情況，如下圖所示：
在這種情況下，對目前節點進行一次左旋轉即可實作樹的重新平衡，使得目前節點的高度差在給定的門檻值範圍内
進行左旋轉之後：
左右情況
這種情況下，是由于目前節點與目前節點的左子節點的右子節點之間的高度差達到指定門檻值的情況，如下圖所示：
這種情況下，首先需要對目前節點的左子節點進行一次左旋轉，然後再進行一次右旋轉即可再次達到樹的平衡
首先對目前節點的左子節點進行左旋轉：
然後再對目前節點進行一次右旋轉：
右左情況
這種情況是目前節點和目前節點的右子節點的左子節點之間的節點高度差達到了給定的門檻值，這種情況如下圖所示：
這種情況下，需要首先對目前節點的右子節點進行一次右旋轉，再對目前節點進行一次左旋轉來完成樹的重新平衡
首先對目前節點的右子節點進行一次右旋轉：
再對目前節點進行一次左旋轉即可：
以上就是在處理 <code>avl</code>樹的過程中可能會遇到的幾種情況，通過分析這幾種情況并提供對應的解決政策使得整個樹最終保持平衡，這是了解 <code>avl</code>樹的基礎。
對于一棵樹來講，最基本的操作便是增、删、改、查四個操作。查找操作與一般的二叉樹的查找沒有任何不同，是以在這裡不介紹具體的實作思路；對于修改操作來講，無非就是找到要修改的節點，然後再更新對應的節點資料即可，這與查找操作沒有太大的差異。
<code>avl</code> 樹中最關鍵的兩個操作便是插入和删除，同時也是實作起來比較困難的地方。主要是要結合上文提到的幾種情況進行分析，然後進行旋轉操作，這幾個過程比較複雜，是以在這裡講述一下實作的思路。
首先，定義 <code>avl</code> 樹的節點類：
實作思路：遞歸地查找目前插入的節點的插入位置，将其插入後再檢測目前的處理節點與其相關的子節點之間是否存在高度差達到指定門檻值的節點，如果存在這樣的節點，那麼就需要調整這個節點。
重新調整目前的處理節點：
每次隻要遞歸地調整處理節點即可實作樹整體的調節。
具體的插入操作的實作如下：
删除操作是一個比較複雜的實作，因為如果任意删除一個節點元素的話，那麼樹的平衡性就很難得到保障。相比較與紅黑樹使用多個節點組成 3- 節點或者 4- 節點來删除鍵來維護樹的平衡性，<code>avl</code> 樹的做法就更加純粹一些。
主要有兩種方式來實作節點的删除操作：一是把要删除的節點不斷地旋轉，将它旋轉到葉子節點然後再删除它，然後再重新調整數的平衡；二是從目前節點的左子節點找到最大的元素節點或者從右子節點中找到最小的元素節點來填充目前節點的資料，然後再向下遞歸地删除這個節點元素，再重新調整樹的平衡性。
想比較而言，使用第二種方式是一個更加簡單有效的實作方式，是以在這裡也采用第二種方式來實作，這裡的實作填充的是右子節點的最小元素資料。
具體實作代碼如下圖所示：
總體上相比較于紅黑樹而言， <code>avl</code> 樹中需要的操作更多，是以整體性能上要比紅黑樹要差一些。
整體的實作代碼：https://github.com/liuxianghai-coder/test-repo/blob/master/datastructure/avl.java