高度平衡二元樹

Input: 10, 20, 39, 42, 45, 49, 51, 63, 70, 75, 80

高度越來越大 → 搜尋時間變大

高度平衡二元搜尋樹 ( height balanced binary search tree ) Adelson-Velskii 與 Landis 提出

空樹(empty tree)為AVL-tree

若 T 不是空樹，則 TL 和 TR 皆為AVL-tree | hL – hR | ≧ 1 內部節點的左子樹高度和右子樹高度，
相差小於或等於1

平衡因子(balanced factor)，BF(v)：節點v的平衡因子 左子樹高度(hL) – 右子樹高度(hR) 每一節點的平衡因子為
– 1、0、1 ↔ | BF(v) | ≦ 1

如果喜歡我們的網頁的話，不要忘記點最上方的讚喔!!