Balancing an AVL tree involves ensuring that the tree remains a height-balanced binary search tree after every insertion or deletion operation. The balance of an AVL tree is maintained by performing rotations whenever the balance factor of any node becomes less than -1 or greater than 1. Here’s a detailed explanation of how to balance an AVL tree:
Balance Factor
The balance factor of a node in an AVL tree is the difference between the heights of its left and right subtrees. It is calculated as:
$$ \text{Balance Factor} = \text{Height of Left Subtree} - \text{Height of Right Subtree} $$
A node is considered balanced if its balance factor is -1, 0, or +1[1][5].
Types of Rotations
There are four types of rotations used to balance an AVL tree:
Left Rotation (LL Rotation)
Right Rotation (RR Rotation)
Left-Right Rotation (LR Rotation)
Right-Left Rotation (RL Rotation)
1. Left Rotation (LL Rotation)
A left rotation is performed when a node is inserted into the right subtree of the right subtree, causing a right-right imbalance. The steps are:
The right child of the unbalanced node becomes the new root of the subtree.
The original root becomes the left child of the new root.
The left subtree of the new root becomes the right subtree of the original root[1][6][7].
2. Right Rotation (RR Rotation)
A right rotation is performed when a node is inserted into the left subtree of the left subtree, causing a left-left imbalance. The steps are:
The left child of the unbalanced node becomes the new root of the subtree.
The original root becomes the right child of the new root.
The right subtree of the new root becomes the left subtree of the original root[1][6][7].
3. Left-Right Rotation (LR Rotation)
A left-right rotation is performed when a node is inserted into the right subtree of the left subtree, causing a left-right imbalance. The steps are:
Perform a left rotation on the left child of the unbalanced node.
Perform a right rotation on the unbalanced node[1][6][7].
4. Right-Left Rotation (RL Rotation)
A right-left rotation is performed when a node is inserted into the left subtree of the right subtree, causing a right-left imbalance. The steps are:
Perform a right rotation on the right child of the unbalanced node.
Perform a left rotation on the unbalanced node[1][6][7].
Balancing Process
Insertion
Insert the node: Perform a standard binary search tree insertion.
Update heights: Update the height of each node starting from the inserted node up to the root.
Check balance factors: Starting from the inserted node...
