AVL Tree

What Makes AVL Trees Different from Regular BSTs? AVL Trees are just like Binary Search Trees, but they add one rule:

Every node must be balanced

This means the height difference (balance factor) between the left and right subtrees of any node must be at most 1.

• In a regular BST, we don’t care how lopsided the tree becomes

• In an AVL Tree, we fix the tree right after insertion or deletion if the balance is off

If the tree becomes unbalanced after inserting or removing a node, the AVL Tree will automatically perform rotations to restore balance.

So everything is the same as before except for insert and remove, which now include some extra logic to check balance and rotate if needed.

How Rotations Works

Let’s say we insert the following values into an empty AVL Tree:

Insert: 10 → 5 → 2

Here’s what happens in a normal BST:

      10
     /
    5
   /
  2

This is left-heavy, and the balance factor of node 10 is now 2, which breaks the AVL rule.

An AVL Tree will perform a right rotation on the node 10 to balance it. After a right rotation the tree will look like this:

      5
     / \
    2   10

Now the tree is balanced again.

AVL trees may perform four types of rotations:

• Left rotation

• Right rotation

• Left-Right rotation

• Right-Left rotation

We’ll walk through the code to handle all of them next.

Add a Height Field to the Node struct

In a regular BST, each node only stores its value and pointers to left and right. In an AVL Tree, we add an extra height field to each node. This lets us track the height of every subtree.

struct Node {
    T data;
    Node* left;
    Node* right;
    int height; // New!

    Node(T val) : data(val), left(nullptr), right(nullptr), height(0) {}
};