平衡樹
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目需要補充更多來源。 (2019年7月8日) |
平衡樹是計算機科學中的一類數據結構,為改進的二叉查找樹。一般的二叉查找樹的查詢複雜度取決於目標結點到樹根的距離(即深度),因此當結點的深度普遍較大時,查詢的均攤複雜度會上升[1]。為了實現更高效的查詢,產生了平衡樹。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Unbalanced_binary_tree.svg/240px-Unbalanced_binary_tree.svg.png)
在這裡,平衡指所有葉子的深度趨於平衡,更廣義的是指在樹上所有可能查找的均攤複雜度偏低。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/0/06/AVLtreef.svg/240px-AVLtreef.svg.png)
基本操作
旋轉(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 Sedgewick於1978年寫的一篇論文。紅黑樹的結構複雜,但它的操作有着良好的最壞情況運行時間,並且在實踐中高效:它可以在時間內完成查找,插入和刪除,這裡的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.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.
外部連結
- 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
|
|