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