pat1066. Root of AVL Tree (25)

1066. Root of AVL Tree (25)

时间限制

100 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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.

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<cstring>
 3 #include<iostream>
 4 #include<stack>
 5 #include<set>
 6 #include<map>
 7 #include<queue>
 8 #include<algorithm>
 9 using namespace std;
10 struct AVLtreenode{
11     int h,v;
12     AVLtreenode *l,*r;
13 };
14 #define max(a,b) (a>b?a:b)
15 int GetHeight(AVLtreenode *root){
16     if(!root){
17         return 0;
18     }
19     return root->h;
20 }
21 AVLtreenode* AVLRightRotation(AVLtreenode* root){
22     AVLtreenode* temp=root->r;
23     root->r=temp->l;
24     temp->l=root;
25     root->h=max(GetHeight(root->l),GetHeight(root->r))+1;
26     temp->h=max(GetHeight(temp->r),GetHeight(root))+1;
27     return temp;
28 }
29 AVLtreenode* AVLLeftRotation(AVLtreenode* root){
30     AVLtreenode* temp=root->l;
31     root->l=temp->r;
32     temp->r=root;
33     root->h=max(GetHeight(root->l),GetHeight(root->r))+1;
34     temp->h=max(GetHeight(temp->l),GetHeight(root))+1;
35     return temp;
36 }
37 AVLtreenode* AVLRightLeftRotation(AVLtreenode* root){
38     root->r=AVLLeftRotation(root->r);
39     root=AVLRightRotation(root);
40     return root;
41 }
42 AVLtreenode* AVLLeftRightRotation(AVLtreenode* root){
43     root->l=AVLRightRotation(root->l);
44     root=AVLLeftRotation(root);
45     return root;
46 }
47 AVLtreenode* AVLInsert(int num,AVLtreenode *root){
48     if(!root){
49 
50         //cout<<1<<endl;
51 
52         root=new AVLtreenode();
53         root->h=1;
54         root->l=root->r=NULL;
55         root->v=num;
56         return root;
57     }
58     //cout<<2<<endl;
59     if(root->v>num){//插入左子树
60         root->l=AVLInsert(num,root->l);
61         if(GetHeight(root->l)-GetHeight(root->r)==2){//需要左旋
62             if(root->l->v>num){//单左旋
63                 root=AVLLeftRotation(root);
64             }
65             else{//左右旋
66                 root=AVLLeftRightRotation(root);
67             }
68         }
69     }
70     else{
71         root->r=AVLInsert(num,root->r);
72         if(GetHeight(root->r)-GetHeight(root->l)==2){//
73             if(root->r->v<num){//
74                 root=AVLRightRotation(root);
75             }
76             else{//
77                 root=AVLRightLeftRotation(root);
78             }
79         }
80     }
81     root->h=max(GetHeight(root->l),GetHeight(root->r))+1;
82     return root;
83 }
84 int main(){
85     //freopen("D:\INPUT.txt","r",stdin);
86     int n;
87     scanf("%d",&n);
88     int i,num;
89     AVLtreenode *root=NULL;
90     for(i=0;i<n;i++){
91         scanf("%d",&num);
92 
93         //cout<<"i: "<<i<<endl;
94 
95         root=AVLInsert(num,root);
96     }
97     cout<<root->v<<endl;
98     return 0;
99 }