View source for 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 (computer scientist)|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 (computer scientist)|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.<ref name="Sedgewick">{{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 |work=Left-Leaning Red–Black Trees |publisher=Department of Computer Science, Princeton University}}</ref>

== 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 (graph theory)|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:
# <li value="6"> 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|thumb|alt=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.|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 [[bijection|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.<ref name="Sedgewick" />

== 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<sub>2</sub> ''N'' &minus; 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 (programming language)|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==
{{reflist}}

== 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]

{{CS-Trees}}

{{DEFAULTSORT:Llrb Tree}}
[[Category:Search trees]]


{{algorithm-stub}}