August 23, 2023

Topics of the day

• 234-trees
• Red-black trees

Suggested reading

• Section 12.2 from Mark Allen Weiss, Data structures and algorithm analysis in C++, 3e

Online references

• 2-3-4 tree (en.wikipedia.org)
• Red-black tree (en.wikipedia.org)

Questions and exercises

1. Draw at least three different valid 2-3-4 trees that contain the letters A through H in order.
2. Consider a 2-3-4 tree such as the one on the right, with five nodes (one root, four children), each of which is "full" (containing three elements). Draw what happens when a single value is added to the tree.
3. How do red-black trees correspond to 2-3-4 trees?
4. Draw a 2-3-4 tree with at least one of each type of node; then draw a red-black tree that corresponds to it.

Assignments

Today

• Project 1: Balanced binary prep due

Upcoming

• Project 1: Balanced binary design due (28 Aug)

Board photos

.

.