Extra 5% OFF Use Code: OL05
Free Shipping over ₹999

AVL Trees

by Mohd Azka
in Data Structure and Algorithm(DSA)
March 25, 2024

AVL Trees

AVL trees are a type of self-balancing binary search tree named after their inventors, Adelson-Velsky and Landis. They were the first such data structure to be invented and maintain balance during insertions and deletions.

Properties of AVL Trees:

  1. Balanced Height: An AVL tree is balanced if the heights of the left and right subtrees of every node differ by at most 1.
  2. Binary Search Tree Property: In addition to being balanced, an AVL tree must also maintain the binary search tree property, where the left subtree of a node contains only nodes with values less than the node’s value, and the right subtree contains only nodes with values greater than the node’s value.

Balancing Operations:

To maintain the balance property, AVL trees perform rotations when necessary during insertions and deletions. There are four types of rotations:

  1. Left Rotation: Rebalances the tree by rotating nodes to the left.
  2. Right Rotation: Rebalances the tree by rotating nodes to the right.
  3. Left-Right Rotation: A combination of left and right rotations.
  4. Right-Left Rotation: A combination of right and left rotations.

These rotations ensure that the AVL tree remains balanced after insertions and deletions.

AVL Insert Node Implementation

#include <stdio.h>
#include <stdlib.h>

// Define a structure for a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    int height; // Height of the node
};

// Function to get the height of a node
int height(struct TreeNode* node) {
    if (node == NULL)
        return 0;
    return node->height;
}

// Function to get the maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->height = 1; // New node is initially added at leaf
    return newNode;
}

// Function to right rotate subtree rooted with y
struct TreeNode* rightRotate(struct TreeNode* y) {
    struct TreeNode* x = y->left;
    struct TreeNode* T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

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

    // Return new root
    return x;
}

// Function to left rotate subtree rooted with x
struct TreeNode* leftRotate(struct TreeNode* x) {
    struct TreeNode* y = x->right;
    struct TreeNode* T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

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

    // Return new root
    return y;
}

// Get the balance factor of a node
int getBalance(struct TreeNode* node) {
    if (node == NULL)
        return 0;
    return height(node->left) - height(node->right);
}

// Function to insert a node into the AVL tree
struct TreeNode* insert(struct TreeNode* node, int data) {
    // Perform normal BST insertion
    if (node == NULL)
        return (createNode(data));

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // Equal keys not allowed in BST
        return node;

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

    // Get the balance factor to check if this node became unbalanced
    int balance = getBalance(node);

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

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

    // Left Right Case
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

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

    return node;
}

// Function to print the inorder traversal of the AVL tree
void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

// Main function
int main() {
    struct TreeNode* 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);

    printf("Inorder traversal of the AVL tree: ");
    inOrderTraversal(root);
    printf("\n");

    return 0;
}

Output:

Inorder traversal of the AVL tree: 10 20 30 35 40 50

Code Explanation

1. Define the TreeNode Structure

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    int height; // Height of the node
};

A TreeNode structure is defined with four members:

  • data: Stores the integer value of the node.
  • left: A pointer to the left child node.
  • right: A pointer to the right child node.
  • height: The height of the node.

3. Function: height

int height(struct TreeNode* node) {
    if (node == NULL)
        return 0;
    return node->height;
}
  • Purpose: Returns the height of a node.
  • Parameters:
    • node: A pointer to the node.
  • Returns:
    • The height of the node. If the node is NULL, returns 0.

4. Function: max

int max(int a, int b) {
    return (a > b) ? a : b;
}
  • Purpose: Returns the maximum of two integers.
  • Parameters:
    • a, b: The two integers to compare.
  • Returns:
    • The larger of the two integers.

5. Function: createNode

struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->height = 1; // New node is initially added at leaf
    return newNode;
}
  • Purpose: Creates a new binary tree node.
  • Parameters:
    • data: The value to be stored in the node.
  • Steps:
    1. Allocate memory for a new node.
    2. Check if memory allocation fails. If it does, print an error message and exit.
    3. Assign data to the data field of the new node.
    4. Set left and right pointers to NULL.
    5. Set the height of the new node to 1.
    6. Return the newly created node.

6. Function: rightRotate

struct TreeNode* rightRotate(struct TreeNode* y) {
    struct TreeNode* x = y->left;
    struct TreeNode* T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    // Return new root
    return x;
}
  • Purpose: Performs a right rotation on the subtree rooted at y.
  • Parameters:
    • y: The root of the subtree to be rotated.
  • Steps:
    1. Store the left child of y as x and the right child of x as T2.
    2. Perform the rotation:
      • Set x->right to y.
      • Set y->left to T2.
    3. Update the heights of y and x.
    4. Return the new root of the subtree (x).

7. Function: leftRotate

struct TreeNode* leftRotate(struct TreeNode* x) {
    struct TreeNode* y = x->right;
    struct TreeNode* T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    // Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
 
    // Return new root
    return y;
}
  • Purpose: Performs a left rotation on the subtree rooted at x.
  • Parameters:
    • x: The root of the subtree to be rotated.
  • Steps:
    1. Store the right child of x as y and the left child of y as T2.
    2. Perform the rotation:
      • Set y->left to x.
      • Set x->right to T2.
    3. Update the heights of x and y.
    4. Return the new root of the subtree (y).

8. Function: getBalance

int getBalance(struct TreeNode* node) {
    if (node == NULL)
        return 0;
    return height(node->left) - height(node->right);
}
  • Purpose: Returns the balance factor of a node.
  • Parameters:
    • node: A pointer to the node.
  • Returns:
    • The balance factor (height of left subtree – height of right subtree).

9. Function: insert

struct TreeNode* insert(struct TreeNode* node, int data) {
    // Perform normal BST insertion
    if (node == NULL)
        return (createNode(data));
 
    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // Equal keys not allowed in BST
        return node;
 
    // Update height of this ancestor node
    node->height = 1 + max(height(node->left), height(node->right));
 
    // Get the balance factor to check if this node became unbalanced
    int balance = getBalance(node);
 
    // Left Left Case
    if (balance > 1 && data < node->left->data)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && data > node->right->data)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    return node;
}
  • Purpose: Inserts a new node into the AVL tree and balances it if necessary.
  • Parameters:
    • node: The root of the AVL tree.
    • data: The value to be inserted.
  • Steps:
    1. Perform normal BST insertion.
    2. Update the height of the current node.
    3. Get the balance factor of the node.
    4. Perform rotations if the node becomes unbalanced:
      • Left Left Case: Right rotation.
      • Right Right Case: Left rotation.
      • Left Right Case: Left rotation on left child, then right rotation.
      • Right Left Case: Right rotation on right child, then left rotation.
    5. Return the root of the balanced subtree.

10. Function: inOrderTraversal

void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}
  • Purpose: Performs an in-order traversal of the AVL tree (left, root, right).
  • Parameters:
    • root: The root of the AVL tree.
  • Steps:
    1. Recursively traverse the left subtree.
    2. Print the data of the current node.
    3. Recursively traverse the right subtree.

11. Main Function

int main() {
    struct TreeNode* 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);
 
    printf("Inorder traversal of the AVL tree: ");
    inOrderTraversal(root);
    printf("\n");
 
    return 0;
}
  • Steps:
    1. Initialize the AVL tree with root set to NULL.
    2. Insert elements 10, 20, 30, 40, 50, and 25 into the AVL tree.
    3. Perform an in-order traversal of the AVL tree and print the elements.

AVL Delete Node Implementation

Below is an implementation of the AVL tree deletion operation in C. Deletion in AVL trees involves standard binary search tree deletion followed by AVL tree balancing to maintain the AVL property.

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
    int height;
} TreeNode;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int getHeight(TreeNode *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

TreeNode* newNode(int data) {
    TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}

TreeNode *rightRotate(TreeNode *y) {
    TreeNode *x = y->left;
    TreeNode *T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    return x;
}

TreeNode *leftRotate(TreeNode *x) {
    TreeNode *y = x->right;
    TreeNode *T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    return y;
}

int getBalance(TreeNode *N) {
    if (N == NULL)
        return 0;
    return getHeight(N->left) - getHeight(N->right);
}

TreeNode* insert(TreeNode* node, int data) {
    if (node == NULL)
        return(newNode(data));

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // Equal data not allowed in BST
        return node;

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

    int balance = getBalance(node);

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

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

    // Left Right Case
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

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

    return node;
}

TreeNode * minValueNode(TreeNode* node) {
    TreeNode* current = node;
    while (current->left != NULL)
        current = current->left;
    return current;
}

void inOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%c ", root->data);
        inOrderTraversal(root->right);
    }
}

TreeNode* deleteNode(TreeNode* root, int data) {
    if (root == NULL)
        return root;

    // Standard BST delete
    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        if ((root->left == NULL) || (root->right == NULL)) {
            TreeNode *temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else
                *root = *temp;
            free(temp);
        } else {
            TreeNode* temp = minValueNode(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }

    if (root == NULL)
        return root;

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

    int balance = getBalance(root);

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

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

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

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

    return root;
}


int main() {
    TreeNode *root = NULL;
    char letters[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};
    int n = sizeof(letters) / sizeof(letters[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, letters[i]);
    }

    inOrderTraversal(root);

    printf("\nDeleting 'C'\n");
    root = deleteNode(root, 'C');

    inOrderTraversal(root);
    return 0;
}

Output:

A B C D E F G H 
Deleting 'C'
A B D E F G H

Time Complexity:

In AVL trees, search, insertion, and deletion operations have a time complexity of O(log n), where n is the number of nodes in the tree. This is because AVL trees maintain balance, ensuring that the height of the tree remains logarithmic with respect to the number of nodes.

Advantages of AVL Trees:

  1. Guaranteed Balanced Structure: AVL trees guarantee a balanced structure, leading to predictable and efficient search, insertion, and deletion operations.
  2. Optimal Time Complexity: With logarithmic time complexity for basic operations, AVL trees are suitable for applications where performance is critical.

Disadvantages of AVL Trees:

  1. More Overhead: Maintaining balance in AVL trees requires additional bookkeeping compared to regular binary search trees. This overhead can result in slightly slower insertion and deletion operations.
  2. Complex Implementation: Implementing AVL trees can be more complex compared to simpler binary search trees due to the need for balancing operations.

Despite these drawbacks, AVL trees are widely used in practice and serve as a foundational data structure in various applications where efficient search, insertion, and deletion operations are required.

    Leave a Reply

    Your email address will not be published.

    Need Help?
    OceanLabz © 2025 All rights reserved.
    Successfully added to your cart.