AVL Tree (Height Balanced BST)

1.特 性

• 空樹是高度平衡樹，若T不是空樹且左右子樹分別為TL與TR

• 若且唯若T是高度平衡樹，則須滿足以下兩個條件：

  • 1.TL 和 TR也是高度平衡樹

  • 2.|hL-hR|<=1, 其中hL和hR分別是TL和TR的高度(D→L的距離 = hL, D→R的距離 = hR)

• AVL樹可在O(log N)時間內完成插入、刪除或修改，且於插入、刪除或修改後，所得的樹仍須保持為高度平衡二元樹

• BST的最壞情況為O(N), AVL最壞仍是O(log N)