Left-leaning red–black tree

From Wikipedia, the free encyclopedia
Left-leaning red–black tree
Invented byRobert Sedgewick
Time complexity in big O notation
Algorithm 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 a left-leaning red–black tree[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 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.

External links[edit]



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)
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 Ahern 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 2-3 GoLLRB
Jim Fisher 2012 C Verifying a balanced-tree index implementation in Verifast
Sebastien Chapuis 2015 C C - Left-leaning rbtree implementation

Seungyoung Kim 2015 C 2-3-4 variant C implementation
Robin Heggelund Hansen 2018 Elm Elm implementation
R Pratap Chakravarthy 2019 Rust Rust implementation
Max Goren 2022 C++ 2-3 Full Recursive Implementation C++ implementation
Valeriano Della Longa 2021 Swift 2-3 Conformance to BidirectionalCollection protocol with O(1) complexity for firstIndex, endIndex, first, last, min and max. Swift implementation
Filza & Ahmed 2021 Python https://www.youtube.com/channel/UCm68_MratG7meGtzTbkS_3g/featured
Seungyoung Kim 2023 Go 2-3-4 and 2-3 GoMapLLRB