Red-black Tree: Difference between revisions
Jump to navigation
Jump to search
| Line 11: | Line 11: | ||
Red-black trees had been invented by Bayer (1972) and Guibas, Sedgewick (1978). They are 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 had been invented by Bayer (1972) and Guibas, Sedgewick (1978). They are 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 Tree Invariants= | =Red-Black Tree Invariants= | ||
# Each node | # Each node is either red or black. | ||
# | # The root is always black. | ||
# 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. | |||
Revision as of 04:57, 13 October 2021
External
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/8acpe/red-black-trees
- https://www.youtube.com/watch?v=scfDOof9pww
- https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Internal
Overview
Red-black trees had been invented by Bayer (1972) and Guibas, Sedgewick (1978). They are 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
- Each node is either red or black.
- The root is always black.
- 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.