平衡二叉搜尋樹（英語：Balanced Binary Tree）是一種結構平衡的二叉搜尋樹，即葉節點高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
基本介紹
- 中文名：平衡二叉查找樹
- 外文名：Balanced Binary Tree
簡介,AVL樹,紅黑樹,
簡介
平衡二叉搜尋樹（英語：Balanced Binary Tree）是一種結構平衡的二叉搜尋樹，即葉節點高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。它能在O(
)內完成插入、查找和刪除操作，最早被發明的平衡二叉搜尋樹為AVL樹。
常見的平衡二叉搜尋樹有：
- 節點大小平衡樹
AVL樹
在計算機科學中，AVL樹是最早被發明的自平衡二叉查找樹。在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間複雜度都是
。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉，以實現樹的重新平衡。AVL樹得名於它的發明者G. M. Adelson-Velsky和Evgenii Landis，他們在1962年的論文《An algorithm for the organization of information》中公開了這一數據結構。
節點的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子1、0或 -1的節點被認為是平衡的。帶有平衡因子 -2或2的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。
