Left-leaning red–black tree

Left-leaning red–black tree
Left-leaning red–black tree
Type	tree
Invented	2008
Invented by	Robert Sedgewick
Operation
Time complexity in big O notation
Operation	Average
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Space complexity
Space	O(n)

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 edit

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 edit

Isomorphism between LLRB trees 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.^[1]

Analysis edit

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 $log 2 N - 0.5$ nodes.
The average tree height is about $2 ln N$
The average size of left subtree exhibits log-oscillating behavior.

Bibliography edit

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 edit

^ ^a ^b Sedgewick, Robert (2008). "Left-Leaning Red–Black Trees" (PDF). Left-Leaning Red–Black Trees. Department of Computer Science, Princeton University.

External links edit

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

[Sedgewick-1] Sedgewick, Robert (2008). "Left-Leaning Red–Black Trees" (PDF). Left-Leaning Red–Black Trees. Department of Computer Science, Princeton University.

[1]