Red-black Tree: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 15: Line 15:
# The root is always black.
# The root is always black.
# There are never 2 red nodes in a row (a red node has only black children).
# There are never 2 red nodes in a row (a red node has only black children).
# Every path taken from root to a NULL pointer has the same number of black nodes.
# Every path taken from root to a NULL pointer has the same number of black nodes (Red makes a node "invisible" to the invariant 4).


These invariants are in addition to the fact that the red-black tree is a binary search tree, so it has the [[Binary_Search_Trees#Binary_Search_Tree_Property|Binary Search Tree Property]].
These invariants are in addition to the fact that the red-black tree is a binary search tree, so it has the [[Binary_Search_Trees#Binary_Search_Tree_Property|Binary Search Tree Property]].
Red makes a node "invisible" to the invariant 4.


=Red-black Trees Maintain Small Heights=
=Red-black Trees Maintain Small Heights=


If all these invariants are satisfied at all times, the height of the tree is going to be small.
If all these invariants are satisfied at all times, the height of the tree is going to be small.

Revision as of 05:07, 13 October 2021

External

Internal

Overview

Red-black trees have been invented by Bayer (1972) and Guibas, Sedgewick (1978). A red-black tree is a type of binary search tree that self-balances on insertion and deletion, thus maintaining its height to a minimum, which leads to efficient operations. Almost all binary search tree operations have a running time bounded by the tree height, and in this case the tree height stays constant at log n, yielding O(log n) operations.

Red-black Tree Invariants

  1. Each node is either red or black.
  2. The root is always black.
  3. There are never 2 red nodes in a row (a red node has only black children).
  4. Every path taken from root to a NULL pointer has the same number of black nodes (Red makes a node "invisible" to the invariant 4).

These invariants are in addition to the fact that the red-black tree is a binary search tree, so it has the Binary Search Tree Property.

Red-black Trees Maintain Small Heights

If all these invariants are satisfied at all times, the height of the tree is going to be small.