Jump to content

Left-leaning red–black tree

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 50.25.15.23 (talk) at 21:22, 6 September 2016 (Implementations: Remove the GitHub gist since it has been erased and it also not on archive.org). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Left-leaning red–black tree
Typetree
Invented2008
Invented byRobert Sedgewick
Time complexity in big O notation
Operation Average Worst case
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)
Space complexity
Space O(n) O(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

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 log 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 to the optimal log 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 log2 N − 0.5 nodes.
  • The average tree height is about 2 log2 N
  • The average size of left subtree exhibits log-oscillating behavior.

Papers

Implementations

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