平衡二叉搜尋樹的任何結點的左子樹和右子樹高度最多。
基本介紹
- 中文名：平衡二叉搜尋樹
- 玩法：相差1的二叉搜尋樹
- 樹的插入算法：則不調整
- 縮寫：AVL
（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. 刪除後調整――從被刪除的結點找到祖父結點，然後開始單旋轉或多旋轉操作，一次旋轉結束並不 意味著樹已經平衡，因為這可能會導致它的祖先結點發生新的不平衡。所以這樣的調整操作要一直進行下去，直到樹平衡為止。
