二叉查找樹(bstree)中進行查找、插入和删除操作的時間複雜度都是o（h），其中h為樹的高度。
bst的高度直接影響到操作實作的性能，最壞情況下，二叉查找樹會退化成一個單連結清單，比如插入的節點序列本身就有序，這時候性能會下降到o(n)。
可見在樹的規模固定的前提下，bst的高度越低越好。
平衡二叉樹是計算機科學中的一類改進的二叉查找樹。
平衡二叉樹具有以下性質：
（1）一棵空樹是平衡二叉樹
（2）如果樹不為空，它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
平衡二叉樹要求對于每一個節點來說，它的左右子樹的高度之差不能超過1，如果插入或者删除一個節點使得高度之差大于1，就要進行節點之間的旋轉，将二叉樹重新維持在一個平衡狀态。
這個方案很好的解決了二叉查找樹退化成連結清單的問題，把插入，查找，删除的時間複雜度最好情況和最壞情況都維持在o(logn)。
一棵好的平衡二叉樹的特征：
（1）保證有n個結點的樹的高度為o(logn)
（2）容易維護，也就是說，在做資料項的插入或删除操作時，為平衡樹所做的一些輔助操作時間開銷為o(1)
平衡二叉樹的常用算法有紅黑樹、avl、treap、伸展樹等。
avl樹是最先發明的自平衡二叉查找樹，是以一般提到平衡二叉樹一般就指avl樹，差別于紅黑樹、伸展樹等。
avl樹得名于它的發明者g.m. adelson-velsky和e.m. landis，他們在1962年的論文《an algorithm for the organization of information》中發表了它。
平衡二叉樹的關鍵在平衡，那麼它的平衡是如何保持的呢？
adelson-velskii 和 landis 提出了一個動态地保持二叉排序樹平衡的方法，其基本思想是：在構造二叉排序樹的過程中，每當插入一個結點時，首先檢查是否因插入而破壞了樹的平衡性，如果是因插入結點而破壞了樹的平衡性，則找出其中最小不平衡子樹，在保持排序樹特性的前提下，調整最小不平衡子樹中各結點之間的連接配接關系，以達到新的平衡。通常将這樣得到的平衡二叉排序樹簡稱為 avl 樹。
現在我們定義平衡因子和最小不平衡子樹的概念。
（1）平衡因子
在二叉樹中，任何一個節點v的平衡因子都定義為其左、右子樹的高度差。空樹的高度定義為-1。
在二叉查找樹t中，若所有節點的平衡因子的絕對值均不超過1，則稱t為一棵avl樹。
（2）最小不平衡子樹
最小不平衡子樹以離插入結點最近、且平衡因子絕對值大于 1 的結點作根結點的子樹。
旋轉操作是一種調整樹結構而不改變二叉查找樹特性的手段。
這裡要了解樹旋轉的意義，樹的最終目的不是維護節點與節點之間的層級關系，關鍵是如何用avl樹這種資料結構進行更好的查找和搜尋。
（1）右旋（順時針方向旋轉）
（2）左旋（逆時針方向旋轉）
為了簡化讨論，不妨假設二叉排序樹的最小不平衡子樹的根結點為 a ，則調整該子樹的規律可歸納為下列四種情況：
（1）ll 型：
ll情況需要右旋解決，如圖所示：
（2）rr 型：
rr情況需要左旋解決，如圖所示：
（3）lr 型：
lr情況需要左右（先b左旋轉，後a右旋轉）旋解決，如圖所示：
（4）rl 型：
rl情況需要右左旋解決（先b右旋轉，後a左旋轉），如圖所示：
avl樹是一棵二叉查找樹，與普通二叉查找樹不同的是，在插入和删除節點之後需要重新進行平衡，是以繼承并重寫普通二叉查找樹的insert和delete方法，就可以實作一棵avl樹。
1
<code>待續。</code>