Red-black Tree

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

• Binary Search Trees

Overview

Red-black trees were invented by Bayer (1972) and Guibas, Sedgewick (1978).

• Self-balancing.
• O(log n) operations.