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

不平衡的樹結構

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

平衡的樹結構

基本操作

編輯

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

插入(insert):在樹中插入一個新值。

刪除(delete):在樹中刪除一個值。

查詢前驅(predecessor):前驅定義為小於x,且最大的數。

查詢後繼(successor):後繼定義為大於x,且最小的數。

在維護節點大小(size)後,可以支援以下操作:

查詢排名(rank):排名定義為比x小的數的個數加一。

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

各種平衡樹

編輯
  • AVL樹:是最早被發明的自平衡二叉搜尋樹。在AVL樹中,任一節點對應的兩棵子樹的最大高度差為1,因此它也被稱為高度平衡樹。尋找、插入和刪除在平均和最壞情況下的時間複雜度都是 。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉,以實現樹的重新平衡。AVL樹得名於它的發明者G. M. Adelson-Velsky和Evgenii Landis,他們在1962年的論文An algorithm for the organization of information 中公開了這一數據結構。 節點的平衡因子是它的左子樹的高度減去它的右子樹的高度(有時相反)。帶有平衡因子1、0或 -1的節點被認為是平衡的。帶有平衡因子 -2或2的節點被認為是不平衡的,並需要重新平衡這個樹。平衡因子可以直接儲存在每個節點中,或從可能儲存在節點中的子樹高度計算出來。
  • 樹堆(Treap):是有一個隨機附加域滿足的性質的二叉搜尋樹,其結構相當於以亂數據插入的二叉搜尋樹。其基本操作的期望時間複雜度 。相對於其他的平衡二叉搜尋樹,Treap的特點是實現簡單,且能基本實現隨機平衡的結構。
  • 伸展樹(Splay tree):能在均攤 的時間內完成基於伸展(Splay)操作的插入、尋找、修改和刪除操作。它是由丹尼爾·斯立特(Daniel Sleator)和羅伯特·塔揚在1985年發明的。在伸展樹上的一般操作都基於伸展操作:假設想要對一個二叉搜尋樹執行一系列的尋找操作,為了使整個尋找時間更小,被查頻率高的那些條目就應當經常處於靠近樹根的位置。於是想到設計一個簡單方法,在每次尋找之後對樹進行調整,把被尋找的條目搬移到離樹根近一些的地方。伸展樹應運而生。伸展樹是一種自調整形式的二叉搜尋樹,它會沿着從某個節點到樹根之間的路徑,通過一系列的旋轉把這個節點搬移到樹根去。 它的優勢在於不需要記錄用於平衡樹的冗餘資訊。
  • 紅黑樹 (Red–black tree):在1972年由魯道夫·貝爾發明,被稱為"對稱二元B樹",它現代的名字源於Leo J. Guibas和Robert Sedgewick1978年寫的一篇論文。紅黑樹的結構複雜,但它的操作有着良好的最壞情況執行時間,並且在實踐中高效:它可以在 時間內完成尋找,插入和刪除,這裏的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)乘以自身大小的結點,重建整個子樹。這樣就得到了替罪羊樹,而被重建的子樹的原來的根就被稱為替罪羊節點。

其他類型

編輯

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

應用

編輯

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

平衡樹的排序方法,雖然在平均時間複雜度上也是 ,但由於cache效能、樹的調整操作等,效能上不如快速排序堆積排序合併排序等同為 複雜度的排序。

參考文獻

編輯
  1. ^ 1.0 1.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.

外部連結

編輯