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