Left-leaning red–black tree

{{Short description|Self-balancing binary search tree data structure}}

{{Infobox data structure

|name=Left-leaning red–black tree

|image = Left-leaning_red–black_tree.png

|type=tree

|invented_by=Robert Sedgewick

|invented_year=2008

|space_avg={{math|O(n)}}

|space_worst={{math|O(n)}}

|search_avg={{math|O(log n)}}

|search_worst={{math|O(log n)}}

|insert_avg={{math|O(log n)}}

|insert_worst={{math|O(log n)}}

|delete_avg={{math|O(log n)}}

|delete_worst={{math|O(log 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.{{cite web |last=Sedgewick |first=Robert |year=2008 |title=Left-Leaning Red–Black Trees |url=http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf |publisher=Department of Computer Science, Princeton University}}

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 implementing search tree operations.

Relation to 2–3 and 2–3–4 trees

File:Left-leaning red-black trees and 2–3–4 trees.svg

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 {{math|log N}} in a tree of {{mvar|N}} keys, and the behavior observed in practice is typically that same multiple faster than the worst-case bound, close to the optimal {{math|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 {{mvar|N}} random keys, Sedgewick's experiments suggest that:

A random successful search examines {{math|log₂ N − 0.5}} nodes.
The average tree height is about {{math|2 ln N}}.
The average size of left subtree exhibits log-oscillating behavior.

Bibliography

Robert Sedgewick's Java implementation of LLRB from [https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf his 2008 paper]
[http://www.cs.princeton.edu/~rs/talks/LLRB/movies/ Robert Sedgewick. 20 Apr 2008. Animations of LLRB operations]
[http://opendatastructures.org/versions/edition-0.1e/ods-java/9_2_RedBlackTree_Simulated_.html#SECTION001222000000000000000 Open Data Structures - Section 9.2.2 - Left-Leaning Red–Black Trees], Pat Morin

References

External links

[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.282 Robert Sedgewick. Left-leaning Red–Black Trees]. [https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf Direct link to PDF].
Robert Sedgewick. Left-Leaning Red–Black Trees [https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf slides from October 2008].
[https://web.archive.org/web/20170207072643/https://web.student.chalmers.se/groups/datx02-dtp/ Linus Ek, Ola Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda]
[https://web.archive.org/web/20160304043338/http://www.reinference.net/llrb-delete-julien-oster.pdf Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees]
[http://www.mew.org/~kazu/proj/red-black-tree/ Kazu Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees]
[http://read.seas.harvard.edu/~kohler/notes/llrb.html Left-Leaning Red-Black Trees Considered Harmful]

Category:Search trees