AVL Tree

AVL Tree

An AVL tree is a self-balancing Binary Search Tree. After every insertion or deletion, the tree automatically rebalances itself so that the balance factor of every node stays within -1, 0, or 1.

Balance Factor

The balance factor of a node is the height of its left subtree minus the height of its right subtree:

balance(node) = height(left) - height(right)

If balance > 1, the tree is left-heavy. If balance < -1, it is right-heavy. Either case requires a rotation.

Right Rotation (Left-Heavy)

When a node is left-heavy and the left child is left-heavy or balanced, perform a right rotation:

      30               20
     /        →       /  \
    20               10   30
   /
  10

struct Node *right_rotate(struct Node *y) {
    struct Node *x = y->left;
    struct Node *t = x->right;
    x->right = y;
    y->left = t;
    y->height = 1 + max(get_height(y->left), get_height(y->right));
    x->height = 1 + max(get_height(x->left), get_height(x->right));
    return x;
}

Left Rotation (Right-Heavy)

When a node is right-heavy and the right child is right-heavy or balanced, perform a left rotation:

  10                   20
    \        →        /  \
     20             10   30
      \
       30

Left-Right and Right-Left Cases

If the imbalance is a zig-zag (e.g., left child is right-heavy), first rotate the child, then rotate the node. These are the Left-Right and Right-Left double rotation cases.

Insert with Rebalancing

After a standard BST insert, walk back up and fix any imbalanced node:

1. Update the node's height.
2. Compute the balance factor.
3. Apply the appropriate rotation if |balance| > 1.

Your Task

Implement struct Node *avl_insert(struct Node *root, int val) that inserts val into an AVL tree and returns the new root, keeping the tree balanced after every insertion. Helper functions get_height, max, get_balance, right_rotate, and left_rotate are provided in the starter code.