AVL Tree Implementation in C

An AVL tree is a self-balancing binary search tree where the difference between the heights of the left and right subtrees cannot be more than one for all nodes. It is named after its inventors Adelson-Velsky and Landis. This balancing is achieved through rotations during insertions and deletions, ensuring that the tree remains balanced and operations like search, insert, and delete are efficient.

Program Structure

This implementation of an AVL tree in C will include the following components:

1. Struct definitions for the AVL tree node.
2. Functions to create a new node and determine the height and balance factor of nodes.
3. Functions to perform rotations (left, right, left-right, and right-left).
4. Functions for inserting a new node, including rebalancing the tree.
5. A main function to demonstrate the usage of the AVL tree with insertion operations.

Code Implementation

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

// AVL tree node structure
typedef struct AVLTreeNode {
    int data;
    struct AVLTreeNode *left;
    struct AVLTreeNode *right;
    int height;
} AVLTreeNode;

// Function prototypes
AVLTreeNode* createNode(int data);
int height(AVLTreeNode *node);
int getBalance(AVLTreeNode *node);
AVLTreeNode* rightRotate(AVLTreeNode *y);
AVLTreeNode* leftRotate(AVLTreeNode *x);
AVLTreeNode* insert(AVLTreeNode* node, int data);
void inorderTraversal(AVLTreeNode *root);

// Function to create a new AVL tree node
AVLTreeNode* createNode(int data) {
    AVLTreeNode *node = (AVLTreeNode*)malloc(sizeof(AVLTreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;  // New node is initially added at leaf
    return node;
}

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

// Function to calculate the balance factor of a node
int getBalance(AVLTreeNode *node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

// Right rotate the subtree rooted with y
AVLTreeNode* rightRotate(AVLTreeNode *y) {
    AVLTreeNode *x = y->left;
    AVLTreeNode *T2 = x->right;

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

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

    // Return new root
    return x;
}

// Left rotate the subtree rooted with x
AVLTreeNode* leftRotate(AVLTreeNode *x) {
    AVLTreeNode *y = x->right;
    AVLTreeNode *T2 = y->left;

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

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

    // Return new root
    return y;
}

// Function to insert a node into the AVL tree and balance the tree
AVLTreeNode* insert(AVLTreeNode* node, int data) {
    // 1. Perform the 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 {
        // Duplicate keys are not allowed in the AVL tree
        return node;
    }

    // 2. Update the height of the ancestor node
    node->height = 1 + ((height(node->left) > height(node->right)) ? height(node->left) : height(node->right));

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

    // If the node becomes unbalanced, then there are 4 cases

    // 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 the unchanged node pointer
    return node;
}

// Function for in-order traversal of the AVL tree
void inorderTraversal(AVLTreeNode *root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// Main function to demonstrate the usage of the AVL tree
int main() {
    AVLTreeNode *root = NULL;

    // Insert keys into the AVL tree
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    // Print the AVL tree using in-order traversal
    printf("In-order traversal of the AVL tree:\n");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

Explanation

The program implements an AVL tree in C, which is a self-balancing binary search tree. The AVL tree ensures that the difference between the heights of the left and right subtrees of any node is no more than one. This balancing is achieved by performing rotations during insertion operations.

The key components of this implementation are as follows:

The AVLTreeNode struct represents a node in the AVL tree, with fields for storing the node’s data, pointers to its left and right children, and an integer height to maintain the height of the node.

The createNode() function creates a new AVL tree node, initializing it with the provided data, and setting its height to 1 since new nodes are initially added as leaf nodes.

The height() function returns the height of a given node, while the getBalance() function calculates and returns the balance factor of a node, which is the difference between the heights of its left and right subtrees.

The rightRotate() and leftRotate() functions perform right and left rotations, respectively, to rebalance the tree when necessary. These functions update the heights of the involved nodes after the rotation.

The insert() function inserts a new node into the AVL tree. It performs the standard binary search tree (BST) insertion, updates the height of the nodes, and checks for any imbalance. If an imbalance is detected, the function rebalances the tree by performing the appropriate rotation (Left-Left, Right-Right, Left-Right, or Right-Left case).

The inorderTraversal() function performs an in-order traversal of the AVL tree, printing the nodes’ values in sorted order.

In the main() function, we demonstrate the AVL tree’s functionality by inserting several keys and printing the tree using an in-order traversal. The AVL tree automatically balances itself during the insertion operations, ensuring that the tree remains balanced and efficient.