17 lines
570 B
Markdown
17 lines
570 B
Markdown
## 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
|
||
|
||
## Resources
|
||
|
||
- [Red-black tree - Wikipedia](https://en.wikipedia.org/wiki/Red–black_tree)
|