Can you explain what an AVL tree is and how it works to balance data?

An AVL tree is a self-balancing binary search tree where, for each node, the difference in height between the left and right subtrees does not exceed 1. This ensures logarithmic time complexity for search, insert, and delete operations.

How it works:

• Inserting or deleting a node may disrupt the tree's balance.
• After such operations, the balance factor (the difference in heights of subtrees) is calculated for each node.
• If the balance factor goes outside the range [-1, 1], special rotations (left, right, double) are performed to restore balance.

This guarantees that the tree remains balanced, which is important for efficient data search and update.

Example: if after inserting a node, the left subtree becomes 2 levels higher than the right, a right rotation is performed to restore balance.