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
In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.
When the ...
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 in a tree of keys, and the behavior observed in practice is typically that same multiple faster than the worst-case bound, close to the optimal nodes examined that would be observed in a perfectly balanced tree.
Specifically, in a left-leaning red-black
2–3 tree
In computer science, a 2–3 tree is a tree data structure, where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. A 2–3 tree is a B-tree of order 3 ...
built from random keys:
* A random successful search examines nodes.
* The average tree height is about
* The average size of left subtree exhibits log-oscillating behavior.
External links
Papers
Robert Sedgewick. Left-leaning Red–Black TreesDirect link to PDF
* Robert Sedgewick. Left-Leaning Red–Black Trees (slides). Two versions:
*
Robert Sedgewick. Left-Leaning Red–Black Trees (slides), from seminar at Dagstuhl in February 2008. Outdated.
*
Robert Sedgewick. Left-Leaning Red–Black Trees (slides), from April 2008; updated
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
Implementations
Other
Robert Sedgewick. 20 Apr 2008. Animations of LLRB operations
Pat Morin
Patrick Ryan Morin is a Canadian computer scientist specializing in computational geometry and data structures. He is a professor in the School of Computer Science at Carleton University.
Education and career
Morin was educated at Carleton Univers ...
* ttp://read.seas.harvard.edu/~kohler/notes/llrb.html Left-Leaning Red-Black Trees Considered Harmful
Search trees
{{algorithm-stub