Start with an empty AVL tree and insert the items
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
in that order, into the tree.
For each insertion show the following information.
Suppose that T is the current tree and x is the new item being inserted.
- Show the new tree, let us call this T', obtained by inserting x.
Show the balances of all the nodes and indicate if T' is an AVL tree
or not.
- If T' is not an AVL tree, specify how to fix it.
The choices are (i) single left rotation, (ii) single right rotation, (iii) a double rotation in which
we first perform a left rotation and then a right rotation, and (iv) a double rotation in which
we first perform a right rotation followed by a left rotation.
- If T' is not an AVL tree, turn it into an AVL tree by performing the operation specified
above. Show the tree after the operation has been performed and show the balances of all the nodes
so that it is clear that the resulting tree is an AVL tree.