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