平衡二叉搜尋樹

平衡二叉搜尋樹，解釋為任何結點的左子樹和右子樹高度相差1的。

基本內容

任何結點的左子樹和右子樹高度最多相差1的二叉搜尋樹。

（1）AVL樹的插入算法

a. 插入結點之後仍然是AVL樹，則不調整；

b. 插入結點之後不再滿足AVL樹條件，則進行調整，根據導致不平衡的原因，分為：

a) LL型――單旋轉調整

b) LR型――雙旋轉調整

c) RL型――雙旋轉調整

d) RR型――單旋轉調整

下圖是順序插入單詞{cup，cop，copy，hit，hi，his，hia}後得到的AVL樹，單詞之間按照字典順序比較：

（2）AVL樹的刪除算法

a. 刪除過程如BST結點的刪除算法（教材算法4.16）；

b. 刪除後調整――從被刪除的結點找到祖父結點，然後開始單旋轉或多旋轉操作，一次旋轉結束並不 意味著樹已經平衡，因為這可能會導致它的祖先結點發生新的不平衡。所以這樣的調整操作要一直進行下去，直到樹平衡為止。