A1066. Root of AVL Tree (25)

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <iostream>
  4 #include <string.h>
  5 #include <math.h>
  6 #include <algorithm>
  7 #include <string>
  8 #include <stack> 
  9 #include <queue>
 10 using namespace std;
 11 const int maxn=110; 
 12 int n,m,s;
 13 struct node{
 14  node *left;
 15  node *right;
 16  int  v,height;//高度可理解为以该节点为根的树的层数 
 17 }*root,*null; 
 18 void init(){
 19     null=new node;
 20     null->height=0;
 21     root=null;//null为 高度为0 
 22 }
 23 node* newNode(int v)//设置新的节点 
 24 {
 25      node* t=new node();
 26      t->v=v;
 27      t->height=1;
 28     t->left=t->right=null;
 29      return t; 
 30 } 
 31 
 32 void getNewheight(node *root)
 33 {
 34     root->height=max(root->left->height,root->right->height)+1;
 35 }
 36 void L(node *&root)
 37 {
 38     node *tmp=root->right;
 39     root->right=tmp->left;
 40     tmp->left=root;
 41     getNewheight(root);
 42     getNewheight(tmp);
 43     root=tmp;
 44     
 45 }
 46 
 47 void R(node *&root)
 48 {
 49     node* tmp=root->left;
 50     root->left=tmp->right;
 51     tmp->right=root;
 52     getNewheight(root);
 53     getNewheight(tmp);
 54     root=tmp;
 55 }
 56 void insert(node *&root,int v)
 57 {
 58     if(root==null)
 59     {
 60      root=newNode(v);
 61      return;    
 62     } 
 63     if(v<root->v)
 64     {
 65         insert(root->left,v);
 66         getNewheight(root);
 67         if((root->left->height)-(root->right->height)==2)
 68         {
 69             //ll型 
 70             if((root->left->left->height)-(root->left->right->height)==1)
 71             {
 72                 R(root); 
 73             }else if((root->left->left->height)-(root->left->right->height)==-1)
 74             {
 75                 //lr
 76                 L(root->left);
 77                 R(root);
 78             }
 79         }
 80     }else
 81     {
 82         insert(root->right,v);
 83         getNewheight(root);
 84         if((root->left->height)-(root->right->height)==-2)
 85         {
 86             if((root->right->left->height)-(root->right->right->height)==1)
 87             {
 88                 R(root->right);
 89                 L(root);
 90             }else if((root->right->left->height)-(root->right->right->height)==-1)
 91             {
 92                 L(root);
 93             }
 94         }
 95     }
 96 }
 97 int main(){
 98     int n,v;
 99     init();
100     scanf("%d",&n);
101     for(int i=0;i<n;i++)
102     {
103         scanf("%d",&v);
104         insert(root,v);
105     }
106     printf("%d\n",root->v);
107     return 0;
108 }