Left-leaning red–black tree
Left-leaning red–black tree | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
![]() | ||||||||||||||||||||||||
Type | tree | |||||||||||||||||||||||
Invented | 2008 | |||||||||||||||||||||||
Invented by | Robert Sedgewick | |||||||||||||||||||||||
|
A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree, introduced by Robert Sedgewick. 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.[1]
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 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 implementation search tree operations.
Relation to 2–3 and 2–3–4 trees
![A 2-node maps to a single black node. A 3-node maps to a black node with a left red child. A 4-node maps to a black node with two red children.](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Left-leaning_red-black_trees_and_2%E2%80%933%E2%80%934_trees.svg/220px-Left-leaning_red-black_trees_and_2%E2%80%933%E2%80%934_trees.svg.png)
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.[1]
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 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, Sedgewick's experiments suggest that:
- A random successful search examines log2 N − 0.5 nodes.
- The average tree height is about 2 ln N.
- The average size of left subtree exhibits log-oscillating behavior.
Bibliography
- Robert Sedgewick's Java implementation of LLRB from his 2008 paper
- Robert Sedgewick. 20 Apr 2008. Animations of LLRB operations
- Open Data Structures - Section 9.2.2 - Left-Leaning Red–Black Trees, Pat Morin
References
- ^ a b Sedgewick, Robert (2008). "Left-Leaning Red–Black Trees" (PDF). Left-Leaning Red–Black Trees. Department of Computer Science, Princeton University.
External links
- Robert Sedgewick. Left-leaning Red–Black Trees. Direct link to PDF.
- Robert Sedgewick. Left-Leaning Red–Black Trees 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
- Left-Leaning Red-Black Trees Considered Harmful
- v
- t
- e
(dynamic sets/associative arrays)
- 2–3
- 2–3–4
- AA
- (a,b)
- AVL
- B
- B+
- B*
- Bx
- (Optimal) Binary search
- Dancing
- HTree
- Interval
- Order statistic
- Palindrome
- (Left-leaning) Red–black
- Scapegoat
- Splay
- T
- Treap
- UB
- Weight-balanced
![]() | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e