#include<iostream>
#define N 10

using namespace std;

struct TreeNode{
      TreeNode *left;
      TreeNode *right;
      int data;
      int bf; 
       
       
       };

void leftRotation(TreeNode *,bool *);
void rightRotation(TreeNode *,bool *);
void avlInsert(TreeNode **,int,bool *);
void display(TreeNode *);


int main(void){
    
    TreeNode *head=NULL;
    bool flag;
    
    avlInsert(&head,3,&flag);
    avlInsert(&head,5,&flag);
    avlInsert(&head,11,&flag);
    avlInsert(&head,8,&flag);
    avlInsert(&head,4,&flag);
    avlInsert(&head,1,&flag);
    avlInsert(&head,12,&flag);
    avlInsert(&head,7,&flag);
    avlInsert(&head,2,&flag);
    avlInsert(&head,6,&flag);
    avlInsert(&head,10,&flag);
    avlInsert(&head,9,&flag);
    
    display(head);
    
    cout<<endl;
    
    
    system("pause");
    return 0;
}



void avlInsert(TreeNode **root,int x,bool *unbalanced){
     TreeNode *p;
     p=*root;
     
     
     if(p==NULL){
     *unbalanced=true;         
     TreeNode *s=new TreeNode;
     s->data=x;
     s->left=NULL;
     s->right=NULL;       
     s->bf=0;
     *root=s;
                 }
     else if(x<(p->data)){
          avlInsert(&((*root)->left),x,unbalanced);
          if(*unbalanced)
           switch(p->bf){
             case -1:p->bf=0;
                     *unbalanced=false;
                      break;
             case 0:p->bf=1;
                      break;
             case 1:leftRotation(p,unbalanced);                           
                    
                    }
          }
     else if(x>(p->data)){
        avlInsert(&((*root)->right),x,unbalanced);
        if(*unbalanced)
        switch(p->bf){
             case 1:p->bf=0;
                     *unbalanced=false;
                      break;
             case 0:p->bf=-1;
                      break;
             case -1:rightRotation(p,unbalanced);
                
               }
               
               }
     else{
           *unbalanced=false;
          cout<<"鍵值已經在樹中"<<endl;
          
          }
     
     }
     
     
void leftRotation(TreeNode *ptr,bool *unbalanced){
      TreeNode *grandChild,*child;
      child=ptr->left;
      if(child->bf==1){
        ptr->left=child->right;
        child->right=ptr;
        ptr->bf=0;
        ptr=child;
     
     }
     else{
          grandChild=child->right;
          child->right=grandChild->left;
          grandChild->left=child;
          ptr->left=grandChild->right;
          grandChild->right=ptr;
          switch(grandChild->bf){
             case 1:ptr->bf=-1;
                    child->bf=0;
                    break;
             case 0:ptr->bf=child->bf=0;break;
             case -1:ptr->bf=0;
                     child->bf=1;      
          }
          ptr=grandChild;
          
          }
     
     ptr->bf=0;
     *unbalanced=false;
     
     }
     
     
void rightRotation(TreeNode *ptr,bool *unbalanced){
      TreeNode *grandChild,*child;
      child=ptr->right;
      if(child->bf==-1){
        ptr->right=child->left;
        child->left=ptr;
        ptr->bf=0;
        ptr=child;
     
     }
     else{
          grandChild=child->left;
          child->left=grandChild->right;
          grandChild->right=child;
          ptr->right=grandChild->left;
          grandChild->left=ptr;
          switch(grandChild->bf){
             case 1:ptr->bf=0;
                    child->bf=-1;
                    break;
             case 0:ptr->bf=child->bf=0;break;
             case -1:ptr->bf=1;
                     child->bf=0;      
          }
          ptr=grandChild;
          
          }
     
     ptr->bf=0;
     *unbalanced=false;
     
     }
     
     
void display(TreeNode *ptr){
     
    if(ptr!=NULL){
            display(ptr->left);       
            cout<<ptr->data<<" ";
            display(ptr->right);
                   }

     }