Red-black Tree: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 9: Line 9:


=Overview=
=Overview=
Red-black trees were invented by Bayer (1972) and Guibas, Sedgewick (1978). A red-black tree is a type of [[Binary_Search_Trees#Overview|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_Trees#Supported_Operations|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 trees were invented by Bayer (1972) and Guibas, Sedgewick (1978). A red-black tree is a type of [[Binary_Search_Trees#Overview|binary search tree]] that self-balances on insertion and deletion, thus maintaining its height to a minimum, which allows for efficient operations. Almost all [[Binary_Search_Trees#Supported_Operations|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=
=Red-black Tree Invariants=

Revision as of 16:40, 13 October 2021

External

Internal

Overview

Red-black trees were 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 allows for 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.