#include<stdio.h>
#include "fatal.h"

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

typedef int ElementType ;

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

struct AvlNode
{
    ElementType Element;
    AvlTree left;
    AvlTree right;
    int height;
};

AvlTree MakeEmpty(AvlTree T)
{
    if(T!=NULL)
    {
        MakeEmpty(T->left);
        MakeEmpty(T->right);
        free(T);
    }
    return NULL;
}

Position Find(ElementType X,AvlTree T)
{
    if(T==NULL)
        return NULL;
    if(X<T->Element)
        return Find(X,T->left);
    else if(X>T->Element)
        return Find(X,T->right);
    else
        return T;
}

Position FindMin(AvlTree T)
{
    if(T==NULL)
        return NULL;
    if(T->left==NULL)
        return T;
    else
        return FindMin(T->left);
}

Position FindMax(AvlTree T)
{
    if(T==NULL)
        return NULL;
    if(T->right==NULL)
        return T;
    else
        return FindMax(T->right);
}

static int Height(Position P)
{
    if(P==NULL)
        return -1;
    else
        return P->height;
}

static int Max(int Lhs,int Rhs)
{
    return Lhs>Rhs?Lhs:Rhs;
}
//RR旋转
static Position SingleRotateWithLeft(Position K2)
{
    Position K1;
    K1=K2->left;
    K2->left=K1->right;
    K1->right=K2;
    K2->height=Max(Height(K2->left),Height(K2->right))+1;
    K1->height=Max(Height(K1->left),Height(K2->right))+1;
    return K1;
}
//LL旋转
static Position SingleRotateWithRight(Position K1)
{
    Position K2;
    K2=K1->right;
    K1->right=K2->left;
    K2->left=K1;
    K1->height=Max(Height(K1->left),Height(K1->right))+1;
    K2->height=Max(Height(K2->right),Height(K1->left))+1;
    return K2;
}
//LR旋转
static Position DoubleRotateWithLeft(Position K3)
{
    K3->left=SingleRotateWithRight(K3->left);

    return SingleRotateWithLeft(K3);
}

//RL旋转
static Position DoubleRotateWithRight(Position K3)
{
    K3->right=SingleRotateWithLeft(K3->right);
    return SingleRotateWithRight(K3);
}

AvlTree Insert(ElementType X,AvlTree T)
{
    if(T==NULL)
    {
        T=malloc(sizeof(struct AvlNode));
        if(T==NULL)
            FatalError("out of space!!!");
        else
        {
            T->Element=X;
            T->right=T->left=NULL;
        }
    }
    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=SingleRotateWithRight(T);
           else
               T=DoubleRotateWithRight(T);
        }
    }
   T->height=Max(Height(T->left),Height(T->right))+1;
   return T;
}

AvlTree Delete(ElementType X,AvlTree T)
{
    Position TmpCell;
    if(T==NULL)
        Error("Element not found");
    else if(X<T->Element)
    {
        T->left=Delete(X,T->left);
        if(Height(T->right)-Height(T->left)==2)
        {
            if(Height(T->right->left)>Height(T->right->right))
                T=DoubleRotateWithRight(T);
            else 
                T=SingleRotateWithRight(T);
        }
    }
    else if(X>T->Element)
    {
        T->right=Delete(X,T->left);
        if(Height(T->left)-Heighe(T->right)==2)
        {
            if(Heighe(T->left->right)>Height(T->left->left))
                T=DoubleRotateWithLeft(T);
            else
                T=SingleRotateWithLeft(T);
        }
    }
    //找到要删除的节点就是根节点，且根节点的左右子树都不为空
    else if(T->left&&T->right)
    {
        if(Height(T->left)>Height(T->right))
        {
            T->Element=FindMax(T->left)->Element;
            T->left=Delete(T->Element,T->left);
        }
        else
        {
            T->Element=FindMin(T->right)->Element;
            T->right=Delete(T->Element,T->right);
        }
    }
    //找到是根节点，但是根节点有一个或者没有子节点
    else
    {
        TmpCell=T;
        if(T->left==NULL)
            T=T->right;
        else if(T->right==NULL)
            T=T->left;
        free(TmpCell);
    }
    T->height=Max(Height(T->left),Height(T->right))+1;
    return T;
}

ElementType Retrieve(Position P)
{
    if(P==NULL)
        return -1;
    else
        return P->Element;
}

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

#define Error( Str )        FatalError( Str )
#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )