DS Menu

AVL Tree



AVL trees, named after their inventors Adelson-Velsky and Landis in the year 1962, are self-balancing binary search trees. In AVL trees, the balance factor and rotations are crucial for maintaining the tree's balanced structure, which ensures efficient operations.

In an AVL tree, the heights of the two child subtrees of any node differ by no more than one. If at any time they differ by more than one, rebalancing is done to restore this property.

Balance Factor in AVL trees

The balance factor of a node in an AVL tree is defined as the difference in height between its left and right subtrees. Mathematically, it's calculated as:

Balance Factor
Balance Factor = Height of Left Subtree − Height of Right Subtree

For an AVL tree to be balanced, the balance factor of every node must be -1, 0, or 1. Here's what these values signify:

  • 0: The heights of the left and right subtrees are equal. The subtree is perfectly balanced.
  • 1: The left subtree is taller than the right subtree by one level.
  • -1: The right subtree is taller than the left subtree by one level.

If the balance factor of any node falls outside this range (-1, 0, 1), it indicates that the tree is unbalanced at that node, and a rotation (or series of rotations) is required to bring it back into balance.

Rotations in AVL trees

Rotations are operations that restructure the tree in order to restore its balance. There are four types of rotations used in AVL trees:

⇒ Left Rotation (LL - Left Left Case)

⇒ Right Rotation (RR - Right Right Case)

⇒ Left-Right Rotation (LR - Left Right Case)

⇒ Right-Left Rotation (RL - Right Left Case)

Let's go through the basic operations in AVL trees:

1. Insertion operations in AVL tree

Insertion in an AVL tree is similar to insertion in a regular binary search tree (BST), with the additional step of balancing the tree.

Steps for Insertion:

  • Insert Like a BST: Start by inserting the node as you would in a standard BST. This involves traversing the tree from the root, moving left or right depending on the value, and inserting the new node in the correct position.
  • Check for Balance: After insertion, walk back up the tree (towards the root) and check the balance factor of each node (the height difference between its left and right subtree). The balance factor should be -1, 0, or 1.
    • Rotate if Necessary: If a node is found with a balance factor of -2 or 2, perform rotations to balance the tree. There are four possible cases:
    • Left-Left (LL) Rotation: Perform a right rotation.
    • Right-Right (RR) Rotation: Perform a left rotation.
    • Left-Right (LR) Rotation: Perform a left rotation on the left child, then a right rotation.
    • Right-Left (RL) Rotation: Perform a right rotation on the right child, then a left rotation.

Example: Construct an AVL Tree by inserting numbers 1,2,3,4,5,6.

2. Deletion operations in AVL tree

Deletion in an AVL tree is more complex due to the need to maintain the tree's balance.

Steps for Deletion:

  • Delete Like a BST: Remove the node as in a standard BST. There are three cases:
    • Node with No Child: Simply remove the node.
    • Node with One Child: Remove the node and replace it with its child.
    • Node with Two Children: Find the in-order successor (smallest node in the right subtree) or in-order predecessor (largest in the left subtree), copy its value to the node, and delete the successor/predecessor.
  • Check for Balance: After deletion, walk back up the tree checking the balance factor of each node.
  • Rotate if Necessary: If any node is unbalanced (balance factor of -2 or 2), perform rotations as in the insertion case to balance the tree.

3. Searching operations in AVL tree

Searching in an AVL tree is identical to searching in a regular BST, as the AVL tree maintains the BST property.

Steps for Searching:

  • Start at the Root: Begin at the root node.
  • Compare and Traverse:
    • Compare the search value with the current node's value.
    • If it matches, the node is found.
    • If the search value is smaller, move to the left child; if larger, move to the right child.
  • Repeat or End: Continue this process until the item is found or a leaf is reached.

W3Schools.com

C Program to implement AVL Tree

Program
// AVL Tree operations in C

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

// Structure for a node in the AVL tree
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int height; // Height of the node
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation error\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    newNode->height = 1; // Initialize height as 1 for a new node
    return newNode;
}

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

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

// Function to perform right rotation
struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;
    struct Node* T2 = x->right;

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

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

    return x;
}

// Function to perform left rotation
struct Node* leftRotate(struct Node* x) {
    struct Node* y = x->right;
    struct Node* T2 = y->left;

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

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

    return y;
}

// Function to get the balance factor of a node
int getBalanceFactor(struct Node* node) {
    if (node == NULL)
        return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// Function to insert a node into the AVL tree
struct Node* insert(struct Node* root, int data) {
    if (root == NULL)
        return createNode(data);

    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    else
        return root; // Duplicate keys are not allowed

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

    // Get the balance factor to check if rotation is needed
    int balance = getBalanceFactor(root);

    // Left-Left case (LL)
    if (balance > 1 && data < root->left->data)
        return rightRotate(root);

    // Right-Right case (RR)
    if (balance < -1 && data > root->right->data)
        return leftRotate(root);

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

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

    return root;
}

// Function to find the node with the minimum value in the tree
struct Node* findMinValueNode(struct Node* node) {
    struct Node* current = node;
    while (current->left != NULL)
        current = current->left;
    return current;
}

// Function to delete a node from the AVL tree
struct Node* deleteNode(struct Node* root, int data) {
    if (root == NULL)
        return root;

    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        // Node with only one child or no child
        if ((root->left == NULL) || (root->right == NULL)) {
            struct Node* temp = root->left ? root->left : root->right;

            // No child case
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else // One child case
                *root = *temp; // Copy the contents of the non-empty child

            free(temp);
        } else {
            // Node with two children: Get the inorder successor (smallest
            // in the right subtree)
            struct Node* temp = findMinValueNode(root->right);

            // Copy the inorder successor's data to this node
            root->data = temp->data;

            // Delete the inorder successor
            root->right = deleteNode(root->right, temp->data);
        }
    }

    // If the tree had only one node then return
    if (root == NULL)
        return root;

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

    // Get the balance factor to check if rotation is needed
    int balance = getBalanceFactor(root);

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

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

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

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

    return root;
}

// Function for in-order traversal of the AVL tree
void inOrderTraversal(struct Node* root) {
    if (root == NULL)
        return;
    
    struct Node* stack[100]; // Stack to store nodes
    int top = -1; // Stack pointer
    struct Node* current = root;
    
    while (current != NULL || top >= 0) {
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }
        current = stack[top--];
        printf("%d ", current->data);
        current = current->right;
    }
}

// Function to free memory by deallocating nodes
void freeMemory(struct Node* root) {
    if (root == NULL)
        return;
    freeMemory(root->left);
    freeMemory(root->right);
    free(root);
}

int main() {
    int choice,value;
    struct Node* root = NULL;
    do
    {
        printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
        printf("\nEnter your choice: ");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1: printf("Enter the value to be insert: ");
                scanf("%d",&value);
                root = insert(root, value);
                break;
        case 2: printf("Enter the value to be deleted: ");
                scanf("%d",&value);
                root = deleteNode(root, value);
                break;
        case 3: inOrderTraversal(root);
                break;
        case 4: freeMemory(root);
                break;
        default: printf("\nWrong selection!!! Try again!!!");  
        }
    }while(choice!=4);
    return 0;
}
Next Topic :Red Black Tree