// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// AVL tree node
struct Node {
    struct Node* left;
    struct Node* right;
    int data;
    struct Node* parent;
    int height;
};


void preorder(struct Node* root)
{

    cout<<root->data<<" ";

    if (root->left != NULL) {
        preorder(root->left);
    }


    if (root->right != NULL) {
        preorder(root->right);
    }
}

// Function to update the height of
// a node according to its children's
// node's heights
void fixHeight(struct Node* root)
{
    if (root != NULL) {

        // Store the height of the
        // current node
        int tempHeight = 1;

        // Store the height of the left
        // and right subtree
        if (root->left != NULL) {
            tempHeight = root->left->height + 1;
        }

        if (root->right != NULL) {
            tempHeight = max(tempHeight, root->right->height + 1);
        }

        // Update the height of the
        // current node
        root->height = tempHeight;
    }
}

// Function to handle Left Left Case
struct Node* LeftLeftRotate(
    struct Node* root)
{

    struct Node* temp = root->left;


    root->left = temp->right;

    if (temp->right != NULL)
        temp->right->parent = root;


    temp->right = root;


    temp->parent = root->parent;

    root->parent = temp;

    if (temp->parent != NULL and root->data < temp->parent->data) {
        temp->parent->left = temp;
    }
    else {
        if (temp->parent != NULL)
            temp->parent->right = temp;
    }


    root = temp;


    fixHeight(root->left);
    fixHeight(root->right);
    fixHeight(root);
    fixHeight(root->parent);

    return root;
}

// Function to handle Right Right Case
struct Node* RightRightRotate(
    struct Node* root)
{

    struct Node* temp = root->right;


    root->right = temp->left;

    if (temp->left != NULL)
        temp->left->parent = root;


    temp->left = root;


    temp->parent = root->parent;


    root->parent = temp;


    if (temp->parent != NULL
        && root->data < temp->parent->data) {
        temp->parent->left = temp;
    }
    else {
        if (temp->parent != NULL)
            temp->parent->right = temp;
    }

    // Make temp as the new root
    root = temp;

    // Update the heights
    fixHeight(root->left);
    fixHeight(root->right);
    fixHeight(root);
    fixHeight(root->parent);

    // Return the root node
    return root;
}

// Function to handle Left Right Case
struct Node* LeftRightRotate(
    struct Node* root)
{
    root->left = RightRightRotate(root->left);
    return LeftLeftRotate(root);
}

// Function to handle right left case
struct Node* RightLeftRotate(
    struct Node* root)
{
    root->right = LeftLeftRotate(root->right);
    return RightRightRotate(root);
}

// Function to balance the tree after
// deletion of a node
struct Node* Balance( struct Node* root)
{

    int leftHeight = 0;
    int rightHeight = 0;

    if (root->left != NULL)
        leftHeight = root->left->height;

    if (root->right != NULL)
        rightHeight = root->right->height;

    // If current node is not balanced
    if (abs(leftHeight - rightHeight) == 2) {
        if (leftHeight < rightHeight) {


            int rightheight1 = 0;
            int rightheight2 = 0;
            if (root->right->right != NULL)
                rightheight2 = root->right->right->height;

            if (root->right->left != NULL)
                rightheight1 = root->right->left->height;

            if (rightheight1 > rightheight2) {

                // Right Left Case
                root = RightLeftRotate(root);
            }
            else {

                // Right Right Case
                root = RightRightRotate(root);
            }
        }
        else {


            int leftGrandchildHeight = 0;
            int rightGrandchildHeight = 0;
            if (root->left->right != NULL)
                rightGrandchildHeight = root->left->right->height;

            if (root->left->left != NULL)
                leftGrandchildHeight = root->left->left->height;

            if (leftGrandchildHeight > rightGrandchildHeight) {

                // Left Left Case
                root = LeftLeftRotate(root);
            }
            else {

                // Left Right Case
                root = LeftRightRotate(root);
            }
        }
    }

    // Return the root node
    return root;
}


struct Node* Insert(struct Node* root,struct Node* parentent,int data)
{

    if (root == NULL) {

        // Create and assign tempHeightues
        // to a new node
        root = new struct Node;
        if (root == NULL)
            cout << "Error in memory" << endl;
        else {
            root->height = 1;
            root->left = NULL;
            root->right = NULL;
            root->parent = parentent;
            root->data = data;
        }
    }

    else if (root->data > data) {

        // Recur to the left subtree
        // to insert the node
        root->left = Insert(root->left,
                            root, data);

        // Store the heights of the
        // left and right subtree
        int leftHeight = 0;
        int rightHeight = 0;

        if (root->left != NULL)
            leftHeight = root->left->height;

        if (root->right != NULL)
            rightHeight = root->right->height;

        // Balance the tree if the
        // current node is not balanced
        if (leftHeight-rightHeight==2 or rightHeight-leftHeight==2) {

            if (root->left != NULL
                && data < root->left->data) {

                // Left Left Case
                root = LeftLeftRotate(root);
            }
            else {

                // Left Right Case
                root = LeftRightRotate(root);
            }
        }
    }

    else if (root->data < data) {

        // Recur to the right subtree
        // to insert the node
        root->right = Insert(root->right,     root, data);

        // Store the heights of the left
        // and right subtree
        int leftHeight = 0;
        int rightHeight = 0;

        if (root->left != NULL)
            leftHeight = root->left->height;

        if (root->right != NULL)
            rightHeight = root->right->height;

        // Balance the tree if the
        // current node is not balanced
        if (abs(leftHeight - rightHeight) == 2) {
            if (root->right != NULL
                && data < root->right->data) {

                // Right Left Case
                root = RightLeftRotate(root);
            }
            else {

                // Right Right Case
                root = RightRightRotate(root);
            }
        }
    }

    // Case when given data is
    // already in tree
    else {
    }

    // Update the height of the
    // root node
    fixHeight(root);

    // Return the root node
    return root;
}


struct Node* Delete( struct Node* root, int data)
{
    if (root != NULL) {


        if (root->data == data) {


            if (root->right == NULL
                && root->left != NULL) {
                if (root->parent != NULL) {
                    if (root->parent->data
                        < root->data)
                        root->parent->right = root->left;
                    else
                        root->parent->left = root->left;


                    fixHeight(root->parent);
                }

                root->left->parent = root->parent;


                root->left = Balance(
                    root->left);

                return root->left;
            }

            // Replace root with its
            // right child
            else if (root->left == NULL && root->right != NULL) {
                if (root->parent != NULL) {
                    if (root->parent->data < root->data)
                        root->parent->right = root->right;
                    else
                        root->parent->left = root->right;

                    // Update the height
                    // of the root's parentent
                    fixHeight(root->parent);
                }

                root->right->parent = root->parent;


                root->right = Balance(root->right);
                return root->right;
            }


            else if (root->left == NULL
                     && root->right == NULL) {
                if (root->parent->data < root->data) {
                    root->parent->right = NULL;
                }
                else {
                    root->parent->left = NULL;
                }

                if (root->parent != NULL)
                    fixHeight(root->parent);

                root = NULL;
                return NULL;
            }


            else {
                struct Node* temp = root;
                temp = temp->right;
                while (temp->left != NULL) {
                    temp = temp->left;
                }

                int tempHeight = temp->data;

                root->right= Delete(root->right, temp->data);

                root->data = tempHeight;


                root = Balance(root);
            }
        }


        else if (root->data < data) {
            root->right = Delete(root->right, data);

            root = Balance(root);
        }


        else if (root->data > data) {
            root->left = Delete(root->left, data);

            root = Balance(root);
        }


        if (root != NULL) {
            fixHeight(root);
        }
    }


    else {
       return NULL;
    }

    // Return the root node
    return root;
}

// Driver Code
int main()
{
    struct Node* root;
    root = NULL;

    // Function call to insert the nodes
    root = Insert(root, NULL, 9);
    root = Insert(root, NULL, 5);
    root = Insert(root, NULL, 10);
    root = Insert(root, NULL, 0);
    root = Insert(root, NULL, 6);

    // Print the tree before deleting node
    cout << "Before deletion:\n";
    preorder(root);

    // Function Call to delete node 10
    root = Delete(root, 10);

    // Print the tree after deleting node
    cout << "After deletion:\n";
    preorder(root);
}