How to Balance a Binary Search Tree (AVL Trees)

An AVL Tree stays balanced by tracking the Balance Factor of every node. The Balance Factor is the height of the left subtree minus the height of the right subtree. If this value goes above positive one or below negative one at any node, the tree must be rebalanced.

The height of a node is the length of the longest path from that node down to a leaf. A NULL node has a height of negative one and a leaf node has a height of zero. Update the height of a node every time its children change.

There are four cases. Left Left means the imbalance is in the left subtree of the left child. Right Right means the imbalance is in the right subtree of the right child. Left Right means the imbalance is in the right subtree of the left child. Right Left means the imbalance is in the left subtree of the right child.

For the Left Left case, perform a single Right Rotation on the unbalanced node. The left child takes the place of the unbalanced node and the unbalanced node becomes the right child of the new root. The Binary Search Tree property is preserved throughout.

For the Right Right case, perform a single Left Rotation. The right child takes the place of the unbalanced node and the unbalanced node becomes the left child of the new root.

For the Left Right case, first perform a Left Rotation on the left child, then a Right Rotation on the unbalanced node. For the Right Left case, first perform a Right Rotation on the right child, then a Left Rotation on the unbalanced node.

After every insertion or deletion, walk back up from the affected node to the root. At each node, recalculate the height and balance factor. If any node is unbalanced, apply the correct rotation. This guarantees the tree always stays balanced and all operations remain logarithmic.