//avl.h
#ifndef __AVL_H__
#define __AVL_H__

typedef int KEY_TYPE;

/* struct */
typedef struct AVL{
 KEY_TYPE key;
 int height;
 struct AVL* lchild;
 struct AVL* rchild;
}AVL;

AVL* New_Node(KEY_TYPE key, AVL* lchild, AVL* rchild, int height = 0);
inline int GetHeight(AVL* node);

AVL* RR_Rotate(AVL* k2);
AVL* LL_Rotate(AVL* k2);
AVL* LR_Rotate(AVL* k3);
AVL* RL_Rotate(AVL* k3);

AVL* Insert(AVL* root, KEY_TYPE key);
AVL* Delete(AVL* root, KEY_TYPE key);
void InOrder(AVL* root);

#endif

//avl.cpp

#include "AVL.h"

#include<iostream>

AVL* New_Node(KEY_TYPE key, AVL* lchild, AVL* rchild, int height)

{

    AVL* p_avl = new AVL;

    p_avl->key = key;

    p_avl->lchild = lchild;

    p_avl->rchild = rchild;

    p_avl->height = height;

    return p_avl;

}

inline int GetHeight(AVL* node)

{

    return (node==NULL)? -:node->height;

}

inline int max(int a, int b)

{

    return a>b?a:b;

}

/* RR(Y rotates to the right):

        k2                   k1

       /  \                 /  \

      k1   Z     ==>       X   k2

     / \                      /  \

    X   Y                    Y    Z

*/

AVL* RR_Rotate(AVL* k2)

{

    AVL* k1 = k2->lchild;

    k2->lchild = k1->rchild;

    k1->rchild = k2;

    k2->height = max(GetHeight(k2->lchild), GetHeight(k2->rchild)) + ;

    k1->height = max(GetHeight(k1->lchild), k2->height) + ;

    return k1;

}

/* LL(Y rotates to the left):

        k2                       k1

       /  \                     /  \

      X    k1         ==>      k2   Z

          /  \                /  \

         Y    Z              X    Y

 */

AVL* LL_Rotate(AVL* k2)

{

    AVL* k1 = k2->rchild;

    k2->rchild = k1->lchild;

    k1->lchild = k2;

    k2->height = max(GetHeight(k2->lchild), GetHeight(k2->rchild)) + ;

    k1->height = max(GetHeight(k1->rchild), k2->height) + ;

    return k1;

}

/* LR(B rotates to the left, then C rotates to the right):

      k3                         k3                       k2

     /  \                       /  \                     /  \

    k1   D                     k2   D                   k1   k3

   /  \         ==>           /  \        ==>          / \   / \

  A    k2                    k1   C                   A  B  C   D

      /  \                  /  \

     B    C                A    B

*/

AVL* LR_Rotate(AVL* k3)

{

    k3->lchild = LL_Rotate(k3->lchild);

    return RR_Rotate(k3);

}

/*

       k3                         k3                          k2

      /  \                       /  \                        /  \

     A    k1                    A    k2                     k3   k1

         /  \       ==>             /  \         ==>       /  \  / \

        k2   B                     C    k1                A   C D   B

       /  \                            /  \

      C    D                          D    B 

 */

AVL* RL_Rotate(AVL* k3)

{

    k3->rchild = RR_Rotate(k3->rchild);

    return LL_Rotate(k3);

}

AVL* Insert(AVL* root, KEY_TYPE key)

{

    if(root == NULL)

        return (root = New_Node(key, NULL, NULL));

    else if(key < root->key)

        root->lchild = Insert(root->lchild, key);

    else

        root->rchild = Insert(root->rchild, key);

    root->height = max(GetHeight(root->lchild), GetHeight(root->rchild)) + ;

    if(GetHeight(root->lchild) - GetHeight(root->rchild) == )

    {

        if(key < root->lchild->key)

            root = RR_Rotate(root);

        else

            root = LR_Rotate(root);

    }

    else if(GetHeight(root->rchild) - GetHeight(root->lchild) == )

    {

        if(key < root->rchild->key)

            root = RL_Rotate(root);

        else

            root = LL_Rotate(root);

    }

    return root;

}

AVL* Delete(AVL* root, KEY_TYPE key)

{

    if(!root)

        return NULL;

    if(key == root->key)

    {

        if(root->rchild == NULL)

        {

            AVL* temp = root;

            root = root->lchild;

            delete(temp);

            return root;

        }

        else

        {

            AVL* temp = root->rchild;

            while(temp->lchild)

                temp = temp->lchild;

            root->key = temp->key;

            root->rchild = Delete(root->rchild, temp->key);

        }

    }

    else if(key < root->key)

        root->lchild = Delete(root->lchild, key);

    else

        root->rchild = Delete(root->rchild, key);

    root->height = max(GetHeight(root->lchild), GetHeight(root->rchild)) + ;

    if(GetHeight(root->rchild) - GetHeight(root->lchild) == )

    {

        if(GetHeight(root->rchild->rchild) >= GetHeight(root->rchild->lchild))

            root = LL_Rotate(root);

        else

            root = RL_Rotate(root);

    }

    else if(GetHeight(root->lchild) - GetHeight(root->rchild) == )

    {

        if(GetHeight(root->lchild->lchild) >= GetHeight(root->lchild->rchild))

            root = RR_Rotate(root);

        else

            root = LR_Rotate(root);

    }

    return root;

}

void InOrder(AVL* root)

{

    if(root)

    {

        InOrder(root->lchild);

        printf("key: %d height: %d ", root->key, root->height);

        if(root->lchild)

            printf("left child: %d ", root->lchild->key);

        if(root->rchild)

            printf("right child: %d ", root->rchild->key);

        printf("\n");

        InOrder(root->rchild);

    }

}

// main.cpp

#include<iostream>

#include "AVL.h"

int main(int argc, char* argv[])

{

    AVL* root = NULL;

    int vector[] = {,,,,,,,,};

    const int length = sizeof(vector)/sizeof(int);

    for(int i = ; i< length;i++)

        root = Insert(root, vector[i]);

    printf("\nInOrder: \n");

    InOrder(root);

    int input;

    printf("\nplease input the value you want to delete: ");

    scanf("%d",&input);

    while()

    {

        root = Delete(root, input);

        printf("\nAfter delete %u:\n",input);

        InOrder(root);

        printf("\nplease input another value you want to delete: ");

        scanf("%u",&input);

    }

    printf("\n");

    return ;

}