We looked at Search Trees previously, and we knew that they were better if balanced. Now we explore how to automatically keep them balanced.
Most of the algorithms that we will discuss use the ideas of balance and rotation.
We have explored AVL trees very thoroughly.
Adding a new node:
Children are either 2-node or 3-node
If n = 200, then each node has between 100 and 200 children. Tree of height 4 could hold:
$$ 100 ^ 4 $$
or 100 million values.