5.4.6 Example [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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:

[Click here for plain-text rendering]

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:

[Click here for plain-text rendering]

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

[Click here for plain-text rendering]