In our previous lesson, we mastered the operations of a Binary Search Tree (BST). We concluded by identifying its critical weakness: in the worst case, a BST can become skewed and degenerate into a structure resembling a linked list, causing operation complexities to degrade from to . Today, we address this problem head-on by studying AVL trees, the first of several self-balancing binary search trees we will encounter.
This lesson is crucial for your GATE preparation, as questions involving the construction and modification of AVL trees are common. Your objective is to understand how AVL trees maintain their balance and to master the mechanical process of applying single and double rotations to restore balance after an insertion or deletion. This skill will ensure you can solve these problems accurately and quickly under exam conditions.
1. The AVL Property: Height Balancing
An AVL tree is, first and foremost, a Binary Search Tree. It adheres to the same ordering principle: left < root < right. What makes it special is an additional constraint on its structure to prevent skewing. This is achieved through the Balance Factor.
The Balance Factor (BF) of a node is defined as the height of its left subtree minus the height of its right subtree:
For the purpose of calculating height, a leaf node has a height of 0, and the height of a non-existent (NULL) child is -1.
An AVL tree requires that the balance factor of every single node must be in the set .
- BF = -1: The right subtree is one level taller than the left (right-heavy).
- BF = 0: The left and right subtrees have the same height.
- BF = 1: The left subtree is one level taller than the right (left-heavy).
If any node has a balance factor of -2 or 2, the tree is considered unbalanced, and a re-balancing operation is required.
To see this in practice, let's watch a foundational explanation.
10.1 AVL Tree - Insertion and Rotations
The legendary instructor Abdul Bari provides one of the clearest introductions to AVL trees. This first segment defines the AVL property and shows how to calculate the balance factor for various tree structures.
Watch from the beginning of his AVL tree explanation at this timestamp. Pay close attention to how he computes the height and balance factor for each node in the example trees.
2. Re-balancing After Insertion: The Four Rotations
When you insert a new node into an AVL tree, you follow the standard BST insertion procedure. After the new leaf node is added, you must trace the path back up to the root, updating the balance factors of all ancestors. The first ancestor whose balance factor becomes -2 or 2 is called the critical node. This is where a rotation is needed.
The type of rotation depends on the path taken from the critical node down to the newly inserted node. This gives us four cases, which are named by the sequence of moves (Left or Right) from the critical node.
- Left-Left (LL) Imbalance: The new node is inserted in the left subtree of the left child of the critical node. This is fixed by a single right rotation.
- Right-Right (RR) Imbalance: The new node is inserted in the right subtree of the right child of the critical node. This is fixed by a single left rotation.
- Left-Right (LR) Imbalance: The new node is inserted in the right subtree of the left child of the critical node. This is a "dogleg" path and is fixed by a double rotation (a left rotation on the child followed by a right rotation on the critical node).
- Right-Left (RL) Imbalance: The new node is inserted in the left subtree of the right child of the critical node. This is also fixed by a double rotation (a right rotation on the child followed by a left rotation on the critical node).
The following video segments from Abdul Bari's lecture demonstrate each of these four rotation types with simple, 3-node examples. Master these fundamental moves.
10.1 AVL Tree - Insertion and Rotations
This part of the video is the core of understanding AVL mechanics. Each segment demonstrates one of the four imbalance cases and its corresponding rotation.
Watch the LL Rotation (single right rotation). Watch the LR Rotation (double rotation). Watch the RR Rotation (single left rotation). Watch the RL Rotation (double rotation).
A key insight is that these rotations are local. They primarily rearrange three nodes (the critical node, its child, and its grandchild on the imbalance path). Even in a large tree, the rotation only affects this small neighborhood. The video explains how the other subtrees are correctly reattached.
10.1 AVL Tree - Insertion and Rotations
Now, let's see how these simple rotations are applied within larger trees that have existing subtrees.
Focus on the explanations from this section. Observe how for an LL rotation, the right subtree of the middle node B gets reattached as the left subtree of node A. Similarly, for an LR rotation, the subtrees of node C are reattached to B and A. Understanding this reattachment is key to performing rotations correctly.
3. Constructing an AVL Tree: A Complete Example
Now, let's put it all together. The most common GATE question format gives you a sequence of keys and asks you to construct the final AVL tree. This requires you to insert each key one by one, check balance factors, and perform rotations as needed.
10.1 AVL Tree - Insertion and Rotations
This extended example from Abdul Bari's video is a perfect simulation of a GATE problem. You will build an AVL tree from scratch by inserting multiple keys.
Follow the entire construction process from this timestamp. I highly recommend pausing the video after each insertion, calculating the balance factors yourself, identifying the rotation needed (if any), performing it on paper, and then resuming the video to check your work. This active practice is the best way to solidify your understanding.
A crucial rule to remember: after an insertion, at most one rotation (either single or double) is sufficient to restore the balance of the entire tree.
4. Re-balancing After Deletion
Deletion in an AVL tree also begins with the standard BST deletion algorithm you learned in the previous lesson. After the node is removed (or replaced by its inorder successor/predecessor), you must trace the path back up to the root, checking and updating balance factors.
The process is:
- Perform the deletion as you would in a BST.
- Starting from the parent of the removed node, traverse up to the root.
- At each node along the path, check its balance factor. If it's -2 or 2, perform the appropriate rotation (LL, RR, LR, or RL).
- Unlike insertion, a single rotation may not be enough. After a rotation, you must continue traversing up the tree, as the height change could have caused an imbalance higher up.
Let's see this in action.
5.15 AVL Tree Deletion in Data structures | with Example | DSA Tutorials
Jenny's Lectures CS IT provides a clear, step-by-step walkthrough of AVL deletion.
First, understand the two main steps: perform BST deletion, then check balance and rotate if necessary. Watch the deletion of a leaf node and a node with one child (Examples 1 & 2). In these specific examples, no rotation is needed, but the balance factor check is still mandatory. Now, watch the critical example starting at this timestamp. Here, deleting a node with two children (by replacing it with its inorder predecessor) causes an imbalance (-2). This triggers an RR imbalance, which is fixed with a single left rotation. This is the core concept you need to master. Finally, watch the deletion of the root node (Example 4) to see another application of the two-child deletion rule, and note the final summary of the process.
Conclusion
Today, you have bridged the gap between the theoretical efficiency of BSTs and their practical pitfalls. By enforcing a strict height balance, AVL trees provide the guarantee that search, insertion, and deletion operations will always perform in time.
Key Takeaways:
- AVL Property: An AVL tree is a BST where the balance factor of every node is restricted to .
- Balance Factor: Calculated as .
- Rotations: The mechanism to restore balance. Imbalances are classified as LL, RR, LR, or RL based on the insertion/deletion path relative to the first unbalanced ancestor.
- Single vs. Double Rotations: LL and RR imbalances are fixed with single rotations. LR and RL imbalances require double rotations.
- Insertion vs. Deletion: An insertion requires at most one rotation to fix the tree. A deletion may require multiple rotations as you travel up the tree to the root.
The price for this guaranteed performance is the overhead of checking balance factors and performing rotations. In our next lesson, we will look at Binary Heaps and Priority Queues. Heaps are another specialized tree-based data structure, but they are optimized for efficiently retrieving the minimum or maximum element, rather than for arbitrary search, and they use a different method to maintain their structure.