/*
首先平衡二叉樹是一個二叉排序樹；
其基本思想是：
在構建二叉排序樹的過程中，當每插入一個節點時，
先檢查是否因為插入而破壞了樹的平衡性，若是，
找出最小不平衡樹，進行適應的旋轉，使之成為新的平衡二叉樹。
*/
#include<cstdio>
#include<cstdlib>
#define LH 1
#define EH 0
#define RH -1

using namespace std;

typedef struct BTNode
{
 int data;
 int BF;//平衡因子（balance factor）
 struct BTNode *lchild,*rchild;
}BTNode,*BTree;

void R_Rotate(BTree *p)//以p為根節點的二叉排序樹進行右旋轉
{
 BTree L;
 L=(*p)->lchild;
 (*p)->lchild=L->rchild;
 L->rchild=(*p);
 *p=L;//p指向新的根節點
}

void L_Rotate(BTree *p)//以p為根節點的二叉排序樹進行左旋轉
{
 BTree R;
 R=(*p)->rchild;
 (*p)->rchild=R->lchild;
 R->lchild=(*p);
 *p=R;
}

void LeftBalance(BTree *T)
{
 BTree L,Lr;
 L=(*T)->lchild;
 switch(L->BF)
 {
  //檢查T的左子樹平衡度，并作相應的平衡處理
  case LH://新節點插入在T的左孩子的左子樹上，做單右旋處理
   (*T)->BF=L->BF=EH;
   R_Rotate(T);
   break;
  case RH://新插入節點在T的左孩子的右子樹上，做雙旋處理
   Lr=L->rchild;
   switch(Lr->BF)
   {
    case LH:
     (*T)->BF=RH;
     L->BF=EH;
     break;
    case EH:
     (*T)->BF=L->BF=EH;
     break;
    case RH:
     (*T)->BF=EH;
     L->BF=LH;
     break;
   }
   Lr->BF=EH;
   L_Rotate(&(*T)->lchild);
   R_Rotate(T);
 }
}

void RightBalance(BTree *T)
{
 BTree R,Rl;
 R=(*T)->rchild;
 switch(R->BF)
 {
  case RH://新節點插在T的右孩子的右子樹上，要做單左旋處理
   (*T)->BF=R->BF=EH;
   L_Rotate(T);
   break;
  case LH://新節點插在T的右孩子的左子樹上，要做雙旋處理
   Rl=R->lchild;
   switch(Rl->BF)
   {
    case LH:
     (*T)->BF=EH;
     R->BF=RH;
     break;
    case EH:
     (*T)->BF=R->BF=EH;
     break;
    case RH:
     (*T)->BF=LH;
     R->BF=EH;
     break;
   }
   Rl->BF=EH;
   R_Rotate(&(*T)->rchild);
   L_Rotate(T);
 }
}

bool InsertAVL(BTree *T,int e,bool *taller)//變量taller反應T長高與否
{
 if(!*T)
 {
  *T=(BTree)malloc(sizeof(BTNode));
  (*T)->data=e;
  (*T)->lchild=(*T)->rchild=NULL;
  (*T)->BF=EH;
  *taller=true;
 }
 else
 {
  if(e==(*T)->data)//不插入
  {
   *taller=false;
   return false;
  }
  if(e<(*T)->data)
  {
   if(!InsertAVL(&(*T)->lchild,e,taller))//未插入
    return false;
   if(*taller)//以插入左子樹，且左子樹變高
   {
    switch((*T)->BF)
    {
     case LH://原本左子樹比右子樹高，需要做左平衡處理
      LeftBalance(T);
      *taller=false;
      break;
     case EH://原本左右子樹等高，現因左子樹增高而樹增高
      (*T)->BF=LH;
      *taller=true;
      break;
     case RH://原本右子樹比左子樹高，現在左右子樹等高
      (*T)->BF=EH;
      *taller=false;
      break;
    }
   }
  }
  else
  {
   //應在T的右子樹中搜尋
   if(!InsertAVL(&(*T)->rchild,e,taller))
    return false;
   if(*taller)//插入右子樹，且右子樹長高
   {
    switch((*T)->BF)
    {
     case LH://原本左子樹比右子樹高，現在左右子樹等高
      (*T)->BF=EH;
      *taller=false;
      break;
     case EH://原本左右子樹等高，現在右子樹變高
      (*T)->BF=RH;
      *taller=true;
      break;
     case RH://原本右子樹比左子樹高，現在需做右平衡處理
      RightBalance(T);
      *taller=false;
      break;
    }
   }
  }
 }
 return true;
}

bool Find(BTree T,int key)
{
 if(!T)
  return false;
 else if(T->data==key)
  return true;
 else if(T->data<key)
  return Find(T->rchild,key);
 else
  return Find(T->lchild,key);
}

void Output(BTree T)
{
 if(T)
 {
  printf("%d",T->data);
  if(T->lchild||T->rchild)
  {
   printf("(");
   Output(T->lchild);
   printf(",");
   Output(T->rchild);
   printf(")");
  }
 }
}

int main(int argc,char *argv[])
{
 int i;
 int A[]={3,2,1,4,5,6,7,10,9,8};
 BTree T=NULL;
 bool taller;
 for(i=0;i<sizeof(A)/sizeof(int);i++)
  InsertAVL(&T,A[i],&taller);
 Output(T);
 printf("/n");
 if(Find(T,6))
  printf("6 is find in the AVL tree!/n");
 else
  printf("6 is not find in the AVL tree!/n");

 return 0;
}