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 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:

88

题目大意： 给出一串序列， 建立一颗平衡二叉树， 理解了平衡二叉树的构造过程 该题就比较简单了
给出两种建立的方法， 第一种是最先接触到的建立方法， 第二种是推荐的建立方法

 1 #include<iostream>
 2 using namespace std;
 3 class node{
 4 public:
 5   int val;
 6   node *left, *right;
 7   node(){left=NULL; right=NULL;}
 8 };
 9 
10 node* rightRoate(node* root){
11   node* temp=root->left;
12   root->left=temp->right;
13   temp->right=root;
14   return temp;
15 }
16 
17 node* leftRoate(node* root){
18   node* temp=root->right;
19   root->right=temp->left;
20   temp->left=root;
21   return temp;
22 }
23 
24 node* leftRightRoate(node* root){
25    root->left=leftRoate(root->left);
26    return rightRoate(root);
27 }
28 
29 
30 
31 node* rightLeftRoate(node* root){
32    root->right=rightRoate(root->right);
33    return leftRoate(root);
34 }
35 
36 int getHeight(node* root){
37   if(root==NULL) return 0;
38   int l=getHeight(root->left), r=getHeight(root->right);
39   return l>r? (l+1):(r+1);
40 }
41 
42 node* insert(node* root, int val){
43   if(root==NULL){
44     node *newnode=new node();
45     newnode->val=val;
46     return newnode;
47   }
48   if(root->val>val){ 
49     root->left=insert(root->left, val);
50     if(getHeight(root->left)-getHeight(root->right)>1){
51       if(getHeight(root->left->left)>getHeight(root->left->right)) root=rightRoate(root);
52       else root=leftRightRoate(root);
53     }
54   }
55   else {
56     root->right=insert(root->right, val);
57     if(getHeight(root->right)-getHeight(root->left)>1){
58       if(getHeight(root->right->right)>getHeight(root->right->left)) root=leftRoate(root);
59       else root=rightLeftRoate(root);
60     }
61   }
62   return root;
63 }
64 
65 
66  
67 int main(){
68   node *root=NULL;
69   int i, n, t;
70   scanf("%d", &n);
71   for(i=0; i<n; i++){
72     scanf("%d", &t);
73     root=insert(root, t);
74   }
75   printf("%d
", root->val);
76   return 0;
77 }

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 struct Node{
 5   int val, height;
 6   Node *left, *right;
 7   Node(int v){val = v; left=right=NULL; height=1;}
 8 };
 9 
10 int getHeight(Node *root){
11   return root==NULL ? 0 : root->height;
12 }
13 
14 void updateHeight(Node *root){
15   int l = getHeight(root->left), r = getHeight(root->right);
16   root->height = l>r ? l+1 : r+1;
17 }
18 
19 int getBalanceFactor(Node* root){
20   return getHeight(root->left) - getHeight(root->right);
21 }
22 
23 void leftRoate(Node* &root){
24   Node *temp = root->right;
25   root->right = temp->left;
26   temp->left = root;
27   updateHeight(root);
28   updateHeight(temp);
29   root = temp;
30 }
31 
32 void rightRoate(Node* &root){
33   Node *temp = root->left;
34   root->left = temp->right;
35   temp->right = root;
36   updateHeight(root);
37   updateHeight(temp);
38   root = temp;
39 }
40 
41 void insertNode(Node* &root, int val){
42   if(root==NULL){
43     root = new Node(val);
44     return;
45   }
46   if(val<root->val){
47     insertNode(root->left, val);
48     updateHeight(root);//插入新节点后不要忘记更新根节点的高度
49     if(getBalanceFactor(root)==2){//调节不平衡的二叉树
50       if(getBalanceFactor(root->left)==1) rightRoate(root);
51       else{
52         leftRoate(root->left);
53         rightRoate(root);
54       }
55     }
56   }else{
57     insertNode(root->right, val);
58     updateHeight(root);
59     if(getBalanceFactor(root)==-2){
60       if(getBalanceFactor(root->right)==-1) leftRoate(root);
61       else{
62         rightRoate(root->right);
63         leftRoate(root);
64       }
65     }
66   }
67 }
68 int main(){
69   int n, i;
70   scanf("%d", &n);
71   Node *root=NULL;
72   for(i=0; i<n; i++){
73     int val;
74     scanf("%d", &val);
75     insertNode(root, val);
76   }
77   printf("%d
", root->val);
78   return 0;
79 }

1066 Root of AVL Tree (25)

相关推荐