首先給AVL樹下個定義：
一棵AVL樹或者是空樹，或者是具有下列性質的二叉搜索樹：它的任意節點的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對值不超過1。

下面做簡要分析：
(1)AVL樹首先是個二叉搜索樹，對任意節點a，比a數值小的節點在左子樹上，比a數值大的節點在右子樹上。
(2)AVL樹高度平衡。每個結點附加一個數字，給出該結點右子樹的高度減去左子樹的高度所得的高度差。這個數字即為結點的平衡因子balance。根據AVL樹的定義，任一結點的平衡因子只能取 -1，0、1。假設有N個節點，那么其高度可保持在O(log2n)，平均搜索長度也可保持在O(log2n)。
(3)添加節點導致不平衡時，需進行平衡化旋轉。

平衡化旋轉：

平衡化旋轉有兩類：
(1)單旋轉 (左旋和右旋)
(2)雙旋轉 (左平衡和右平衡)

每插入一個新結點時，AVL樹中相關結點的平衡狀態可能會發生改變。因此，在插入一個新結點后，需要從插入位置沿通向根的路徑回溯，檢查各結點的平衡因子(左、右子樹的高度差)。 如果在某一結點發現高度不平衡，停止回溯。

從發生不平衡的結點起，沿剛才回溯的路徑取直接下兩層的結點。此時分為兩種情況：
(1)如果這三個結點處于一條直線上，則采用單旋轉進行平衡化。單旋轉可按其方向分為左單旋轉和右單旋轉，其中一個是另一個的鏡像，其方向與不平衡的形狀相關。
(2)如果這三個結點處于一條折線上，則采用雙旋轉進行平衡化。雙旋轉分為先左后右和先右后左兩類。



假設以上三個節點從上至下分別為A、B、C，則有：
(1)右單旋轉：
以節點B為軸，節點A順時針旋轉，成為節點B的右兒子，節點B原右子樹成為節點A的左子樹。
(2)左單旋轉：
以節點B為軸，節點A逆時針旋轉，成為節點B的左兒子，節點B原左子樹成為節點A的右子樹。
(3)左右雙旋轉：
節點C和節點B逆時針轉動，C成為節點A的左兒子，B成為C的左兒子，且C的左子樹成為B的右子樹；然后再進行右單旋轉。
(4)右左雙旋轉：
節點C和節點B順時針轉動，C成為節點A的右兒子，B成為C的右兒子，且C的右子樹成為B的左子樹；然后再進行左單旋轉。

AVL樹的插入

從一個空樹開始，給定輸入序列，要求建立AVL樹，此時涉及到AVL樹的插入問題。在插入時需要判斷每個節點的平衡因子，并在失去平衡時用到之前所說的旋轉平衡。

插入函數執行將值為x的新節點插入到AVL樹的恰當位置，并做平衡處理的功能。
(1)先判斷是否為空樹，若是則為新節點動態分配存儲空間，然后置success為1，再將taller置為1。如果不是，根據新節點與根節點的大小判斷，分成左右子樹兩種情況討論，做下述操作。
(2)算法從樹的根結點開始，遞歸向下找插入位置。在找到插入位置(空指針)后，為新結點動態分配存儲空間，將它作為葉結點插入，并置success為1，再將taller置為1，以表明插入成功。在退出遞歸沿插入路徑向上返回時做必要的調整，即判斷是否需要旋轉平衡。

AVL樹的刪除

如果被刪結點x最多只有一個子女，那么問題比較簡單。如果被刪結點x有兩個子女，首先搜索x 在中序次序下的直接前驅 y (同樣可以找直接后繼)。再把結點y 的內容傳送給結點x，現在問題轉移到刪除結點y。

將結點y從樹中刪去。因為結點y最多有一個子女，我們可以簡單地把y的父親結點中原來指向y的指針改指到這個子女結點；如果結點y沒有子女，y父親結點的相應指針置為NULL。然后將原來以結點y為根的子樹的高度減1，必須沿x 通向根的路徑反向追蹤高度的變化對路徑上各個結點的影響。


詳細內容和源代碼可以參看以下鏈接：
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