A left-leaning red–black (LLRB) tree is a type of
self-balancing binary search tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...
, introduced by
Robert Sedgewick. It is a variant of the
red–black tree
In computer science, a red–black tree is a self-balancing binary search tree data structure noted for fast storage and retrieval of ordered information. The nodes in a red-black tree hold an extra "color" bit, often drawn as red and black, wh ...
and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement.
Properties
A left-leaning red-black tree satisfies all the properties of a red-black tree:
# Every node is either red or black.
# A NIL node is considered black.
# A red node does not have a red child.
# Every
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desir ...
from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
# The root is black (by convention).
Additionally, the left-leaning property states that:
#
If a node has only one red child, it must be the left child.
The left-leaning property reduces the number of cases that must be considered when implementing search tree operations.
Relation to 2–3 and 2–3–4 trees
LLRB trees are isomorphic 2–3–4 trees. Unlike conventional red-black trees, the 3-nodes always lean left, making this relationship a 1 to 1 correspondence. This means that for every LLRB tree, there is a unique corresponding 2–3–4 tree, and vice versa.
If we impose the additional requirement that a node may not have two red children, LLRB trees become isomorphic to 2–3 trees, since 4-nodes are now prohibited. Sedgewick remarks that the implementations of LLRB 2–3 trees and LLRB 2–3–4 trees differ only in the position of a single line of code.
Analysis
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-node) and two data elements. A 2–3 tree is a B-tree of order 3 ...
built from random keys, Sedgewick's experiments suggest that:
* A random successful search examines nodes.
* The average tree height is about .
* The average size of left subtree exhibits log-oscillating behavior.
Bibliography
* Robert Sedgewick's Java
Java is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...
implementation of LLRB fro
his 2008 paper
Robert Sedgewick. 20 Apr 2008. Animations of LLRB operations
Pat Morin
References
External links
Robert Sedgewick. Left-leaning Red–Black TreesDirect link to PDF
* Robert Sedgewick. Left-Leaning Red–Black Tree
slides from October 2008
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
Search trees
{{algorithm-stub