Left-leaning red–black tree: Difference between revisions
Fix link, now 2-3 tree link goes to 2-3 tree article, not to 2-3-4 tree article |
→Analysis: correction (base2 log -> natural log), and clarify that these are Sedgewick's experimental results |
||
| Line 34: | Line 34: | ||
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: |
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'' − 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 ln ''N''}} |
||
* The average size of left subtree exhibits log-oscillating behavior. |
* The average size of left subtree exhibits log-oscillating behavior. |
||
Revision as of 06:43, 21 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. 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 trees
In the same way conventional red-black trees are related to 2–3–4 trees, left-leaning red-black trees are isomorphic to 2–3 trees, which are a subtype of 2–3–4 trees. This means that for every left-leaning red-black tree, there is a unique corresponding 2–3 tree, and vice versa. Precisely, each (red left child, black parent) pair corresponds to a degree 3 node in a 2–3 tree, and all other black nodes correspond to degree 2 nodes.
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 experiments suggest that:
- A random successful search examines log2 N − 0.5 nodes.
- The average tree height is about 2 ln N
- The average size of left subtree exhibits log-oscillating behavior.
Bibliography
- Robert Sedgewick's Java implementation of LLRB from his 2008's paper
- Robert Sedgewick. 20 Apr 2008. Animations of LLRB operations
- Open Data Structures - Section 9.2.2 - Left-Leaning Red–Black Trees, Pat Morin
External links
- Robert Sedgewick. Left-leaning Red–Black Trees. Direct link to PDF.
- Robert Sedgewick. Left-Leaning Red–Black Trees slides from April 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
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |