AVL Tree Insertion and Rebalancing

1. The Building Blocks: Node and Tree Structure

Before we can rotate anything, we need the basic structure. Our AVL tree will be built upon a Node class and an AVLTree class that orchestrates the operations.

An AVL Node is just like a BST Node, but with one crucial addition: a height attribute. We'll use this to calculate the balance factor and determine when to rebalance.

class Node {
    int key;
    int height; // Height of the node
    Node left;
    Node right;

    Node(int key) {
        this.key = key;
        this.height = 1; // A new node is a leaf, so its height is 1
    }
}

The AVLTree class will contain the root and the methods to manage the tree. We'll need a few helper methods to start:

• height(Node n): A safe way to get the height of a node, returning 0 for a null node.
• updateHeight(Node n): Recalculates a node's height based on the heights of its children.
• balanceFactor(Node n): Calculates the balance factor using the height method.

Let's look at a concise video that explains this setup and the overall implementation strategy we'll be following.

2. Implementing the Core Mechanics: Rotations

As we saw, rotations are the fundamental operations for rebalancing. We need to implement two primary methods: rightRotate and leftRotate. These methods will rearrange the nodes and, critically, update their heights.

Let's look at a right rotation on a node y. Its left child is x.

1. The new root of the subtree will be x.
2. y becomes the right child of x.
3. The original right child of x (let's call it T2) becomes the new left child of y.
4. The heights of y and x must be updated (in that order, since y is now a child of x).
5. The new root, x, is returned.

This diagram illustrates the pointer changes for a single right rotation (top) and a single left rotation (bottom). Notice how the BST property (T1 < x < T2 < y < T3) is preserved in both operations.

Now, let's watch a detailed walkthrough of implementing the rotation and insertion logic in Java.

3. The insert Method with Rebalancing

Here is the complete algorithm for a recursive AVL insertion:

1. Base Case (BST Insert): If the current node is null, we've found the insertion spot. Create a new Node with the given key and return it.
2. Recursive Step (BST Insert): If the key is less than the current node's key, recursively call insert on the left child. Otherwise, call it on the right child. Assign the result of the recursive call back to node.left or node.right. This is crucial for reconnecting the tree after rotations.

   // e.g., for the left side
   node.left = insert(node.left, key); 
   

3. Update Height: After the recursive call returns, update the height of the current node.
4. Get Balance Factor: Calculate the balanceFactor for the current node.
5. Check for Imbalance and Rotate:
   • If balanceFactor > 1 (Left-Heavy):
     • If balanceFactor of node.left is >= 0, it's a Left-Left (LL) case. Perform a single rightRotate(node).
     • If balanceFactor of node.left is < 0, it's a Left-Right (LR) case. Perform node.left = leftRotate(node.left) followed by rightRotate(node).
   • If balanceFactor < -1 (Right-Heavy):
     • If balanceFactor of node.right is <= 0, it's a Right-Right (RR) case. Perform a single leftRotate(node).
     • If balanceFactor of node.right is > 0, it's a Right-Left (RL) case. Perform node.right = rightRotate(node.right) followed by leftRotate(node).
6. Return Node: Return the current node (which might be the new root of the subtree after rotation).

This logic is typically placed within a single recursive insert helper method. For an alternative, clean implementation of this logic, you can refer to this Baeldung article.

4. Testing the Implementation

The most effective way to see if our self-balancing logic works is to try to break it. We can do this by inserting elements in a perfectly sorted order. In a standard BST, this would create a long, skewed chain. In our AVL tree, it should remain short and bushy.

Let's see this in action.

This is a powerful demonstration. A height of 10 for a tree with 1000 nodes is exactly what we expect from a balanced tree, as $2^{10}\approx 1024$. This guarantees the fast performance needed for competitive programming and efficient applications.

Conclusion

Congratulations on completing this implementation! You've translated the abstract theory of AVL rotations into concrete Java code that automatically maintains a balanced binary search tree. This is a significant step in your journey to mastering advanced data structures.

Key Takeaways:

• AVL tree insertion builds on BST insertion. The magic happens after the recursive call returns.
• On the path back up to the root, each node's height is updated, its balance factor is checked, and if necessary, rotations are performed.
• Rotation methods (leftRotate, rightRotate) must not only rearrange pointers but also update the heights of the affected nodes and return the new root of the rotated subtree.
• The recursive insert method must re-assign the return value of its calls (e.g., node.left = insert(...)) to ensure the parent node correctly links to the potentially new child node after a rotation.

Preview of the Next Lesson:
We've spent a lot of time on trees designed for efficient searching (BSTs and AVL trees). Next, we will shift our focus to a different type of tree-based structure: the binary heap. You'll learn how to implement max-heaps and min-heaps using a simple array and see why they are the perfect data structure for building Priority Queues, which are essential for solving a wide range of problems, including finding top-K elements and implementing famous graph algorithms like Dijkstra's.