Data Structure

AVL Tree Lab Tutorial: Rotations, Insertion, Deletion & Height Explained with Examples: DS LAB 08

By 7 Mins Read

AVL Tree Lab Tutorial: Rotations, Insertion, Deletion & Height Explained with Examples

Introduction

In data structures, maintaining performance is not just about storing data—it’s about organizing it efficiently. A simple Binary Search Tree (BST) can quickly become unbalanced, leading to slow operations.

This lab focuses on AVL Trees, a self-balancing structure introduced by Georgy Adelson-Velsky and Evgenii Landis, designed to maintain optimal performance automatically.

This guide aligns directly with your lab objectives and outcomes, ensuring both conceptual clarity and hands-on implementation.

Lab Objectives (Mapped to Practice)

By completing this lab, students will be able to:

  • Implement left and right rotations to balance a tree
  • Insert nodes while maintaining AVL properties
  • Delete nodes without breaking balance
  • Analyze how balancing improves efficiency

Activity Outcomes (Concept Coverage)

This lab ensures understanding of:

  • Height of the tree
  • Rotate Left (RR Fix)
  • Rotate Right (LL Fix)
  • Insertion in AVL Tree
  • Deletion in AVL Tree

Understanding the Core Concepts

1. Height of the Tree

Height plays a central role in AVL trees. It determines whether a node is balanced or not.

Definition:

Height of a node = longest path from that node to a leaf

Balance Factor:

BF=Height(Left)−Height(Right)

Valid Range: -1, 0, +1

If BF goes beyond this range, rotation is required

Real-Time Insight

Imagine a university database system storing student records.

  • If the tree becomes skewed → searching a record becomes slow
  • AVL ensures the tree remains balanced → fast retrieval every time

 

For details on AVL Balancing technique, visit the link below:

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

 

Real-World Scenario: Task Scheduling System

Consider a system where tasks are inserted continuously:

  • High-priority tasks must be accessed quickly
  • AVL ensures no long chains form
  • Performance remains stable

2. Insertion in AVL Tree

Insertion follows BST rules but adds balancing logic.

Steps:

  1. Insert node like BST
  2. Update height
  3. Calculate balance factor
  4. Apply rotation if needed

Real-World Scenario: Task Scheduling System

Consider a system where tasks are inserted continuously:

  • High-priority tasks must be accessed quickly
  • AVL ensures no long chains form
  • Performance remains stable

3. Deletion in AVL Tree

Deletion is more complex because it may disturb balance at multiple levels.

Steps:

  1. Delete node (BST logic)
  2. Update height
  3. Check balance factor
  4. Apply required rotation

Example Scenario

Delete a node from a balanced AVL tree:

  • Tree becomes right-heavy
  • Apply RR rotation
  • Restore balance

Real-World Scenario: File Management System

When files are removed:

  • Tree structure changes
  • AVL ensures directory indexing remains efficient

Why This Lab Matters

This lab builds strong foundations for:

  • Advanced data structures
  • Algorithm optimization
  • Real-world system design

AVL trees are widely used where frequent search operations are required.

Activity 1:

Node creation

// Node structure
struct Node
{
int data;
   Node* left;
   Node* right;
   int height;
};


// Create new node
Node* createNode(int value)
{
    Node* newNode = new Node();
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->height = 1;
    return newNode;
}

Activity 2:

Height calculation

// Function to get height
int getHeight(Node* root)
{
    if(root == NULL)
        return 0;
    return root->height;
}

// Function to return maximum
int maxHeight(int lh, int rh)
{
    if(lh > rh)
        return lh;
    return rh;
}


// Get balance factor
int getBalance(Node* root)
{
    if(root == NULL)
        return 0;
    return getHeight(root->left) - getHeight(root->right);
}

Activity 3:

Left Rotation

// Left Rotation
Node* rotateLeft(Node* x)
{
    Node* y = x->right;
    Node* T2 = y->left;

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

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

    return y;
}

Activity 4:

Right Rotation

// Right Rotation
Node* rotateRight(Node* y)
{
    Node* x = y->left;
    Node* T2 = x->right;

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

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

    return x;
}

Activity 5:

Insert in AVL Tree

// Insert node in AVL Tree
Node* insert(Node* root, int value)
{
    // Normal BST insertion
    if(root == NULL)
        return createNode(value);

    if(value < root->data)
        root->left = insert(root->left, value);
    else if(value > root->data)
        root->right = insert(root->right, value);
    else
        return root;

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

    // Check balance
    int balance = getBalance(root);

    // Left Left Case
    if(balance > 1 && value < root->left->data)
        return rotateRight(root);

    // Right Right Case
    if(balance < -1 && value > root->right->data)
        return rotateLeft(root);

    // Left Right Case
    if(balance > 1 && value > root->left->data)
    {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }

    // Right Left Case
    if(balance < -1 && value < root->right->data)
    {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    return root;
}

Activity 6:

Inorder Traversal

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

Main Method:

// Main function
int main()
{
    Node* root = NULL;

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    cout << "Inorder Traversal of AVL Tree: ";
    inorder(root);

    return 0;
}

Complete Code:

#include <iostream>
using namespace std;

// Node structure
struct Node
{
   int data;
   Node* left;
   Node* right;
   int height;
};

// Function to get height
int getHeight(Node* root)
{
    if(root == NULL)
        return 0;
    return root->height;
}

// Function to return maximum
int maxHeight(int lh, int rh)
{
    if(lh > rh)
        return lh;
    return rh;
}

// Create new node
Node* createNode(int value)
{
    Node* newNode = new Node();
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->height = 1;
    return newNode;
}

// Get balance factor
int getBalance(Node* root)
{
    if(root == NULL)
        return 0;
    return getHeight(root->left) - getHeight(root->right);
}

// Right Rotation
Node* rotateRight(Node* y)
{
    Node* x = y->left;
    Node* T2 = x->right;

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

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

    return x;
}

// Left Rotation
Node* rotateLeft(Node* x)
{
    Node* y = x->right;
    Node* T2 = y->left;

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

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

    return y;
}

// Insert node in AVL Tree
Node* insert(Node* root, int value)
{
    // Normal BST insertion
    if(root == NULL)
        return createNode(value);

    if(value < root->data)
        root->left = insert(root->left, value);
    else if(value > root->data)
        root->right = insert(root->right, value);
    else
        return root;

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

    // Check balance
    int balance = getBalance(root);

    // Left Left Case
    if(balance > 1 && value < root->left->data)
        return rotateRight(root);

    // Right Right Case
    if(balance < -1 && value > root->right->data)
        return rotateLeft(root);

    // Left Right Case
    if(balance > 1 && value > root->left->data)
    {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }

    // Right Left Case
    if(balance < -1 && value < root->right->data)
    {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    return root;
}

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

// Main function
int main()
{
    Node* root = NULL;

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    cout << "Inorder Traversal of AVL Tree: ";
    inorder(root);

    return 0;
}

Graded Lab Tasks

Lab Task 1:

Complete all types of rotations applied in AVL Tree.

Lab Task 2

Apply level order traversal of AVL Tree.

 

Conclusion

This AVL tree lab bridges theory and practical implementation. By working through rotations, insertion, and deletion, students gain hands-on experience in maintaining balanced trees—an essential concept in computer science.

Mastering AVL trees equips you with the ability to design efficient systems that perform consistently, even with large datasets.

 

Lesson 21: Heap Data Structure Explained with Max Heap, Min Heap, Insertion, Deletion & Priority Queue

Author

Related Posts

Write A Comment