左傾紅黑樹

左傾紅黑樹（LLRB）是一種類型的自平衡二叉查找樹。它是紅黑樹的變體，並保證對操作相同漸近的複雜性，但被設計成更容易實現。

基本介紹

• 中文名：左傾紅黑樹
• 外文名：Self-balancing binary search tree

實現

作者	時間	語言	變體	附註	連結
Robert Sedgewick, rkapsi	2008	Java	-	Fromthis Sedgewick paper	Left-leaning Red–Black Tree (LLRB)-- this code has errors, see github comments
David Anson	2 Jun 2009	C#	-	-	Maintaining balance: A versatile red-black tree implementation for .NET
kazu-yamamoto	2011	Haskell	-	-	llrbtree(Data.Set.LLRBTree)
gradbot	2010	F#	-	-	f-sharp-llrbt
Lee Stanza	2010	C	-	Includes discussion	Balanced Trees, Part 4: Left Leaning Red–Black Trees
Jason Evans	2010	C	2-3	-	rb.h
Nicola Bortignon	December 8, 2010	ActionScript 3	-	-	AS3 implementation and discussion
william at 25thandClement.com	2011	C	2-3 variant using iteration with parent pointers	-	llrb.h: Left-leaning Red–Black Tree
Maciej Piechotka	2009	Vala	-	-	Gee.TreeMap
Petar Maymounkov	2010	Go	-	-	GoLLRB
Sebastien Chapuis	2015	C	-	-	C - Left-leaning rbtree implementation

平衡樹

平衡樹是計算機科學中的一類數據結構。

平衡樹是計算機科學中的一類改進的二叉查找樹。一般的二叉查找樹的查詢複雜度是跟目標結點到樹根的距離（即深度）有關，因此當結點的深度普遍較大時，查詢的均攤複雜度會上升，為了更高效的查詢，平衡樹應運而生了。

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

套用

用於表示有序的線性數據結構，如優先佇列、關聯數組、鍵-值的映射等。自平衡的二叉查找樹的實現與其競爭對手hash表的實現，各自具有優缺點。自平衡二叉查找樹在按序遍歷所有鍵值時是量級最優的，hash表不能。自平衡二叉查找樹在查找一個鍵值時，最壞情況下時間複雜度優於hash表， O(log n)對比O(n)；但平均時間複雜度遜於hash表，O(log n)對比O(1)。

自平衡二叉查找樹的排序方法，雖然在平均時間複雜度上也是O(n log n)，但由於cache性能、樹的調整操作等，性能上不如快速排序、堆排序、合併排序。