570 B
570 B
Outline
- Review homework and do some tree exercises
- Introduce tree balancing
- Introduce red-black trees
- Basic properties
- Root property: the root is black
- External property: every nil child pointer is considered a black node
- Internal property: children and parents of a red node are black
- Depth property: all nodes have the same black depth
- Insertion and balancing algorithms
- Assignment: implement red-black tree balancing