C Program to Implement AVL Tree

1. Introduction

AVL tree (named after its inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. The main characteristic of an AVL tree is that the heights of the two child subtrees of any node differ by at most one. This ensures that the AVL tree remains balanced, leading to logarithmic height growth, ensuring operations like insertion, deletion, and lookup run in O(log n) time.

2. Program Overview

Our program will:

1. Define the structure of an AVL tree node.

2. Implement helper functions to get height, balance factor, and perform rotations.

3. Implement functions to insert nodes.

4. Demonstrate insertion in an AVL tree.

3. Code Program

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

// Define the structure for an AVL tree node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int height; // To store the height of the node
} Node;

// Utility function to get the height of the tree
int getHeight(Node* node) {
    if (node == NULL) return 0;
    return node->height;
}

// Utility function to get balance factor
int getBalance(Node* node) {
    if (node == NULL) return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// Utility function to create a new node
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->height = 1; // Newly created node has height 1
    return newNode;
}

// Right rotation to balance the tree
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T3 = x->right;

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

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

    return x;
}

// Left rotation to balance the tree
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

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

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

    return y;
}

// Function to insert a node into AVL tree
Node* insert(Node* root, int value) {
    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; // Duplicates are not allowed

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

    // Get balance factor to decide rotation
    int balance = getBalance(root);

    // If unbalanced, perform rotations
    if (balance > 1) {
        if (value < root->left->data) return rightRotate(root);
        else {
            root->left = leftRotate(root->left);
            return rightRotate(root);
        }
    }
    if (balance < -1) {
        if (value > root->right->data) return leftRotate(root);
        else {
            root->right = rightRotate(root->right);
            return leftRotate(root);
        }
    }

    return root;
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    // In-order traversal can be added to see the balanced tree structure

    return 0;
}

Output:

Since we've only implemented the insertion function and not traversal, the program doesn't produce an output. However, if in-order traversal is performed, the nodes will be printed in ascending order, showcasing the balanced AVL tree.

4. Step By Step Explanation

1. We initiate by defining the Node structure for our AVL tree, where each node will have an extra attribute: height. The height is essential to determine if rotations are needed.

2. The getHeight function retrieves the height of a node, and the getBalance function calculates the balance factor.

3. We've defined two rotation functions: leftRotate and rightRotate to manage the tree's balance.

4. The insert function is designed to handle the insertion of nodes while maintaining the balance of the AVL tree. After every insertion, it checks for balance and performs rotations if necessary.

5. The main function demonstrates inserting various nodes into the AVL tree.

In conclusion, AVL trees are an efficient way to maintain a balanced binary search tree, ensuring that basic operations remain efficient even as more nodes are added or removed.