Left-leaning red–black tree

From Wikipedia, the free encyclopedia
  (Redirected from LLRB tree)
Jump to: navigation, search
Left-leaning red–black tree
Type Tree
Invented 2008
Invented by Robert Sedgewick
Time complexity
in big O notation
Average Worst case
Space O(n) O(n)
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)

A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree. It is a variant of the red–black tree and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement.

Properties of Left Leaning RB[edit]

All of the red-black tree algorithms that have been proposed are characterized by a worst-case search time bounded by a small constant multiple of lg N in a tree of N keys, and the behavior observed in practice is typically that same multiple faster than the worst-case bound, close the to optimal lg N nodes examined that would be observed in a perfectly balanced tree.

Specifically, in a left-leaning red-black 2-3 tree built from N random keys:

  • A random successful search examines lg N – 0.5 nodes.
  • The average tree height is about 2 ln N (!)
  • The average size of left subtree exhibits log-oscillating behavior.

External links[edit]

Papers[edit]

Implementations[edit]

Author Date Language Variant Notes Link
Robert Sedgewick, rkapsi 2008 Java From this 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

Other[edit]