AVL樹是有平衡條件的二叉搜尋樹。這個平衡條件必須容易保持，而且需要保證樹的深度是O（logN)。
- AVL=BBST
作為二叉搜尋樹的最後一部分，我們來介紹最為經典的一種平衡二叉搜尋樹：AVL樹。回顧此前的幾節，我們首先介紹的是二叉查找樹BST。然而我們也能感受到，盡管從同時兼顧高效的靜态操作
和動态操作的角度講，BST相對此前簡單的向量和連結清單已經具有某種優勢和潛質，但是畢竟它并不能保證這一點。其原因在于 它的高度，無論是從平均情況 還是最壞情況都不能保證做到足夠的低，具體來說也就是做到logN以下當然——在BST中的确存在一種特殊的類型：也就是所謂的Complete Binary Tree它的高度可以達到嚴格的最小——也就是logN。然而相對于整體的BST這類BST的數量極少。而且将任何一棵樹轉化為一棵完全二叉樹所需要的成本也太高，也正因如此，我們的建議是：或許應該适當地放松所謂“平衡”的标準。也就是說，隻需考察某一類在漸近意義下不超O(logN)高度的樹即可。而這樣一類樹，也就是我們所說的平衡二叉搜尋樹Balanced Binary Search Tree，BBST。
本節涉及概念及其關系
比如我們這一節将要介紹的AVL樹就是在這種意義下的一種BBST。以AVL樹為代表的這些BBST
首先并沒有放棄漸近意義logN的複雜度底線。同時正因為它已經适度地放松了平衡的标準，是以通過精巧地設計，它們都可以具有這樣一種屬性：具體來說，對于任何一棵這樣意義下的BBST在其生命期内即便在某次操作之後它不再滿足BBST的條件， 遊離到BBST這個範疇之外，我們也可以通過上節所介紹的等價變換迅速地将其重新轉化為一棵等價的BBST。也就是說可以通過極小的代價就使之重新歸入BBST的範疇。而這種極小的代價是多少呢？不出你的意料——依然是不超過logN。
令剛剛失衡的搜尋樹重新恢複為一棵BBST的過程也稱作重平衡Rebalance。而對于包括AVL樹在内的各種BBST而言，其核心的技巧無非兩條：
- 如何來界定一種“适度的平衡”标準
- 其次則是一整套重平衡的技巧和算法
以下我們就以AVL樹為例，具體地講解如何完成這兩項任務。
先不管具體AVL樹的要求，先來想想，如果我們自己來設計平衡标準，該如何考慮呢？最簡單的想法是，要求左右子樹具有相同的高度，那這種想法不要求樹的高度盡量低。但是……極端情況下可能出現兩條左右分叉的單鍊，這就很心碎了。是以這個标準是遠遠不夠的。
再想想有沒有更好的辦法，（可達鴨眉頭一皺，發現事情并不簡單hhhh）于是我們想到了另一種平衡條件——要求每個節點都必須有同高的左右子樹。可是這樣一來又會出問題：因為空樹-1，那就隻有具有2^k-1個節點的理想平衡樹（Perfect Binary Tree）滿足了，這個适用性就太狹窄了……很紮心。是以，雖然這個條件保證了樹的高度很低，但是太苛刻了，我們還要再放寬點條件。
後來，兇暴死宅的計算機科學家們（誤）想到了一個絕妙的點子，而且我這裡地方夠大，寫得下hhhhh。 用這個條件來限制：“讓每個節點的左右子樹高度最多差1”。可以證明，大緻來講一個AVL樹的高度<=1.44log（N+2）-1.328。
這棵樹的左子樹是高度為7且節點數最少的AVL樹，右子樹是高度為8且節點數最少的AVL樹。可以看出在高度為h的AVL樹中，最少節點數S(h)=S(h-1) + S(h-2) + 1。對于h=0，S(h) = 1；h=1，S(h)=2。函數S(h)與斐波那契數密切相關，由此可以推出上面的關于AVL樹的高度上界。
有了上面的感性認識後，我們來詳細讨論、解釋AVL樹的各處細節，将上面給出的若幹濃縮表述一一诠釋。
首先，給出在AVL的意義下，什麼叫做适度的平衡。這要引入一個概念——平衡因子，憑它來判斷一棵樹是否是在AVL意義下的适度平衡
平衡因子(Balanced Factor)就是左子樹的高度與右子樹高度之差，BalFac(v)=height（lc（v））- height（rc（v））。結合上面發明者的定義
那麼很顯然，這是一顆AVL樹（通過校驗每個節點的balFac，每處都上上下下不超過1）：
AVL樹隻考慮左右子樹的高度，是以隻有所有節點滿足全局的單調性即可，并不需要關心具體的數值。我們應該把更多的關注點集中于每個節點的平衡因子上。從這個例子可以看出，AVL樹未必是CBT，反過來說，如此定義的AVL樹，是否适度平衡呢？
- AVL=适度平衡
可以證明，AVL樹的确是适度平衡的——也就是說 一棵規模為N的AVL樹高度在漸近意義下是不超過logN的。
實際上，為了證明規模固定的AVL樹高度不會超過某個上限，我們可以等價地證明：在高度固定的情況下，一棵AVL樹的節點也不至于太少。具體來說，可以證明這樣一個事實：對于高度固定為h的AVL樹其中所包含的節點數，至少是與h呈fibonacci數關系。
為了得到這個關系式，我們需要借助遞推式。具體而言可以證明這樣一個遞推式：S(h)=S(h-1) + S(h-2) + 1，這也就是上面所給出的那個遞推式。如果我們将高度為h的AVL樹的規模下限定義為S(h)的話，那麼S(h)與S(h-1)以及S(h-2)之間就滿足這麼樣一個疊加的關系。
為此，我們來考察那棵高度為h同時規模達到最小的AVL樹。
既然它的規模要達到最少，是以它的左子樹和右子樹的規模也應該盡可能少，那麼在AVL樹的定義下，可變化的餘地充其量不過其中一棵子樹比另一棵子樹高一層。不失一般性，假設左子樹比右子樹高出一層，因為它的高度為h-1，是以它的規模下限自然也就是S(h-1)。同理，作為高度為h-2的右子樹，它的規模下限自然也就是S(h-2)。當然——還不要忘了這裡的樹根節點。這也就是為什麼我們還要再附加上一個機關1。
這個遞推式是我們所有分析的核心，而以下隻不過是一些簡單的數學技巧而已。為此，我們不妨對它做一個等價變換——在左右各加一個1。
S(h)+1=[S(h-1)+1 ]+ [S(h-2) + 1]
接下來，如果我們将S(h)+1定義為一個新的函數T(h)，就會發現遞推式的右側變成T(h-1) +T(h-2)。這種形式是fibonacci數所特有的遞推形式。是以我們可以斷定它應該是等于fibonacci的某一項。那麼具體的是從 h前後位移多少項呢？
我們隻需考察對應的邊界情況即可：首先考察規模為1高度為0的AVL樹。此時的T(h)應該等于1+1，這是fibonacci數的第三項。再來考察高度為1的AVL樹，其規模最小也不至低于2，也就是左子樹為一個節點、右子樹為空的一棵AVL樹，此時的T(h)應該是2+1，這是fibonacci數的第四項。
由此可見 這裡的T(h)，隻不過是fibonacci數向前位移了三位。我們知道fibonacci數，大緻是呈Φ的指數形式增長，由此我們也得到了n關于高度h的一個下界。是以反過來等價地 n的對數，也就構成了h的一個上界。而這一點正是BBST所謂适度平衡的要求——這就意味着我們的AVL樹的确是适度平衡的。
好了，至此我們也就完成了第一項使命——也就是給出AVL意義下的，适度平衡标準。下一節将給出具體的重平衡（旋轉操作）細節和插入新節點的算法。