從二叉搜尋樹到平衡二叉搜尋樹

二叉搜尋樹的中序序列相同，則稱它們彼此等價。兩個等價的二叉搜尋樹，可能在形态上存在拓普茶藝，各個節點的垂直高度可能有所不同，但水準次序完全相同，可簡化為“上下可變，左右不可變”。

一個二叉搜尋樹（要求有序）需要支援的主要接口有：

search()

insert()

remove()

三者的時間複雜度均正比于二叉樹的高度。在最壞的情況下，所有的内部結點（根和葉子除外），均為左孩子結點或右孩子結點。此時的查找效率甚至會降至 o(n)，線性正比于資料集的規模。故若不能有效地控制樹高，則就實際的性能而言，相比此前的向量和清單，二叉搜尋樹将無法體會出明顯優勢。

證明含 n 個結點的二叉樹的最小高度為 ⌊log2n⌋（同時也是完全二叉樹（線性表存儲）的樹高）。

高度為 h 的二叉樹結點與樹高的關系為：

n≤2h+1−1

等号成立，當且僅當二叉樹是滿樹。

h≥⌈log2(n+1)⌉−1=⌊log2n⌋