Red-black Tree
Jump to navigation
Jump to search
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 were invented by Bayer (1972) and Guibas, Sedgewick (1978). They are a type of binary search tree that self-balance on insertion and deletion, thus keeping their height to a minimum, which leads to efficient operations (almost all operations on binary trees have running time bounded by the tree height, and in this case the tree height stays constant at log n).
- Self-balancing.
- O(log n) operations.