Reading

7.4. Balanced Trees
Explanation of 2-3 trees (and optionally red-black trees) from Sedgewick & Wayne.
- Note: S&W colors the links between nodes instead of the nodes themselves. The color of a link in S&W corresponds in our presentation to the color of the target node of the link.
Optional handout: 2-3 tree deletion

Note: The material on red-black trees is optional. Note that there are many different variants of red-black trees in the literature. The ones of Sedgewick & Wayne are a version of left-leaning red-black trees where a red node is only allowed as a left child of a black node. These have a stricter (weaker) invariant and thus use different operations to fix the invariant when inserting a node than other variants.

Videos and slides

E. 2-3 trees
(F. Red-black trees) (optional)

Note: Check out the tree visualizations (e.g. Gnarley trees) to see self-balancing search trees in action.