Left-leaning red–black tree | |
Type: | tree |
Invented By: | Robert Sedgewick |
Invented Year: | 2008 |
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]
A left-leaning red-black tree satisfies all the properties of a red-black tree:
Additionally, the left-leaning property states that:
The left-leaning property reduces the number of cases that must be considered when implementation search tree operations.
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.
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 built from random keys, Sedgewick's experiments suggest that: