Self-Balancing Trees: AVL Rotations

Hello! Welcome back to our deep dive into tree data structures.

In our last lesson, we confirmed a critical weakness of standard Binary Search Trees (BSTs): if the data is inserted in a sorted or nearly sorted order, the tree becomes skewed and degenerates into a structure resembling a linked list. This pushes the time complexity for search, insertion, and deletion from the ideal $O (lo g N)$ to a worst-case $O (N)$ . For your goals in competitive programming and technical interviews, relying on an algorithm that can unexpectedly perform poorly is a significant risk.

Today, we'll address this problem head-on. This lesson introduces AVL trees, a type of self-balancing binary search tree that guarantees $O (lo g N)$ performance for its core operations. You'll learn why they are necessary and master the fundamental mechanism they use to maintain balance: rotations.

1. The Need for Self-Balancing

The core problem with a standard BST is that it has no rules to enforce a "bushy" shape. The structure is entirely dependent on the order of insertion.

Why AVL Tree? - Comparison with Binary Tree — This image perfectly illustrates the problem. Both trees contain the same elements (1-7). The standard BST on the right, formed by inserting keys in ascending order, is skewed. To insert the key '8', it requires 7 comparisons. The AVL tree on the left is balanced, and inserting '8' takes only 3 comparisons. This demonstrates the efficiency gain from maintaining balance.

To formalize the idea of "balance," we need a precise metric. This is where the balance factor comes in.

2. The AVL Property: Height and Balance Factor

An AVL tree is a BST with one additional constraint:

For every node in the tree, the absolute difference between the height of its left subtree and the height of its right subtree cannot be greater than 1.

This difference is called the balance factor.

Balance Factor (BF) = height(left subtree) - height(right subtree)

Therefore, for any node in an AVL tree, its balance factor must be in the set {-1, 0, 1}.

BF = -1: The node is "right-heavy" (its right subtree is one level taller).
BF = 0: The subtrees are of equal height.
BF = 1: The node is "left-heavy" (its left subtree is one level taller).

If an insertion or deletion causes any node to have a balance factor of -2 or 2, the tree is considered "unbalanced," and a rebalancing operation must be performed.

Let's watch a short video to solidify our understanding of the balance factor.

AVL Tree Explained and Implemented in Java | AVL Trees Rotations | Self-Balancing Trees | Geekific

This video from Geekific clearly defines the height of a node and the balance factor, which is the core property of an AVL tree.

Watch from 01:51 to 03:20. Focus on how the height of a node is calculated and how that is used to determine the balance factor. Notice how a balance factor of 2 indicates an imbalance.

Now that we can detect an imbalance, how do we fix it?

3. Rebalancing Through Rotations

The magic of AVL trees lies in their ability to restructure themselves locally to restore balance. This is done through operations called rotations. A rotation is a simple operation that swaps a parent and child node while carefully rearranging their subtrees to preserve the BST property.

There are four scenarios of imbalance we need to handle, which are corrected by two types of single rotations and two types of double rotations.

Let's watch a concise, animated explanation of all four cases.

AVL Tree Explained and Implemented in Java | AVL Trees Rotations | Self-Balancing Trees | Geekific

The following segment from the Geekific video demonstrates the four rotation cases. Focus on the 'before' and 'after' structure of the tree for each rotation.

Watch from 03:20 to 06:59. The video will walk you through the four main imbalance situations and the rotations used to fix them: Left-Left, Right-Right, Left-Right, and Right-Left.

Great! Let's break down and summarize those four cases. The imbalanced node (where BF is -2 or +2) is z.

AVL Tree Rotations Explained — This diagram is your cheat sheet for AVL rotations. It shows the initial imbalanced state and the final balanced state for all four cases.

Case 1: Left-Left (LL)

Imbalance: Node z has a BF of +2, and its left child y has a BF of +1. The imbalance is caused by an insertion into the left subtree of the left child.
Solution: A single Right Rotation on z.
How it works: y becomes the new root of this subtree. z becomes the right child of y. The original right child of y (T2) becomes the new left child of z. The BST property is maintained.

Case 2: Right-Right (RR)

Imbalance: Node z has a BF of -2, and its right child y has a BF of -1. The imbalance is caused by an insertion into the right subtree of the right child.
Solution: A single Left Rotation on z.
How it works: This is the mirror image of the LL case. y becomes the new root, z becomes its left child, and the original left child of y (T2) becomes the new right child of z.

Case 3: Left-Right (LR)

Imbalance: Node z has a BF of +2, and its left child y has a BF of -1. This "zig-zag" shape is caused by an insertion into the right subtree of the left child.
Solution: A Double Rotation:
1. First, perform a Left Rotation on the child node y. This transforms the subtree into a standard LL case.
2. Then, perform a Right Rotation on the parent node z.
How it works: The first rotation straightens the "zig-zag," and the second rotation balances the straightened line.

Case 4: Right-Left (RL)

Imbalance: Node z has a BF of -2, and its right child y has a BF of +1. This is the other "zig-zag" shape, caused by an insertion into the left subtree of the right child.
Solution: A Double Rotation:
1. First, perform a Right Rotation on the child node y. This transforms the subtree into a standard RR case.
2. Then, perform a Left Rotation on the parent node z.
How it works: This is the mirror image of the LR case.

Test your understanding!

Imagine you insert the number 7 into the following AVL tree.

      10 (BF=+1)
     /
    5  (BF=0)
   / \
  3   8

After inserting 7, the new tree looks like this:

      10 (BF becomes +2, imbalanced!)
     /
    5  (BF becomes -1)
   / \
  3   8
     /
    7

Which of the four imbalance cases (LL, RR, LR, RL) does this represent at node 10, and what rotation(s) are needed to fix it?

Show answer

This is a Left-Right (LR) case.

The imbalanced node is 10 (BF = +2).
Its left child is 5 (BF = -1).
The signs of the balance factors (+2 for the parent, -1 for the child) are opposite, indicating a "zig-zag" or LR/RL case. Since the parent is left-heavy, it's an LR case.

To fix it, you need a double rotation:

Perform a Left Rotation on the child node 5.
Perform a Right Rotation on the parent node 10.

The final balanced tree will have 8 as the root, with 5 as its left child and 10 as its right child. 3 and 7 will be the children of 5.

4. The Insertion and Rebalancing Process

Now that you know how to perform rotations, let's briefly touch on when. The general algorithm for an AVL insertion is:

Insert: Perform a standard BST insertion to add the new node.
Update and Check: Traverse back up the tree from the new node to the root. On this path:
a. Update the height of each node.
b. Calculate the new balance factor.
c. If a node's balance factor is -2 or +2, it's the first unbalanced ancestor. Stop here.
Rotate: Perform the appropriate rotation (LL, RR, LR, or RL) on this unbalanced node to restore the balance of its subtree.

Because you fix the first unbalanced node you find on the path up to the root, the AVL property ensures that the entire tree becomes balanced again after just one set of rotations (either a single or double rotation).

To see this process in action, let's review a resource that walks through several insertion examples.

Data Structures and Algorithms: AVL Trees

The following article from InterviewKickstart provides clear pseudocode for each rotation and outlines the insertion process. The diagrams are also helpful for visualizing the pointer changes.

Skim through the sections from 'What Is AVL Tree Rotation?' to 'Steps to Follow for Insertion'. Focus on the pseudocode for each of the four rotations and the step-by-step logic for insertion. The diagrams for each rotation type are particularly useful.

Conclusion

Excellent work today! You've grasped one of the most fundamental concepts in advanced data structures. Understanding why trees go out of balance and how rotations fix them is a critical skill for building efficient and reliable systems, and it's a topic that frequently appears in technical interviews.

Key Takeaways:

Standard BSTs can become unbalanced, leading to $O (N)$ time complexity.
AVL trees are self-balancing BSTs that maintain a balance factor of {-1, 0, 1} for every node, guaranteeing $O (lo g N)$ performance.
Imbalances are corrected using rotations.
LL and RR cases ("straight line" imbalances) are fixed with a single rotation.
LR and RL cases ("zig-zag" imbalances) are fixed with a double rotation.

Preview of the Next Lesson:
Theory is great, but as a hands-on developer, you know that implementation is where the real learning happens. In the next lesson, we will implement insertion into an AVL tree with automatic rebalancing. You'll write the Java code for the rotation methods we discussed today and integrate them into the insert function to create a fully functional, self-balancing AVL tree.

Recommended resources