平衡二叉搜索樹

（1）

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