首先給AVL樹下個(gè)定義：
一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的任意節(jié)點(diǎn)的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對值不超過1。
下面做簡要分析：
(1)AVL樹首先是個(gè)二叉搜索樹，對任意節(jié)點(diǎn)a，比a數(shù)值小的節(jié)點(diǎn)在左子樹上，比a數(shù)值大的節(jié)點(diǎn)在右子樹上。
(2)AVL樹高度平衡。每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差。這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子balance。根據(jù)AVL樹的定義，任一結(jié)點(diǎn)的平衡因子只能取 -1，0、1。假設(shè)有N個(gè)節(jié)點(diǎn)，那么其高度可保持在O(log2n)，平均搜索長度也可保持在O(log2n)。
(3)添加節(jié)點(diǎn)導(dǎo)致不平衡時(shí)，需進(jìn)行平衡化旋轉(zhuǎn)。
平衡化旋轉(zhuǎn)：
平衡化旋轉(zhuǎn)有兩類：
(1)單旋轉(zhuǎn) (左旋和右旋)
(2)雙旋轉(zhuǎn) (左平衡和右平衡)
每插入一個(gè)新結(jié)點(diǎn)時(shí)，AVL樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)可能會發(fā)生改變。因此，在插入一個(gè)新結(jié)點(diǎn)后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因子(左、右子樹的高度差)。 如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。
從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。此時(shí)分為兩種情況：
(1)如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。
(2)如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。
/%CA%FD%BE%DD%BD%E1%B9%B9/lesson/ch07/picture/28.JPG)
假設(shè)以上三個(gè)節(jié)點(diǎn)從上至下分別為A、B、C，則有：
(1)右單旋轉(zhuǎn)：
以節(jié)點(diǎn)B為軸，節(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)，成為節(jié)點(diǎn)B的右兒子，節(jié)點(diǎn)B原右子樹成為節(jié)點(diǎn)A的左子樹。
(2)左單旋轉(zhuǎn)：
以節(jié)點(diǎn)B為軸，節(jié)點(diǎn)A逆時(shí)針旋轉(zhuǎn)，成為節(jié)點(diǎn)B的左兒子，節(jié)點(diǎn)B原左子樹成為節(jié)點(diǎn)A的右子樹。
(3)左右雙旋轉(zhuǎn)：
節(jié)點(diǎn)C和節(jié)點(diǎn)B逆時(shí)針轉(zhuǎn)動，C成為節(jié)點(diǎn)A的左兒子，B成為C的左兒子，且C的左子樹成為B的右子樹；然后再進(jìn)行右單旋轉(zhuǎn)。
(4)右左雙旋轉(zhuǎn)：
節(jié)點(diǎn)C和節(jié)點(diǎn)B順時(shí)針轉(zhuǎn)動，C成為節(jié)點(diǎn)A的右兒子，B成為C的右兒子，且C的右子樹成為B的左子樹；然后再進(jìn)行左單旋轉(zhuǎn)。
AVL樹的插入
從一個(gè)空樹開始，給定輸入序列，要求建立AVL樹，此時(shí)涉及到AVL樹的插入問題。在插入時(shí)需要判斷每個(gè)節(jié)點(diǎn)的平衡因子，并在失去平衡時(shí)用到之前所說的旋轉(zhuǎn)平衡。
/%CA%FD%BE%DD%BD%E1%B9%B9/lesson/ch07/picture/34.JPG)
/%CA%FD%BE%DD%BD%E1%B9%B9/lesson/ch07/picture/35.JPG)
插入函數(shù)執(zhí)行將值為x的新節(jié)點(diǎn)插入到AVL樹的恰當(dāng)位置，并做平衡處理的功能。
(1)先判斷是否為空樹，若是則為新節(jié)點(diǎn)動態(tài)分配存儲空間，然后置success為1，再將taller置為1。如果不是，根據(jù)新節(jié)點(diǎn)與根節(jié)點(diǎn)的大小判斷，分成左右子樹兩種情況討論，做下述操作。
(2)算法從樹的根結(jié)點(diǎn)開始，遞歸向下找插入位置。在找到插入位置(空指針)后，為新結(jié)點(diǎn)動態(tài)分配存儲空間，將它作為葉結(jié)點(diǎn)插入，并置success為1，再將taller置為1，以表明插入成功。在退出遞歸沿插入路徑向上返回時(shí)做必要的調(diào)整，即判斷是否需要旋轉(zhuǎn)平衡。
AVL樹的刪除
如果被刪結(jié)點(diǎn)x最多只有一個(gè)子女，那么問題比較簡單。如果被刪結(jié)點(diǎn)x有兩個(gè)子女，首先搜索x 在中序次序下的直接前驅(qū) y (同樣可以找直接后繼)。再把結(jié)點(diǎn)y 的內(nèi)容傳送給結(jié)點(diǎn)x，現(xiàn)在問題轉(zhuǎn)移到刪除結(jié)點(diǎn)y。
將結(jié)點(diǎn)y從樹中刪去。因?yàn)榻Y(jié)點(diǎn)y最多有一個(gè)子女，我們可以簡單地把y的父親結(jié)點(diǎn)中原來指向y的指針改指到這個(gè)子女結(jié)點(diǎn)；如果結(jié)點(diǎn)y沒有子女，y父親結(jié)點(diǎn)的相應(yīng)指針置為NULL。然后將原來以結(jié)點(diǎn)y為根的子樹的高度減1，必須沿x 通向根的路徑反向追蹤高度的變化對路徑上各個(gè)結(jié)點(diǎn)的影響。
詳細(xì)內(nèi)容和源代碼可以參看以下鏈接：
http://spec.cumtcs.net/%CA%FD%BE%DD%BD%E1%B9%B9(%D0%C2)/%CA%FD%BE%DD%BD%E1%B9%B9/lesson/ch07/0706.html