#ifndef _AVLTREE_H
#define _AVLTREE_H

struct Node;
typedef int ElementType;
typedef struct Node *PtrToNode;
typedef PtrToNode AvlTree;
typedef PtrToNode Position;

AvlTree MakeEmpty(AvlTree T);
int Height(Position P);
Position Find(ElementType X,AvlTree T);
Position FindMax(AvlTree T);
Position FindMin(AvlTree T);
AvlTree Insert(ElementType X,AvlTree T);
AvlTree Delete(ElementType X,AvlTree T);

#endif

struct Node
{
    ElementType element;
    PtrToNode Left;
    PtrToNode Right;
    int Height;
};

#include <stdlib.h>
#include <stdio.h>
#include "AvlTree.h"
#include "../../lib/common.h"

AvlTree MakeEmpty(AvlTree T)
{
    if(T!=NULL){
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}
int Height(Position P)
{
    if(P==NULL){
        return -1;
    }else{
        return P->Height;
    }
}
Position Find(ElementType X,AvlTree T)
{
    if(T==NULL){
        return NULL;
    }else if(X<T->element){
        return Find(X,T->Left);
    }else if(X>T->element){
        return Find(X,T->Right);
    }
    return T;
}
Position FindMax(AvlTree T)
{
    if(T!=NULL){
        while(T->Right!=NULL){
            T=T->Right;
        }
    }
    return T;
}
Position FindMin(AvlTree T)
{
    if(T!=NULL){
        while(T->Left!=NULL){
            T=T->Left;
        }
    }
    return T;
}
AvlTree SingleRotateWithLeft(AvlTree T)
{
    Position P;
    P=T->Left;
    T->Left=P->Right;
    P->Right=T;
    T->Height=Max(Height(T->Left),Height(T->Right))+1;
    P->Height=Max(Height(P->Left),Height(P->Right))+1;
    return P;
}
AvlTree SingleRotateWithRight(AvlTree T)
{
    Position P;
    P=T->Right;
    T->Right=P->Left;
    P->Left=T;
    T->Height=Max(Height(T->Left),Height(T->Right))+1;
    P->Height=Max(Height(P->Left),Height(P->Right))+1;
    return P;
}
AvlTree DoubleRotateWithLeft(AvlTree T)
{
    T->Left=SingleRotateWithRight(T->Left);
    return SingleRotateWithLeft(T);
}
AvlTree DoubleRotateWithRight(AvlTree T)
{
    T->Right=SingleRotateWithLeft(T->Right);
    return SingleRotateWithRight(T);
}
AvlTree Insert(ElementType X,AvlTree T)
{
    if(T==NULL){
        T=malloc(sizeof(struct Node));
        if(T==NULL){
            printf("out of space");
            exit(1);
        }else{
            T->Left=T->Right=NULL;
            T->Height=0;
        }else if(X<T->element){
            T->Left=Insert(X,T->Left);
            if((Height(T->Left)-Height(T->Right))==2){
                if(X<T->Left->element){
                    T=SingleRotateWithLeft(T);
                }else{
                    T=DoubleRotateWithLeft(T);
                }
            }
        }else if(X>T->element){
            T->Right=Insert(X,T->Right);
            if((Height(T->Right)-Height(T->Left))==2){
                if(X<T->Right->element){
                    T=DoubleRotateWithRight(T);
                }else{
                    T=SingleRotateWithRight(T);
                }
            }
        }
        T->Height=Max(Height(T->Left),Height(T->Right))+1;
        return T;
    }
}