從二叉搜索樹BST中可以看出，如果一個數(shù)據(jù)在'很深'的節(jié)點處保存、對于搜索的開銷就會很大，能不能調(diào)整一下樹的結(jié)構(gòu)，讓查詢所有的數(shù)據(jù)的時間差不多平衡。

平衡二叉樹AVL解釋: 這兩人的 Adelson-Velsky 和 E.M. Landis的名字縮寫，在他們發(fā)表的文章'An algorithm for the organization of information'提及該算法。

平衡二叉樹要求對于每一個節(jié)點來說，它的左右子樹的高度之差不能超過1，如果插入或者刪除一個節(jié)點使得高度之差大于1，就要進行節(jié)點之間的旋轉(zhuǎn)，將二叉樹重新維持在一個平衡狀態(tài)。這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時間復雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉(zhuǎn)會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉樹查詢來說，時間上穩(wěn)定了很多。


平衡二叉樹實現(xiàn)的大部分過程和二叉查找樹是一樣的，區(qū)別就在于插入和刪除之后要寫一個旋轉(zhuǎn)[算法]去維持平衡，維持平衡需要借助一個節(jié)點高度的屬性。

AVL樹的旋轉(zhuǎn)規(guī)律

1. LL型

? ? ? ?平衡二叉樹某一節(jié)點的左孩子的左子樹上插入一個新的節(jié)點，使得該節(jié)點不再平衡。這時只需要把樹向右旋轉(zhuǎn)一次即可，如圖所示，原A的左孩子B變?yōu)楦附Y(jié)點，A變?yōu)槠溆液⒆?，而原B的右子樹變?yōu)锳的左子樹，注意旋轉(zhuǎn)之后Brh是A的左子樹:(淡紅色尾部為要添加子樹的節(jié)點)

2. RR型

平衡二叉樹某一節(jié)點的右孩子的右子樹上插入一個新的節(jié)點，使得該節(jié)點不再平衡。這時只需要把樹向左旋轉(zhuǎn)一次即可，如圖所示，原A右孩子B變?yōu)楦附Y(jié)點，A變?yōu)槠渥蠛⒆?，而原B的左子樹Blh將變?yōu)锳的右子樹:

3. LR型

平衡二叉樹某一節(jié)點的左孩子的右子樹上插入一個新的節(jié)點，使得該節(jié)點不再平衡。這時需要旋轉(zhuǎn)兩次，僅一次的旋轉(zhuǎn)是不能夠使二叉樹再次平衡。如圖所示，在B節(jié)點按照RR型向左旋轉(zhuǎn)一次之后，二叉樹在A節(jié)點仍然不能保持平衡，這時還需要再向右旋轉(zhuǎn)一次：

4. RL型

平衡二叉樹某一節(jié)點的右孩子的左子樹上插入一個新的節(jié)點，使得該節(jié)點不再平衡。同樣，這時需要旋轉(zhuǎn)兩次，旋轉(zhuǎn)方向剛好同LR型相反：

java實現(xiàn):http://blog.csdn.net/zxman660/article/details/7940190