Meeting 37: Balancing Trees -- Red-Black Trees
Today we will see an algorithm for balancing a binary search tree that guarantees O(log n) insert, remove, and search.
- Review of Binary Search Trees
- Review of left/right rotations
- Augmenting the nodes with colors
- Red-Black Tree properties
- Insert algorithm
- Remove algorithm
Links