AVL Trees

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

// Structure to represent a node in the AVL tree
struct Node {
    int key;
    struct Node* left;
    struct Node* right;
    int height;
};

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

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

// Helper function that allocates a new node with the given key
struct Node* newNode(int key) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // New node is initially added at leaf
    return(node);
}

// Right rotate subtree rooted with y
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(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Return new root
    return x;
}

// Left rotate subtree rooted with x
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(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // Return new root
    return y;
}

// Get Balance factor of node N
int getBalance(struct Node* N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// Function to insert a key in the subtree rooted with node and returns the new root of the subtree
struct Node* insert(struct Node* node, int key) {
    // 1. Perform the normal BST insertion
    if (node == NULL)
        return(newNode(key));

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else { // Equal keys are not allowed in BST
        printf("The key %d already exists in the AVL tree.\n", key);
        return node;
    }

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

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

    // 4. If this node becomes unbalanced, then there are 4 cases

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

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

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

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

    // return the (unchanged) node pointer
    return node;
}

// Function to find the node with minimum key value found in that tree
struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;

    // Loop down to find the leftmost leaf
    while (current->left != NULL)
        current = current->left;

    return current;
}

// Recursive function to delete a node with given key from subtree with given root. It returns root of the modified subtree.
struct Node* deleteNode(struct Node* root, int key) {
    // STEP 1: PERFORM STANDARD BST DELETE

    if (root == NULL) {
        printf("Key %d does not exist in the AVL tree.\n", key);
        return root;
    }

    // If the key to be deleted is smaller than the root's key, then it lies in left subtree
    if (key < root->key)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted is greater than the root's key, then it lies in right subtree
    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    // if key is same as root's key, then This is the node to be deleted
    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 = minValueNode(root->right);

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

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

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

    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
    root->height = 1 + max(height(root->left), height(root->right));

    // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether this node became unbalanced)
    int balance = getBalance(root);

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

    // 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;
}

// Function to print preorder traversal of the tree
void preOrder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}

// Main function to drive the AVL Tree insertion and deletion
int main() {
    struct Node* root = NULL;
    int choice, key;

    do {
        printf("\nAVL Tree Operations Menu:\n");
        printf("1. Insert a key\n");
        printf("2. Delete a key\n");
        printf("3. Print Preorder traversal\n");
        printf("4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter key to insert: ");
                scanf("%d", &key);
                root = insert(root, key);
                break;

            case 2:
                printf("Enter key to delete: ");
                scanf("%d", &key);
                root = deleteNode(root, key);
                break;

            case 3:
                printf("Preorder traversal of the AVL tree is:\n");
                preOrder(root);
                printf("\n");
                break;

            case 4:
                printf("Exiting...\n");
                break;

            default:
                printf("Invalid choice! Please try again.\n");
                break;
        }
    } while (choice != 4);

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

BFS Matrix

-
#include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 int adj[MAX][MAX];   int state[MAX];      int queue[MAX], front = -1, rear = -1;  void create_graph(int n, int gtype); void BF_Traversal(int n); void BFS(int v, int n); void insert_queue(int vertex); int delete_queue(); int isEmpty_queue(); int main() {     int n, gtype;          printf("Enter 1 for undirected graph and -1 for directed graph: ");     scanf("%d", &gtype);     printf("Enter the number of vertices: ");     scanf("%d", &n);          create_graph(n, gtype);          BF_Traversal(n);          return 0; } void create_graph(int n, int gtype) {     int max_edges, src, dest;          if (gtype == 1)         max_edges = (n * (n - 1)) /...
Read more

BFS List

-
#include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 struct Node { int vertex; struct Node* next; }; int queue[MAX],front=-1,rear=-1; int state[MAX]; struct Node* adj[MAX]; void create_graph(int n,int gtype); void insert_queue(int v); int delete_queue(); int isEmpty_queue(); void BFT(int n); void BFS(int start,int n); void add_edge(int src,int dest); struct Node* create_node(int v); int main() { int gtype,n; printf("Enter 1 for undirected graph and -1 for directed graph:"); scanf("%d",&gtype); printf("Enter the number of vertices:"); scanf("%d",&n); create_graph(n,gtype); BFT(n); return 0; } void create_graph(int n,int gtype) { int max_edges,src,dest; if(gtype==1) max_edges=(n*(n-1))/2; else if(gtype==-1) max_edges=(n*(n-1)); for(int i=0;i<n;i++) adj[i]=NULL; for(int i=0;i<max_edges;i++) { printf("Enter edge %d (press -1 and -1 to quit):...
Read more