平衡二叉搜尋樹，又被稱為AVL樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。 —-來自百度百科
由于普通的二叉查找樹會容易失去”平衡“，極端情況下，二叉查找樹會退化成線性的連結清單，導緻插入和查找的複雜度下降到 O(n) ，是以，這也是平衡二叉樹設計的初衷。那麼平衡二叉樹如何保持”平衡“呢？根據定義，有兩個重點，一是左右兩子樹的高度差的絕對值不能超過1，二是左右兩子樹也是一顆平衡二叉樹。
如下圖所示，左圖是一棵平衡二叉樹，根節點10，左右兩子樹的高度差是1，而右圖，雖然根節點左右兩子樹高度差是0，但是右子樹15的左右子樹高度差為2，不符合定義，是以右圖不是一棵平衡二叉樹。
由此可以看出平衡二叉樹是一棵高度平衡的二叉查找樹。是以，要建構跟維系一棵平衡二叉樹就比普通的二叉樹要複雜的多。在建構一棵平衡二叉樹的過程中，當有新的節點要插入時，檢查是否因插入後而破壞了樹的平衡，如果是，則需要做旋轉去改變樹的結構。
關于旋轉，這東西不拿動态圖将還真很難講明白。是以我就借一下 最容易懂得紅黑樹 這篇文章中左旋右旋的圖來講。
左旋：
右旋：
不同于順時針跟逆時針變換這種方式去記憶，上面兩個動态圖特别友善記憶跟了解：
左旋就是将節點的右支往左拉，右子節點變成父節點，并把晉升之後多餘的左子節點出讓給降級節點的右子節點；
而右旋就是反過來，将節點的左支往右拉，左子節點變成了父節點，并把晉升之後多餘的右子節點出讓給降級節點的左子節點。
即左旋就是往左變換，右旋就是往右變換。不管是左旋還是右旋，旋轉的目的都是将節點多的一支出讓節點給另一個節點少的一支。
舉個例子，像上圖是否平衡二叉樹的圖裡面，左圖在沒插入前”19“節點前，該樹還是平衡二叉樹，但是在插入”19“後，導緻了”15“的左右子樹失去了”平衡“，是以此時可以将”15“節點進行左旋，讓”15“自身把節點出讓給”17“作為”17“的左樹，使得”17“節點左右子樹平衡，而”15“節點沒有子樹，左右也平衡了。如下圖，
由于在建構平衡二叉樹的時候，當有新節點插入時，都會判斷插入後時候平衡，這說明了插入新節點前，都是平衡的，也即高度差絕對值不會超過1。當新節點插入後，有可能會有導緻樹不平衡，這時候就需要進行調整，而可能出現的情況就有4種，分别稱作左左，左右，右左，右右。
左左：
左左即為在原來平衡的二叉樹上，在節點的左子樹的左子樹下，有新節點插入，導緻節點的左右子樹的高度差為2，如上即為”10“節點的左子樹”7“，的左子樹”4“，插入了節點”5“或”3“導緻失衡。
左左調整其實比較簡單，隻需要對節點進行右旋即可，如下圖，對節點”10“進行右旋，
注意：如果對左右旋變換還不是很懂或不是很熟練的，可以對照着前面的那兩個動圖去想象，自己動手變換幾次，就明白了。
左右：
左右即為在原來平衡的二叉樹上，在節點的左子樹的右子樹下，有新節點插入，導緻節點的左右子樹的高度差為2，如上即為”11“節點的左子樹”7“，的右子樹”9“，插入了節點”10“或”8“導緻失衡。
左右的調整就不能像左左一樣，進行一次旋轉就完成調整。我們不妨先試着讓左右像左左一樣對”11“節點進行右旋，結果圖如下，右圖的二叉樹依然不平衡，而右圖就是接下來要講的右左，即左右跟右左互為鏡像，左左跟右右也互為鏡像。
右右跟左左一樣，隻需要旋轉一次就能把樹調整平衡，而左右跟右左也一樣，都要進行旋轉兩次才能把樹調整平衡，是以，首先上圖的這種調整是錯誤的，正确的調整方式是，将左右進行第一次旋轉，将左右先調整成左左，然後再對左左進行調整，進而使得二叉樹平衡。
即先對上圖的節點”7“進行左旋，使得二叉樹變成了左左，之後再對”11“節點進行右旋，此時二叉樹就調整完成，如下圖，
右左：
右左即為在原來平衡的二叉樹上，在節點的右子樹的左子樹下，有新節點插入，導緻節點的左右子樹的高度差為2，如上即為”11“節點的右子樹”15“，的左子樹”13“，插入了節點”12“或”14“導緻失衡。
前面也說了，右左跟左右其實互為鏡像，是以調整過程就反過來，先對節點”15“進行右旋，使得二叉樹變成右右，之後再對”11“節點進行左旋，此時二叉樹就調整完成，如下圖，
右右：
右右即為在原來平衡的二叉樹上，在節點的右子樹的右子樹下，有新節點插入，導緻節點的左右子樹的高度差為2，如上即為”11“節點的右子樹”13“，的左子樹”15“，插入了節點”14“或”19“導緻失衡。
右右隻需對節點進行一次左旋即可調整平衡，如下圖，對”11“節點進行左旋。
平衡二叉樹建構的過程，就是節點插入的過程，插入失衡情況就上面4種，算簡單了，下面講下平衡二叉樹節點的删除，删除的情況會複雜一點，複雜的原因主要在于删除了節點之後要維系二叉樹的平衡，但是删除二叉樹節點總結起來就兩個判斷：①删除的是什麼類型的節點？②删除了節點之後是否導緻失衡？
節點的類型有三種：1.葉子節點；2.隻有左子樹或隻有右子樹；3.既有左子樹又有右子樹。
針對這三種節點類型，再引入判斷②，是以處理思路分别是：
（1）當删除的節點是葉子節點，則将節點删除，然後從父節點開始，判斷是否失衡，如果沒有失衡，則再判斷父節點的父節點是否失衡，直到根節點，此時到根節點還發現沒有失衡，則說此時樹是平衡的；如果中間過程發現失衡，則判斷屬于哪種類型的失衡（左左，左右，右左，右右），然後進行調整。
（2）删除的節點隻有左子樹或隻有右子樹，這種情況其實就比删除葉子節點的步驟多一步，就是将節點删除，然後把僅有一支的左子樹或右子樹替代原有結點的位置，後面的步驟就一樣了，從父節點開始，判斷是否失衡，如果沒有失衡，則再判斷父節點的父節點是否失衡，直到根節點，如果中間過程發現失衡，則根據失衡的類型進行調整。
（3）删除的節點既有左子樹又有右子樹，這種情況又比上面這種多一步，就是中序周遊，找到待删除節點的前驅或者後驅都行，然後與待删除節點互換位置，然後把待删除的節點删掉，後面的步驟也是一樣，判斷是否失衡，然後根據失衡類型進行調整。
最後總結一下，平衡二叉樹是一棵高度平衡的二叉樹，是以查詢的時間複雜度是 O(logN) 。插入的話上面也說，失衡的情況有4種，左左，左右，右左，右右，即一旦插入新節點導緻失衡需要調整，最多也隻要旋轉2次，是以，插入複雜度是 O(1) ，但是平衡二叉樹也不是完美的，也有缺點，從上面删除處理思路中也可以看到，就是删除節點時有可能因為失衡，導緻需要從删除節點的父節點開始，不斷的回溯到根節點，如果這棵平衡二叉樹很高的話，那中間就要判斷很多個節點。是以後來也出現了綜合性能比其更好的樹—-紅黑樹，後面再講。