AVL Tree Problem

An AVL tree is a BST where every node has balance factor height(left) - height(right) in {-1, 0, 1}. Insert the key exactly as in a BST, then return through recursion updating each node's height. If a node becomes unbalanced, classify it from the inserted key or child balance: LL needs a right rotation, RR a left rotation, LR a left rotation on the left child then a right rotation, and RL the symmetric pair. A rotation preserves in-order key order while shortening the heavy path; always return the new subtree root so the parent link is repaired. For deletion, the same repair can propagate farther upward, so use child balance factors rather than the deleted key. Discuss duplicate-key policy explicitly. Empty children have height zero (or -1 consistently), and every rotation must recalculate the lower node before the new root. Search, insertion, and deletion are O(log n); each node stores O(1) extra metadata.