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

Output Specification:

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

Sample Input 1:

5
88 70 61 96 120

Sample Output 1:

Sample Input 2:

7
88 70 61 96 120 90 65

Sample Output 2:

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 struct Node{
 5      int v,height;
 6      Node* lchild,*rchild;
 7 }*root;
 8 
 9 Node* newNode(int v){
10     Node* node = new Node;
11     node -> v = v;
12     node -> lchild = node -> rchild = NULL;
13     node -> height = 1;
14     return node;
15 }
16 
17 int getHeight(Node* root){
18     if(root == NULL) return 0;
19     return root -> height;
20 }
21 
22 void updateHeight(Node* root){
23      root -> height = max(getHeight(root -> lchild),getHeight(root -> rchild))+1;
24 } 
25 
26 int getBalanceFactor(Node* root){
27     return getHeight(root -> lchild) - getHeight(root -> rchild);
28 }
29 
30 void R(Node* &root){
31     Node* temp =  root -> lchild;
32     root -> lchild = temp -> rchild;
33     temp -> rchild = root;
34     updateHeight(root);
35     updateHeight(temp);
36     root = temp;
37 }
38 void L(Node* &root){
39     Node* temp = root -> rchild;
40     root -> rchild = temp -> lchild;
41     temp -> lchild = root;
42     updateHeight(root);  //先更新root（子树）的高度
43     updateHeight(temp);
44     root = temp;
45 }
46 
47 void insert(Node* &root, int v){
48     if(root == NULL){
49         root = newNode(v);
50         return;
51     }
52     if(v < root -> v){
53         insert(root -> lchild,v);
54         updateHeight(root);
55         if(getBalanceFactor(root) == 2){
56             if(getBalanceFactor(root -> lchild) == 1){
57                 R(root);
58             }else if(getBalanceFactor(root -> lchild) == -1){
59                 L(root -> lchild);
60                 R(root);
61             }
62         }
63     }else{
64         insert(root -> rchild,v);
65         updateHeight(root);
66         if(getBalanceFactor(root) == -2){
67             if(getBalanceFactor(root -> rchild) == -1){
68                 L(root);
69             }else if(getBalanceFactor(root -> rchild) == 1){
70                 R(root -> rchild);
71                 L(root);
72                 
73             }
74         }
75     }
76 }
77 
78 int main(){
79     int n,v;
80     scanf("%d",&n);
81     for(int i = 0; i < n; i++){
82         scanf("%d",&v);
83         insert(root,v);
84     }
85     printf("%d",root -> v);
86     return 0;
87 }