5.4.6 Example

We're done with writing the code. Now, for clarification, let's run through an example designed to need lots of rebalancing along the way. Suppose that, starting with an empty AVL tree, we insert 6, 5, and 4, in that order. The first two insertions do not require rebalancing. After inserting 4, rebalancing is needed because the balance factor of node 6 would otherwise become -2, an invalid value. This is case 1, so we perform a right rotation on 6. So far, the AVL tree has evolved this way:

If we now insert 1, then 3, a double rotation (case 2.1) becomes necessary, in which we rotate left at 1, then rotate right at 4:

Inserting a final item, 2, requires a right rotation (case 1) on 5: