#include<bits/stdc++.h>
#define MaxSize 100
using namespace std;
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode{
int data;
AVLTree Left;
AVLTree Right;
int Height;
};
int Max(int a,int b){
return a>b?a:b;
}
AVLTree SingleLeftRotation(AVLTree A){
//A必须有一个左子结点B
//将A与B做左单旋(LL),更新A与B的高度,返回新的根结点B
AVLTree B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = Max(getheight(A->Left),getheight(A->Right))+1;
B->Height = Max(getheight(B->Left),A->Height)+1;
return B;
}
AVLTree SingleRightRotation(AVLTree A){
//A有右子结点B,RR
AVLTree B = A->Right;
A->Right = B->Left;
B->Left = A;
A->Height = Max(getheight(A->Left),getheight(A->Right))+1;
B->Height = Max(getheight(B->Right),A->Height)+1;
return B;
}
AVLTree DoubleLeftRightPotation(AVLTree A){
//A有左子结点B,B有右结点C,LR旋转
A->Left = SingleRightRotation(A->Left);//BandC
return SingleLeftRotation(A);//AandC LL
}
AVLTree DoubleRightLeftPotation(AVLTree A){
//RL
A->Right = SingleLeftRotation(A->Right);
return SingleRightRotation(A);
}
//插入
AVLTree Insert(AVLTree T,int X){
if(!T){
T = (AVLTree)malloc(sizeof(struct AVLNode));
T->data = X;
T->Height = 0;
T->Right = T->Left = NULL;
}
else if(X < T->data){
T->Left = Insert(T->Left,X);
if(getheight(T->Left)-getheight(T->Right) == 2)
if(X<T->Left->data)
T = SingleLeftRotation(T);
else
T = DoubleLeftRightPotation(T);
}
else if(X > T->data){
T->Right = Insert(T->Right,X);
if(getheight(T->Left)-getheight(T->Right) == -2)
if(X > T->Right->data)
T = SingleRightRotation(T);
else
T = DoubleRightLeftPotation(T);
}
T->Height = Max(getheight(T->Left),getheight(T->Right))+1;
return T;
}