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

Internal

• Binary Search Trees

Overview

Red-black trees were invented in 1970s.

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