AVL Trees

AVL Tree Operations

AVL trees are self-balancing binary search trees where the heights of the two child subtrees of any node differ by at most one. After each insertion or deletion, rotations are performed to maintain this balance property.
Operations Log:

C Implementation:

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

struct Node {
    int value;
    int height;
    struct Node *left;
    struct Node *right;
};

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

// Get maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

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

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

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

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

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

    return x;
}

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

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

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

    return y;
}

// Print the tree in-order
void printInOrder(struct Node* node) {
    if (node != NULL) {
        printInOrder(node->left);
        printf("%d(bf=%d) ", node->value, getBalanceFactor(node));
        printInOrder(node->right);
    }
}

// Insert node
struct Node* insert(struct Node* node, int value) {
    if (node == NULL) return newNode(value);

    if (value < node->value)
        node->left = insert(node->left, value);
    else if (value > node->value)
        node->right = insert(node->right, value);
    else
        return node;  // Duplicate values not allowed

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

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

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

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

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

    return node;
}

int main() {
    struct Node* root = NULL;
    
    // Test case 1: Right-Right case (20, 30, 40)
    printf("\nTest case 1: Right-Right case\n");
    root = insert(root, 20);
    printf("After inserting 20: ");
    printInOrder(root);
    printf("\n");
    
    root = insert(root, 30);
    printf("After inserting 30: ");
    printInOrder(root);
    printf("\n");
    
    root = insert(root, 40);
    printf("After inserting 40: ");
    printInOrder(root);
    printf("\n");

    // Reset tree for next test
    root = NULL;
    
    // Test case 2: Left-Left case (50, 40, 30)
    printf("\nTest case 2: Left-Left case\n");
    root = insert(root, 50);
    root = insert(root, 40);
    root = insert(root, 30);
    printf("Final tree: ");
    printInOrder(root);
    printf("\n");

    return 0;
}