Question $1.[$written question$]$

$[20$ marks$]$

In this question, we use the insertion algorithm for AVL tree.

Insert the following sequence of keys $($one$-$by$-$one$)$ into an empty AVL tree:

$12,23,34,45,56,67,78,89$

In each insertion operation, you may encounter $0$ rotation, $1$ rotation, or more than $1$

rotations.

Draw the trees as follows:

Draw the tree just before you perform a rotation.

Draw the final tree.