Red-black Tree: Difference between revisions
Jump to navigation
Jump to search
| Line 9: | Line 9: | ||
=Overview= | =Overview= | ||
Red-black trees were invented by Bayer (1972) and Guibas, Sedgewick (1978). | 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. | * Self-balancing. | ||
* O(log n) operations. | * O(log n) operations. | ||
Revision as of 04:47, 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 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.