Data Structure

Lesson 16: Tree Balancing Technique (AVL Tree) – Complete Guide with Rotations & Code

By 9 Mins Read

Tree Balancing Technique (AVL Tree) – Complete Guide with Examples

  • Introduction to AVL Tree
  • What is Tree Balancing?
  • AVL Tree Structure
  • Balance Factor Concept
  • AVL Rotations (LL, RR, LR, RL)
  • AVL Tree Operations
    • Insertion
    • Searching
    • Deletion
  • Time Complexity
  • Advantages & Disadvantages
  • AVL vs Other Trees
  • Real-World Applications
  • Conclusion

Introduction to AVL Tree

In the domain of Data Structures and Algorithms, maintaining efficiency is critical. A standard Binary Search Tree (BST) can degrade into a linear structure (like a linked list), resulting in poor performance O(n).

To address this issue, the AVL Tree was introduced as a self-balancing Binary Search Tree.

👉 It ensures that the height difference between left and right subtrees remains controlled, guaranteeing O(log n) time complexity for operations.

What is Tree Balancing?

Tree balancing ensures that the tree height remains minimal after every insertion or deletion.

Balance Factor Formula:

Balance Factor Formula:

Balance Factor = Height(Left Subtree) − Height(Right Subtree)

Conditions:

  • -1, 0, +1 → Balanced
  • Less than -1 or greater than +1 → Unbalanced

AVL Tree Structure

AVL Tree Insertion | Insertion in AVL Tree | Gate Vidyalay

Data Structures Tutorials - AVL Tree | Examples | Balance Factor

 

Each node in an AVL tree stores:

  • Data (value)
  • Height
  • Left child
  • Right child

AVL Tree Rotations

Rotations are the most important part of the working of the AVL tree. They are responsible for maintaining the balance in the AVL tree. There are 4 types of rotations based on the 4 possible cases:

  1. LL Case (Left-Left) → Right Rotation
  2. RR Case (Right-Right) → Left Rotation
  3. Left-Right Rotation (LR)
  4. Right-Left Rotation (RL)

Why Rotations Are Needed

When inserting into a BST, the tree may become skewed:

  • Left-heavy → imbalance
  • Right-heavy → imbalance

👉 AVL trees fix this using rotations to maintain:

  • −1≤Balance Factor≤1

1. LL Case (Left-Left) → Right Rotation

The RR rotation is applied when a node becomes unbalanced due to an insertion into the left subtree of its left child. This type of imbalance is called Right Imbalance. The solution to it is to take the unbalanced node, and rotate the top edge (that is connected with parent) 90° to the right (clockwise).

Condition

  • Insertion occurs in left subtree of left child

Example

Insert: 30 → 20 → 10

Key Insight

  • Middle node becomes root
  • Left child remains left
  • Root shifts right

2. RR Case (Right-Right) → Left Rotation

The LL rotation is used in an AVL tree to balance a node that becomes unbalanced due to an insertion into the right subtree of its right child.  It is called Left Imbalance. The solution to it is to take the unbalanced node, and rotate the top edge (that is connected with parent) 90° to the left(anti-clockwise).

Condition

  • Insertion occurs in right subtree of right child

Example

Insert: 10 → 20 → 30

left-rotation-ll-of-avl-tree

Key Insight

  • Middle node becomes root
  • Right child remains right
  • Root shifts left

3. LR Case (Left-Right) → Double Rotation

A left-right rotation is used when a left child of a node is right-heavy. It helps in balancing the tree after a double imbalance, which is another specific insertion case. We first perform a left rotation on the left child and follow it up with a right rotation on the original node.

 

Condition

  • Insertion occurs in right subtree of left child

🧠 Example

Insert: 30 → 10 → 20

left-right-rotation-in-avl-tree

Key Insight

  • First fix child imbalance
  • Then fix root imbalance

4. RL Case (Right-Left) → Double Rotation

The right left rotation is performed when a right child of a node is left-heavy. We perform a right rotation on the right child and follow it up with a left rotation on the original node.

Condition

  • Insertion occurs in left subtree of right child

🧠 Example

Insert: 10 → 30 → 20

right-left-rotation-in-avl-tree

Key Insight

  • Fix child first
  • Then rotate root

Summary Table

Case Condition Rotation
LL Left of Left Right Rotation
RR Right of Right Left Rotation
LR Right of Left Left + Right
RL Left of Right Right + Left

VL Tree Operations

1. Insertion in AVL Tree

Steps:

  1. Insert like BST
  2. Update height
  3. Calculate balance factor
  4. Apply rotation if needed
AVL Tree Insertion Code
#include <iostream>
using namespace std;

class AVL {
    private:
    struct Node {
        int key;
        Node* left;
        Node* right;
        int height;

        Node(int k) {
            key = k;
            left = right = NULL;
            height = 1;
        }
    };

    Node* root;

    // 🔹 Get Height
    int height(Node* n) {
        return (n == NULL) ? 0 : n->height;
    }

    // 🔹 Get Balance Factor
    int getBalance(Node* n) {
        return (n == NULL) ? 0 : height(n->left) - height(n->right);
    }

    // 🔁 Right Rotation (LL Case)
    Node* rightRotate(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;

        x->right = y;
        y->left = T2;

        y->height = max(height(y->left), height(y->right)) + 1;
        x->height = max(height(x->left), height(x->right)) + 1;

        return x;
    }

    // 🔁 Left Rotation (RR Case)
    Node* leftRotate(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;

        y->left = x;
        x->right = T2;

        x->height = max(height(x->left), height(x->right)) + 1;
        y->height = max(height(y->left), height(y->right)) + 1;

        return y;
    }

    // 🌱 INSERT
    Node* insert(Node* node, int key) {

        // BST insertion
        if (node == NULL)
            return new Node(key);

        if (key < node->key)
            node->left = insert(node->left, key);
        else if (key > node->key)
            node->right = insert(node->right, key);
        else
            return node; // No duplicates

        // Update height
        node->height = 1 + max(height(node->left), height(node->right));

        // Balance factor
        int balance = getBalance(node);

        // 🔄 Rotations

        // LL Case
        if (balance > 1 && key < node->left->key)
            return rightRotate(node);

        // RR Case
        if (balance < -1 && key > node->right->key)
            return leftRotate(node);

        // LR Case
        if (balance > 1 && key > node->left->key) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // RL Case
        if (balance < -1 && key < node->right->key) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    // 🔍 SEARCH
    Node* search(Node* node, int key) {
        if (node == NULL || node->key == key)
            return node;

        if (key < node->key)
            return search(node->left, key);

        return search(node->right, key);
    }

    // 🔹 Find Minimum (used in deletion)
    Node* minValueNode(Node* node) {
        Node* current = node;
        while (current->left != NULL)
            current = current->left;
        return current;
    }

    // ❌ DELETE
    Node* deleteNode(Node* root, int key) {

        // BST delete
        if (root == NULL)
            return root;

        if (key < root->key)
            root->left = deleteNode(root->left, key);

        else if (key > root->key)
            root->right = deleteNode(root->right, key);

        else {
            // One or zero child
            if ((root->left == NULL) || (root->right == NULL)) {
                Node* temp = root->left ? root->left : root->right;

                if (temp == NULL) {
                    temp = root;
                    root = NULL;
                } else {
                    *root = *temp;
                }
                delete temp;
            }
            else {
                // Two children
                Node* temp = minValueNode(root->right);

                root->key = temp->key;

                root->right = deleteNode(root->right, temp->key);
            }
        }

        if (root == NULL)
            return root;

        // Update height
        root->height = 1 + max(height(root->left), height(root->right));

        // Balance
        int balance = getBalance(root);

        // 🔄 Rotations after deletion

        // LL
        if (balance > 1 && getBalance(root->left) >= 0)
            return rightRotate(root);

        // LR
        if (balance > 1 && getBalance(root->left) < 0) {
            root->left = leftRotate(root->left);
            return rightRotate(root);
        }

        // RR
        if (balance < -1 && getBalance(root->right) <= 0)
            return leftRotate(root);

        // RL
        if (balance < -1 && getBalance(root->right) > 0) {
            root->right = rightRotate(root->right);
            return leftRotate(root);
        }

        return root;
    }

    // 🌿 Inorder Traversal
    void inorder(Node* root) {
        if (root != NULL) {
            inorder(root->left);
            cout << root->key << " ";
            inorder(root->right);
        }
    }

    public:
    AVL() {
        root = NULL;
    }

    // Public wrappers
    void insert(int key) {
        root = insert(root, key);
    }

    void remove(int key) {
        root = deleteNode(root, key);
    }

    void searchKey(int key) {
        Node* result = search(root, key);
        if (result != NULL)
            cout << "Key found: " << result->key << endl;
        else
            cout << "Key not found\n";
    }

    void display() {
        inorder(root);
        cout << endl;
    }
};

int main() {
    AVL tree;

    // Insert
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(25);
    tree.insert(5);

    cout << "Inorder Traversal: ";
    tree.display();

    // Search
    tree.searchKey(25);

    // Delete
    tree.remove(20);

    cout << "After Deletion: ";
    tree.display();

    return 0;
}

2. Deletion in AVL Tree

Deletion follows:

  1. Perform BST deletion
  2. Update height
  3. Check balance
  4. Apply appropriate rotation
// ❌ DELETE
Node* deleteNode(Node* root, int key) {

    // BST delete
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);

    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    else {
        // One or zero child
        if ((root->left == NULL) || (root->right == NULL)) {
            Node* temp = root->left ? root->left : root->right;

            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else {
                *root = *temp;
            }
            delete temp;
        }
        else {
            // Two children
            Node* temp = minValueNode(root->right);

            root->key = temp->key;

            root->right = deleteNode(root->right, temp->key);
        }
    }

    if (root == NULL)
        return root;

    // Update height
    root->height = 1 + max(height(root->left), height(root->right));

    // Balance
    int balance = getBalance(root);

    // 🔄 Rotations after deletion

    // LL
    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    // LR
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // RR
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    // RL
    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

Searching Code:

// 🔍 SEARCH
Node* search(Node* node, int key) {
    if (node == NULL || node->key == key)
        return node;

    if (key < node->key)
        return search(node->left, key);

    return search(node->right, key);
}

Time Complexity

Operation Time Complexity
Insertion O(log n)
Deletion O(log n)
Search O(log n)

 

👉 Guaranteed due to strict balancing rules.

 

Advantages of AVL Tree

  • Always balanced (strictly)
  • Faster search compared to BST
  • Predictable performance
  • Ideal for lookup-heavy applications

Disadvantages of AVL Tree

  • More rotations (overhead)
  • Complex implementation
  • Slightly slower insertion/deletion than Red-Black Trees

AVL Tree vs Other Trees

Feature AVL Tree  BST Red-Black Tree
Balance Strict No Moderate
Search Speed Fast Slow (worst case) Fast
Rotations More None Fewer

 

Real-World Applications

  • Database indexing
  • Memory management systems
  • File systems
  • Searching algorithms

Conclusion

The AVL Tree is a fundamental technique in maintaining efficient data structures. By enforcing strict height balance using rotations, AVL trees ensure optimal performance for dynamic datasets.

If your application demands fast lookup and guaranteed performance, AVL trees are a highly effective choice.

 

 

 

Author

Related Posts

Write A Comment