Left-leaning red–black tree
|Left-leaning red–black tree|
|Invented by||Robert Sedgewick|
|Time complexity in big O notation|
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
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.
- Robert Sedgewick. Left-leaning Red–Black Trees. Direct link to PDF.
- Robert Sedgewick. Left-Leaning Red–Black Trees (slides). Two versions:
- Linus Ek, Ola Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda
- Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees
- Kazu Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees
|Robert Sedgewick||2008||Java||From this Sedgewick paper|
|David Anson||2 Jun 2009||C#||Maintaining balance: A versatile red-black tree implementation for .NET|
|Lee Stanza||2010||C++||Includes discussion||Balanced Trees, Part 4: Left Leaning Red–Black Trees|
|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|
|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|
- Robert Sedgewick. 20 Apr 2008. Animations of LLRB operations
- Open Data Structures - Section 9.2.2 - Left-Leaning Red–Black Trees, Pat Morin
- Left-Leaning Red-Black Trees Considered Harmful
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|