#include<iostream>
#include<cstdlib>
using namespace std;

typedef struct TreeNode
{
int Element;
int Height;
TreeNode *Left;
TreeNode *Right;
}*MyAVLTree;

MyAVLTree MakeEmpty(MyAVLTree &T);
void InorderTraverse(const MyAVLTree &T);
static int Max(int a,int b);
static int Height(MyAVLTree &T);
MyAVLTree Find(const MyAVLTree &T,int X);
MyAVLTree FindMin(const MyAVLTree &T);
MyAVLTree FindMax(const MyAVLTree &T);
static MyAVLTree LeftSingleRotate(MyAVLTree &K2);
static MyAVLTree RightSingleRotate(MyAVLTree &K1);
static MyAVLTree LeftDoubleRotate(MyAVLTree &K1);
static MyAVLTree RightDoubleRotate(MyAVLTree &K1);
MyAVLTree Insert(MyAVLTree &T,int X);
MyAVLTree Delete(MyAVLTree &T,int X);

int main()  //text
{
MyAVLTree T=NULL,Temp=NULL;
int a[15]={7,8,9,4,5,6,3,1,2,11,19,15,18,14,13};

MakeEmpty(T);

for(int i=0;i<15;i++)
   Insert(T,a[i]);
cout <<"创建一个AVL树后" <<"树深为" <<Height(T) <<" 中序遍历为" <<endl ;
InorderTraverse(T);
cout <<endl ;

Delete(T,11);
cout <<"删除6后树深为" <<Height(T) <<" 中序遍历为" <<endl ;
InorderTraverse(T);
cout <<endl ;

Temp=Find(T,10);
if(Temp) 
cout <<Temp->Element <<"被查找到了" <<endl ;
else 
cout <<"没有找到这个元素 " <<endl ;

Temp=FindMin(T);
cout <<Temp->Element <<"是最小值" <<endl ;

Temp=FindMax(T);
cout <<Temp->Element <<"是最大值" <<endl ;

MakeEmpty(T);
return 0;
}

static int Max(int a,int b)
{
return a>b?a:b;
}

MyAVLTree MakeEmpty(MyAVLTree &T)
{
if(T)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
delete T;
}
return NULL;
}

void InorderTraverse(const MyAVLTree &T)
{
if(T)
{
InorderTraverse(T->Left);
cout <<T->Element <<' ' ;
InorderTraverse(T->Right);
}
}

static int Height(MyAVLTree &T)
{
if(T) return T->Height;
else return -1;
}

MyAVLTree Find(const MyAVLTree &T,int X)
{
if(T==NULL) return NULL;
else if(X>T->Element) return Find(T->Right,X);
else if(X<T->Element) return Find(T->Left,X);
else return T;
}

MyAVLTree FindMin(const MyAVLTree &T)
{
if(T->Left) return FindMin(T->Left);
else return T;
}

MyAVLTree FindMax(const MyAVLTree &T)
{
if(T->Right) return FindMax(T->Right);
else return T;
}

//the following rotate ,i suggest you draw a picture 
static MyAVLTree LeftSingleRotate(MyAVLTree &K2) //cut off the weight of left
{
MyAVLTree K1=NULL;

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(K1->Right))+1;
return K1;
}

static MyAVLTree RightSingleRotate(MyAVLTree &K1)  //cut off the weight of right 
{
MyAVLTree K2=NULL;

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->Left),Height(K2->Right))+1;
return K2;
}

static MyAVLTree LeftDoubleRotate(MyAVLTree &K1)  //cut off the weight of left
{
K1->Left=RightSingleRotate(K1->Left); //make K2 become a node can rotate 
return LeftSingleRotate(K1);         
}

static MyAVLTree RightDoubleRotate(MyAVLTree &K1) //cut off the weight of right
{
K1->Right=LeftSingleRotate(K1->Right); //a same theory 
return RightSingleRotate(K1);
}

MyAVLTree Insert(MyAVLTree &T,int X)
{
if(T==NULL)      //create a new node
{
T=new TreeNode;
if(T==NULL) cout <<"空间不足 " <<endl ;
else
{
T->Element=X;
   T->Left=T->Right=NULL;
   T->Height=0;
}
}
else if(X<T->Element)  //go left
{
T->Left=Insert(T->Left,X);
if(Height(T->Left)-Height(T->Right)==2)  //if the left is weighter 
   if(X<T->Left->Element)                 
       T=LeftSingleRotate(T);          //it can be balanced by just singlerotate(first advice)
   else
       T=LeftDoubleRotate(T);          //doublerotate condition
}
else if(X>T->Element)       //go right 
{
T->Right=Insert(T->Right,X);
if(Height(T->Right)-Height(T->Left)==2)  //a same theory
   if(X>T->Right->Element)
       T=RightSingleRotate(T);
   else
       T=RightDoubleRotate(T);
}
T->Height=Max(Height(T->Left),Height(T->Right))+1;  //the height of tree increase
return T;
}

MyAVLTree Delete(MyAVLTree &T,int X)
{
MyAVLTree Temp=NULL;

if(T==NULL) cout <<"未找到这个元素" <<endl ;
else if(X<T->Element) 
{
T->Left=Delete(T->Left,X);
if(Height(T->Right)-Height(T->Left)==2)     //if not balanced
{
if(Height(T->Right->Left) > Height(T->Right->Right)) //if it needs doublerotate
   LeftDoubleRotate(T);
else
   LeftSingleRotate(T);          //else it needs singlerotate           
}
}
else if(X>T->Element)              //a same theory
{
T->Right=Delete(T->Right,X);
if(Height(T->Left)-Height(T->Right)==2)
if(Height(T->Left->Right)>Height(T->Left->Left))
   RightDoubleRotate(T);
else 
   RightSingleRotate(T);
} 
else if(T->Left&&T->Right)   //balanced deletion
{
Temp=FindMin(T->Right);
T->Element=Temp->Element;
T->Right=Delete(T->Right,T->Element);
}
else     //balanced deletion
{
Temp=T;
if(T->Left==NULL) T=T->Right;
else if(T->Right==NULL) T=T->Left;
delete Temp;
}
if(T)
T->Height=Max(Height(T->Left),Height(T->Right))+1;
return T;  //important
}