Welcome to AVL tree construction! An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. We'll insert the sequence 16, 15, 14, 13, 12, 11, 10, 8, 9 and observe how rotations maintain the balance property. Let's start by inserting our first node: 16.
Now let's insert 15. It becomes the left child of 16. Next, we insert 14, which becomes the left child of 15. This creates an imbalance at node 16 with a balance factor of 2. This is a Left-Left case, so we perform a right rotation at node 16. After rotation, 15 becomes the new root with 14 as left child and 16 as right child.
Continuing with our insertions: When we insert 13, it creates an imbalance at node 15. We perform a right rotation making 14 the new root. Next, inserting 12 creates an imbalance at 14, so we rotate right making 13 the new root. Finally, inserting 11 creates another imbalance at 13, requiring another right rotation that makes 12 the new root. Notice how each insertion maintains the AVL property through rotations.
Now we insert 10, which creates an imbalance at node 12. We perform a right rotation making 11 the new root. Next, we insert 8, which creates an imbalance at node 11. Another right rotation makes 10 the new root. The tree now has 8 as the left child of 10, and a chain of nodes 11, 12, 13, 14, 15, 16 extending to the right. The tree remains balanced according to AVL properties.
Finally, we insert 9 as the right child of 8. This creates a Left-Right imbalance at node 10, following the path 10 to 8 to 9. For a Left-Right case, we first perform a left rotation at node 8, then a right rotation at node 10. After these rotations, 9 becomes the new root of our AVL tree. The final tree has 8 as the left child of 9, and 10 as the right child, with the chain continuing through 11, 12, 13, 14, 15, and 16. Our AVL tree construction is now complete and perfectly balanced.