AVL樹(shù)：它是高度平衡的二叉搜索樹(shù)，它的左子樹(shù)和右子樹(shù)都是AVL樹(shù)锚国。結(jié)點(diǎn)擁有的平衡因子（balance）是該結(jié)點(diǎn)的右子樹(shù)減去左子樹(shù)的高度所得到的高度差,規(guī)定AVL任意結(jié)點(diǎn)的平衡因子只能取-1,0,1叨恨。
1午磁、代碼實(shí)現(xiàn)：
首先定義一個(gè)AVLTree類模板：
購(gòu)買(mǎi)和釋放結(jié)點(diǎn)：
2莺戒、實(shí)例分析：
如上圖所示,選取數(shù)組int ar[]={16, 3, 7, 11, 9, 26, 18, 14, 15 }進(jìn)行插入構(gòu)造AVLTree操作呀舔。
步驟分析：
（1）先插入16弥虐，再插入3，再插入7媚赖，至此得到下圖：
（2）可以看到此時(shí)這棵樹(shù)已經(jīng)不平衡了霜瘪，所以需要對(duì)此調(diào)整【寤牵可以看到它們位于一條折線上颖对，因此需要進(jìn)行先左后右的雙旋轉(zhuǎn)，先以結(jié)點(diǎn)7為旋轉(zhuǎn)軸磨隘，將結(jié)點(diǎn)3逆時(shí)針做左單旋轉(zhuǎn)缤底；再以結(jié)點(diǎn)7為旋轉(zhuǎn)軸，將結(jié)點(diǎn)16順時(shí)針做右單旋轉(zhuǎn)番捂，得到如下圖：
（3）再插入下一個(gè)結(jié)點(diǎn)11个唧，插入結(jié)點(diǎn)9，得到下圖：
（4）可以看到此時(shí)這棵樹(shù)已經(jīng)不平衡了设预，所以需要對(duì)此調(diào)整徙歼。16、11、9三點(diǎn)處于一條斜線上魄梯，因此對(duì)它進(jìn)行右單旋轉(zhuǎn)桨螺，以11為旋轉(zhuǎn)軸，將16右單旋轉(zhuǎn)可得到：
（5）繼續(xù)插入26酿秸，得到：
（6）可以看到此時(shí)這棵樹(shù)已經(jīng)不平衡了灭翔，所以需要對(duì)此調(diào)整。11辣苏、16肝箱、26三點(diǎn)處于一條斜線上，因此對(duì)它進(jìn)行左單旋稀蟋，以11為旋轉(zhuǎn)軸狭园，將7逆時(shí)針旋轉(zhuǎn)，得到：
（7）然后插入18糊治，同樣得到一顆不平衡的樹(shù)：
（8）因此需要對(duì)其進(jìn)行調(diào)整，因?yàn)?6,26,18三點(diǎn)處于一條折線上罚舱，因此需要對(duì)其進(jìn)行右左雙旋井辜，先以18為旋轉(zhuǎn)軸，將26順時(shí)針旋轉(zhuǎn)管闷，再以18為旋轉(zhuǎn)軸，將16進(jìn)行逆時(shí)針旋轉(zhuǎn)，可以得到下圖：
（9）然后插入14顿乒、15摹察，得到圖如下：
（10）分析上圖的不平衡，可以發(fā)現(xiàn)16,14,15三點(diǎn)處于一條折線上碧囊，需要進(jìn)行先左后右旋轉(zhuǎn)树灶，先以15為旋轉(zhuǎn)軸，將14逆時(shí)針旋轉(zhuǎn)糯而，再以15為旋轉(zhuǎn)軸天通，將16順時(shí)針旋轉(zhuǎn)，得到下圖：
（11）至此熄驼，得到了本文最開(kāi)始的高度平衡的二叉樹(shù)像寒，也即AVL樹(shù)。
3瓜贾、實(shí)例的代碼實(shí)現(xiàn)（向AVLTree插入結(jié)點(diǎn)）：
4诺祸、AVL樹(shù)的其它操作：
