Tu banner alternativo

Left-leaning red–black tree

In today's world, Left-leaning red–black tree is a topic of great relevance and interest to a wide audience. From its origins to its impact on society, Left-leaning red–black tree has been the subject of study and debate in different areas. Over time, Left-leaning red–black tree has evolved and adapted to changes, maintaining its influence on various aspects of daily life. In this article, we will explore the importance of Left-leaning red–black tree, analyzing its different dimensions and its relevance in the contemporary world. Through a comprehensive analysis, we will seek to better understand the importance of Left-leaning red–black tree and its influence on our society.

Tu banner alternativo
Left-leaning red–black tree
Typetree
Invented2008
Invented byRobert Sedgewick
Time complexity in big O notation
Operation Average Worst case
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)
Space complexity
Space O(n) 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

A left-leaning red-black tree satisfies all the properties of a red-black tree:

  1. Every node is either red or black.
  2. A NIL node is considered black.
  3. A red node does not have a red child.
  4. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
  5. The root is black (by convention).

Additionally, the left-leaning property states that:

  2. 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

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

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

References

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


Stub icon

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

Wikious
Boobota
Sagapedia