> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/avl-tree-height-balanced-bst.md).

# 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)