1066. Root of AVL Tree (25)

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

    

    

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print ythe root of the resulting AVL tree in one line.

588 70 61 96 120

70

788 70 61 96 120 90 65

88

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;struct Node{ int data; int height;//树高 Node *leftChild; Node *rightChild;};int getHeight(Node * t){ if(!t) return 0; else return t->height;}int MAX(int a,int b){ return a>b?a:b;}Node * singleLeftRotation(Node *A){ Node *B = A->leftChild; A->leftChild = B->rightChild; B->rightChild = A; A->height = MAX(getHeight(A->leftChild),getHeight(A->rightChild))+1; B->height = MAX(getHeight(B->leftChild),getHeight(B->rightChild))+1; return B;}Node * singleRightRotation(Node *A){ Node *B = A->rightChild; A->rightChild = B->leftChild; B->leftChild = A; A->height = MAX(getHeight(A->leftChild),getHeight(A->rightChild))+1; B->height = MAX(getHeight(B->leftChild),getHeight(B->rightChild))+1; return B;}Node *doubleLeftAndRightRotaion(Node *A){ A->leftChild = singleRightRotation(A->leftChild); return singleLeftRotation(A);}Node *doubleRightAndLeftRotaion(Node *A){ A->rightChild = singleLeftRotation(A->rightChild); return singleRightRotation(A);}Node *InsertAVLTree(int data,Node * treeNode){ if(!treeNode) { treeNode = new Node; treeNode->data = data; treeNode->height = 1; treeNode->leftChild = treeNode->rightChild = NULL; } else if(data
           
            data) //插入左子树 { treeNode->leftChild = InsertAVLTree(data,treeNode->leftChild); int leftHight = getHeight(treeNode->leftChild); int rightHight = getHeight(treeNode->rightChild); if(leftHight-rightHight==2) //需要左旋转 { if(data
            
             leftChild->data)//LL旋转 左单旋 { treeNode = singleLeftRotation(treeNode); } else //LR旋转，LR双旋 { treeNode = doubleLeftAndRightRotaion(treeNode); } } } else if(data>treeNode->data) //插入右子树 { treeNode->rightChild = InsertAVLTree(data,treeNode->rightChild); int leftHight = getHeight(treeNode->leftChild); int rightHight = getHeight(treeNode->rightChild); if(leftHight-rightHight==-2) //右需要旋转 { if(data>treeNode->rightChild->data)//RR旋转 右单旋 { treeNode = singleRightRotation(treeNode); } else //RL旋转，RL双旋 { treeNode = doubleRightAndLeftRotaion(treeNode); } } } treeNode->height = MAX(getHeight(treeNode->leftChild),getHeight(treeNode->rightChild))+1; return treeNode;}int main(){ int n,temp; scanf("%d",&n); Node *root=NULL; for(int i =0; i
             
              data); return 0;}