題組內容

三、AVL 樹是學者 G.M.Adelson-Velsky 和 E.M.Landis，於 1962 年的發表論文《An algorithm for the organization of information》而成名。

(一)請問何謂 AVL 樹？（5 分）

詳解 (共 4 筆)

詳解 提供者：kkcs60584
AVL樹是最先發明的自平衡二元搜尋樹。在AVL樹中任何節點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O（log n）。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。AVL樹得名於它的發明者G.M. Adelson-Velsky和E.M. Landis，他們在1962年的論文《An algorithm for the organization of information》中發表了它。 節點的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子1、0或 -1的節點被認為是平衡的。帶有平衡因子 -2或2的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。
詳解 提供者：gx4yes
詳解 提供者：果凍羊
詳解 提供者：我還有明天

AVL Tree定義：

1.為一二元搜尋樹(BST)

2.所有節點之左右子樹高度差<=1