Left-leaning red–black tree: Difference between revisions
Procyon117 (talk | contribs) m v2.05 - Fix errors for CW project (Reference list missing) |
Undid revision 1220003608 by Noamz (talk) Tag: Reverted |
||
Line 37: | Line 37: | ||
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. |
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 |
Specifically, in a left-leaning red-black [[2–3 tree]] built from {{mvar|N}} random keys, Sedgewick's experimental results suggest that: |
||
* A random successful search examines {{math|log<sub>2</sub> ''N'' − 0.5}} nodes. |
* A random successful search examines {{math|log<sub>2</sub> ''N'' − 0.5}} nodes. |
||
* The average tree height is about {{math|2 |
* The average tree height is about {{math|2 log<sub>2</sub> ''N''}} |
||
* The average size of left subtree exhibits log-oscillating behavior. |
* The average size of left subtree exhibits log-oscillating behavior. |
||
Revision as of 18:05, 26 April 2024
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.[1] 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.
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:
- A node must not have a red right child.
Relation to 2–3–4 trees
Left-leaning red–black trees are isomorphic to 2–3–4 trees.
To see this, recall that 2–3–4 trees extend binary trees by allowing nodes with three child nodes and two data elements, as well as nodes with four child nodes and three data elements. (These are called 3-nodes and 4-nodes, respectively.) To any conventional red-black tree one can associate a 2–3–4 tree by interpreting red links (that is, links to a red child) as internal links in 3-nodes and 4-nodes. However, this correspondence is not one-to-one, since a 3-node corresponds to a black node with one red child on either the left or the right. That is, 3-nodes may be either "left-leaning" or "right-leaning". By forbidding nodes from having right red children, we thereby obtain a one-to-one correspondence between left-leaning red–black trees and 2–3–4 trees.
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 experimental results suggest that:
- A random successful search examines log2 N − 0.5 nodes.
- The average tree height is about 2 log2 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
- ^ 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