一、AVL樹
二、AVL樹的實作
1、資料結構
節點類：因為需要控制節點的高度，是以高度是一個屬性。指針域包括left、right，parent可以包括也可以不要，本文的實作中，我們包括parent。
2、節點的平衡
當插入新的節點或者删除節點時，會導緻樹的不平衡，即其中有節點的左右子樹的高度相差>1，這個時候就需要調節樹使之平衡。可能出現不平衡的情況總共有以下幾種：
////////////////////////////////////////
a a a a
/ / \ \
b b b b
/ \ / \
c c c c
LL LR RL RR
//////////////////////////////////////
總共就隻會出現這四種情況，對這四種情況的分類很多書上有各自的說法。其中1、4和2、3是對稱的，我們用LL、LR、RL、RR來分别表示，要使這幾種情況平衡，我們隻用做簡單的旋轉操作就OK了，針對1、4，有的說法是做單旋，有的說法是外旋，而2、3，則做雙旋或内旋，不管是哪種說法，其本質是不變的。在我們的實作中，采用單旋和雙旋，雙旋就是做兩次單旋：
3、平衡的修複
在插入節點和删除節點的時候，會破壞樹的平衡條件，這個時候就需要修複。我們采用盡可能少地改動原有代碼的原則來修複，這個原則和紅黑樹的修複操作是一緻的，即插入和删除操作我們依然沿用二叉搜尋樹的實作，隻在後面添加修複的代碼即可。
如何修複？首先，插入和删除會破壞節點的高度，是以，應更新結點的高度；其次，插入和删除破壞了樹中某些節點的平衡，是以，應針對上面四種情況分别平衡節點。是以，這裡就需要兩個函數：一個更新結點高度的函數UpdateHeight( AVLNode *node )；一個平衡節點的函數： BalanceNode( AVLNode *node )。
基本上該注意的點都提到了，下面附上詳細代碼實作：
View Code