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

enum Balance  { SLeft=-1, SEven=0, SRight=1 };

typedef struct node {
    int key;
    int count;
    struct node *left, *right;
    enum Balance  bal;
} Node;

void insert(int x, Node **p, int *h);
void balanceL(Node **p, int *h);
void balanceR(Node **p, int *h);
void removeNode(int x, Node **p, int *h);
void destroyTree(Node **tree);
void printTree(Node **tree);

/**
 * @brief Function to insert a key into the AVL tree.
 *
 * @param x : key to be inserted.
 * @param p : double pointer to the root of the AVL tree.
 * @param h : pointer to a flag used to indicate if tree height increased.
 *
 * This function inserts the key into the AVL tree and adjusts the balance
 * factors of the nodes accordingly. It also updates the height of the tree.
 */

void insert(int x, Node **p, int *h) {
    if (*p == NULL) {
        *p = (Node*) malloc(sizeof(Node));
        *h = 1;
        (*p)->key = x;
        (*p)->count = 1;
        (*p)->left = NULL;
        (*p)->right = NULL;
        (*p)->bal = SEven;
    } else if ((*p)->key > x ) {
        insert(x, &((*p)->left), h);
        if (*h) balanceL(p, h);
    } else if ((*p)->key < x ) {
        insert(x, &((*p)->right), h);
        if (*h) balanceR(p, h);
    } else {
        (*p)->count++;
    }
}

/**
 * @brief Function to left balance the AVL tree.
 *
 * @param p : double pointer to the root of the AVL tree.
 * @param h : pointer to a flag used to indicate if tree height increased.
 *
 * This function is used after insertion into the right subtree. If the
 * balance factor becomes 2 then depending upon the balance factor of the
 * right child, appropriate rotations are performed to balance the tree.
 */

void balanceL(Node **p, int *h) {
    Node *p1 = NULL, *p2 = NULL;
    if ((*p)->bal == SRight) {
        (*p)->bal = SEven;
        *h = 0;
    } else if ((*p)->bal == SEven) {
        (*p)->bal = SLeft;
    } else if ((*p)->bal == SLeft) {
        p1 = (*p)->left;
        if(p1->bal == SLeft) {
            (*p)->left = p1->right;
            p1->right = *p;
            (*p)->bal = SEven;
            *p = p1;
        } else {
            p2 = p1->right;
            p1->right = p2->left;
            p2->left = p1;
            (*p)->left = p2->right;
            p2->right = *p;
            if(p2->bal == SLeft) {
                (*p)->bal = SRight;
            } else {
                (*p)->bal = SEven;
            }
            if(p2->bal == SRight) {
                p1->bal = SLeft;
            } else {
                p1->bal = SEven;
            }
            *p = p2;
        }
        (*p)->bal = SEven;
        *h = 0;
    }
}

/**
 * @brief Function to right balance the AVL tree.
 *
 * @param p : double pointer to the root of the AVL tree.
 * @param h : pointer to a flag used to indicate if tree height increased.
 *
 * This function is used after insertion into the left subtree. If the
 * balance factor becomes -2 then depending upon the balance factor of the
 * left child, appropriate rotations are performed to balance the tree.
 */
void balanceR(Node **p, int *h) {
    Node *p1 = NULL, *p2 = NULL;
    if ((*p)->bal == SLeft) {
        (*p)->bal = SEven;
        *h = 0;
    } else if ((*p)->bal == SEven) {
        (*p)->bal = SRight;
    } else if ((*p)->bal == SRight) {
        p1 = (*p)->right;
        if(p1->bal == SRight) {
            (*p)->right = p1->left;
            p1->left = *p;
            (*p)->bal = SEven;
            *p = p1;
        } else {
            p2 = p1->left;
            p1->left = p2->right;
            p2->right = p1;
            (*p)->right = p2->left;
            p2->left = *p;
            if(p2->bal == SRight) {
                (*p)->bal = SLeft;
            } else {
                (*p)->bal = SEven;
            }
            if(p2->bal == SLeft) {
                p1->bal = SRight;
            } else {
                p1->bal = SEven;
            }
            *p = p2;
        }
        (*p)->bal = SEven;
        *h = 0;
    }
}

/**
 * @brief Function to remove a node from the AVL tree.
 *
 * @param x : key to be removed.
 * @param p : double pointer to the root of the AVL tree.
 * @param h : pointer to a flag used to indicate if tree height decreased.
 *
 * This function removes the key from the AVL tree and adjusts the balance
 * factors of the nodes accordingly. It also updates the height of the tree.
 */
void removeNode(int x, Node **p, int *h) {
    Node *temp = NULL;
    Node *prev = NULL;
    if (*p == NULL) return;
    else if ((*p)->key > x){
        removeNode(x, &((*p)->left), h);
        if (*h) balanceL(p, h);
    } else if ((*p)->key < x){
        removeNode(x, &((*p)->right), h);
        if (*h) balanceR(p, h);
    } else {
        temp = *p;
        if (temp->right == NULL) {
            *p = temp->left;
            *h = 1;
        } else if (temp->left == NULL) {
            *p = temp->right;
            *h = 1;
        } else {
            prev = NULL;
            temp = (*p)->left;
            while (temp->right) {
                prev = temp;
                temp = temp->right;
            }
            (*p)->key = temp->key;
            if (prev != NULL) {
                prev->right = temp->left;
            } else {
                (*p)->left = temp->left;
            }
            *h = 1;
        }
        free(temp);
    }
}

/**
 * @brief Function to delete an AVL tree.
 *
 * @param tree : double pointer to the root of the AVL tree.
 *
 * This function recursively deletes all nodes of the AVL tree pointed by tree.
 */
void destroyTree(Node **tree) {
    if (*tree) {
        destroyTree(&((*tree)->left));
        destroyTree(&((*tree)->right));
        free(*tree);
        *tree = NULL;
    }
}

/**
 * @brief Function to print the AVL tree.
 *
 * @param tree : double pointer to the root of the AVL tree.
 *
 * This function prints the keys of the AVL tree in an in-order fashion.
 */
void printTree(Node **tree) {
    if(*tree) {
        printTree(&((*tree)->left));
        printf("%d ", (*tree)->key);
        printTree(&((*tree)->right));
    }
}

int main() {
    Node *root = NULL;
    int h = 0;
    int treeSize = 100;  // Set your desired tree size here.


    srand(time(NULL));
    for (int i = 0; i < treeSize; i++) {
        insert(rand() % 1000, &root, &h);
    }

    printf("\n Sorted output AVL tree is: \n");
    printTree(&root);

    // Free the memory allocated for the tree.
    destroyTree(&root);
    return 0;
}