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.

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)
David Anson 2 Jun 2009 C# Maintaining balance: A versatile red-black tree implementation for .NET
kazu-yamamoto 2011 Haskell llrbtree
Haskell 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
Vala Gee.TreeMap
Petar Maymounkov 2010 Go GoLLRB

Other[edit]