平衡樹

平衡樹是電腦科學中的一類數據結構，為改進的二叉搜尋樹。一般的二叉搜尋樹的查詢複雜度取決於目標結點到樹根的距離（即深度），因此當結點的深度普遍較大時，查詢的均攤複雜度會上升^[1]。為了實現更高效的查詢，產生了平衡樹。

不平衡的樹結構

在這裏，平衡指所有葉子的深度趨於平衡，更廣義的是指在樹上所有可能尋找的均攤複雜度偏低。

平衡的樹結構

基本操作

旋轉（rotate）：幾乎所有平衡樹的操作都基於樹旋轉操作（也有部分基於重構，如替罪羊樹），通過旋轉操作可以使得樹趨於平衡。對一棵尋找樹（search tree）進行查詢、新增、刪除等動作，所花的時間與樹的高度h成比例，並不與樹的容量n成比例。如果可以讓樹維持平衡，也就是讓h維持在${\displaystyle O(\log {n})}$的左右，就可以在${\displaystyle O(\log {n})}$的複雜度內完成各種基本操作^[1]。

插入（insert）：在樹中插入一個新值。

刪除（delete）：在樹中刪除一個值。

查詢前驅（predecessor）：前驅定義為小於x，且最大的數。

查詢後繼（successor）：後繼定義為大於x，且最小的數。

在維護節點大小（size）後，可以支援以下操作：

查詢排名（rank）：排名定義為比x小的數的個數加一。

查詢第k大：即排名為k的數。

各種平衡樹

• AVL樹：是最早被發明的自平衡二叉搜尋樹。在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。尋找、插入和刪除在平均和最壞情況下的時間複雜度都是${\displaystyle O(\log {n})}$。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉，以實現樹的重新平衡。AVL樹得名於它的發明者G. M. Adelson-Velsky和Evgenii Landis，他們在1962年的論文An algorithm for the organization of information 中公開了這一數據結構。 節點的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子1、0或 -1的節點被認為是平衡的。帶有平衡因子 -2或2的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接儲存在每個節點中，或從可能儲存在節點中的子樹高度計算出來。
• 樹堆（Treap）：是有一個隨機附加域滿足堆的性質的二叉搜尋樹，其結構相當於以亂數據插入的二叉搜尋樹。其基本操作的期望時間複雜度為${\displaystyle O(\log {n})}$。相對於其他的平衡二叉搜尋樹，Treap的特點是實現簡單，且能基本實現隨機平衡的結構。
• 伸展樹（Splay tree）：能在均攤${\displaystyle O(\log {n})}$的時間內完成基於伸展（Splay）操作的插入、尋找、修改和刪除操作。它是由丹尼爾·斯立特（Daniel Sleator）和羅伯特·塔揚在1985年發明的。在伸展樹上的一般操作都基於伸展操作：假設想要對一個二叉搜尋樹執行一系列的尋找操作，為了使整個尋找時間更小，被查頻率高的那些條目就應當經常處於靠近樹根的位置。於是想到設計一個簡單方法，在每次尋找之後對樹進行調整，把被尋找的條目搬移到離樹根近一些的地方。伸展樹應運而生。伸展樹是一種自調整形式的二叉搜尋樹，它會沿着從某個節點到樹根之間的路徑，通過一系列的旋轉把這個節點搬移到樹根去。 它的優勢在於不需要記錄用於平衡樹的冗餘資訊。
• 紅黑樹 （Red–black tree）：在1972年由魯道夫·貝爾發明，被稱為"對稱二元B樹"，它現代的名字源於Leo J. Guibas和Robert Sedgewick於1978年寫的一篇論文。紅黑樹的結構複雜，但它的操作有着良好的最壞情況執行時間，並且在實踐中高效：它可以在${\displaystyle O(\log {n})}$時間內完成尋找，插入和刪除，這裏的n是樹中元素的數目。
• 加權平衡樹（Weight balanced tree）：加權平衡樹的每個結點儲存這個結點下子樹的大小，可以用來實現順序統計樹操作。優勢在於佔用空間相對較小。
• 2-3樹：其內部節點（存在子節點的節點）要麼有2個孩子和1個數據元素，要麼有3個孩子和2個數據元素，葉子節點沒有孩子，並且有1個或2個數據元素。2–3樹和AA樹是等距同構的，換句話說，對於每個2–3樹，都至少有1個AA樹和它的元素排列是相同的。
• AA樹：AA樹是紅黑樹的一種變種，是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹，設計的目的是減少紅黑樹考慮的不同情況，區別於紅黑樹的是，AA樹的紅節點只能作為右葉子，從而大大簡化了維護2-3樹的模擬。
• 替罪羊樹：其平衡基於部分重建，在非平衡的二叉搜尋樹中，每次操作以後檢查操作路徑，找到最高的滿足左右子樹大小大於平衡因子（alpha）乘以自身大小的結點，重建整個子樹。這樣就得到了替罪羊樹，而被重建的子樹的原來的根就被稱為替罪羊節點。

其他類型

以下數據結構支援平衡樹大多數操作，但實現有根本不同:

• 跳表
• 有序向量
• 值域線段樹
• 數字搜尋樹（DigitalSearchTree）

應用

用於表示有序的線性數據結構，如優先佇列、關聯陣列、鍵(key)-值(value)的對映等。自平衡的二叉搜尋樹與雜湊表的相比，各有優缺。平衡樹在按序遍歷所有鍵值時是量級最佳的，雜湊表不能。自平衡二叉搜尋樹在尋找一個鍵值時，最壞情況下時間複雜度優於雜湊表， ${\displaystyle O(\log n)}$對比${\displaystyle O(n)}$；但平均時間複雜度遜於hash表，${\displaystyle O(\log n)}$對比${\displaystyle O(1)}$。

平衡樹的排序方法，雖然在平均時間複雜度上也是${\displaystyle O(n\log n)}$，但由於cache效能、樹的調整操作等，效能上不如快速排序、堆積排序、合併排序等同為${\displaystyle O(n\log n)}$複雜度的排序。

參考文獻

1. Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.

外部連結

• Dictionary of Algorithms and Data Structures: Height-balanced binary search tree （頁面存檔備份，存於互聯網檔案館）
• GNU libavl （頁面存檔備份，存於互聯網檔案館）, a LGPL-licensed library of binary tree implementations in C, with documentation