A1066. Root of AVL Tree

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<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef struct NODE{
 6     struct NODE* lchild, *rchild;
 7     int key;
 8     int height;
 9 }node;
10 int getHeight(node* root){
11     if(root == NULL)
12         return 0;
13     else return root->height;
14 }
15 void updateHeight(node *root){
16     root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
17 }
18 void L(node* &root){
19     node* temp = root;
20     root = root->rchild;
21     updateHeight(root);
22     temp->rchild = root->lchild;
23     root->lchild = temp;
24     updateHeight(temp);
25 }
26 void R(node* &root){
27     node *temp = root;
28     root = root->lchild;
29     updateHeight(root);
30     temp->lchild = root->rchild;
31     root->rchild = temp;
32     updateHeight(temp);
33 }
34 void insert(node* &root, int key){
35     if(root == NULL){   //此处可获得插入节点的信息
36         node* temp = new node;
37         temp->lchild = NULL;
38         temp->rchild = NULL;
39         temp->key = key;
40         temp->height = 1;
41         root = temp;
42         return;
43     }
44     if(key < root->key){   //此处可获得距离插入节点最近得父节点得信息
45         insert(root->lchild, key);
46         updateHeight(root);
47         if(abs(getHeight(root->lchild) - getHeight(root->rchild)) == 2){
48             if(getHeight(root->lchild->lchild) > getHeight(root->lchild->rchild)){
49                 R(root);
50             }else{
51                 L(root->lchild);
52                 R(root);
53             }    
54         }
55     }else{
56         insert(root->rchild, key);
57         updateHeight(root);
58         if(abs(getHeight(root->lchild) - getHeight(root->rchild)) == 2){
59             if(getHeight(root->rchild->rchild) > getHeight(root->rchild->lchild)){
60                 L(root);
61             }else{
62                 R(root->rchild);
63                 L(root);
64             }    
65         }
66     }
67 }
68 int main(){
69     int N, key;
70     scanf("%d", &N);
71     node* root = NULL;
72     for(int i = 0; i < N; i++){
73         scanf("%d", &key);
74         insert(root, key);
75     }
76     printf("%d", root->key);
77     cin >> N;
78     return 0;
79 }

View Code

总结：

1、题意：按照题目给出的key的顺序，建立一个平衡二叉搜索树。

2、二叉搜索树的几个关键地方：

每个节点使用height来记录自己的高度，叶节点高度为1;
获得某个节点高度的函数，主要是由于在获取平衡因子时，有些树的子树是空的，需要返回0，为避免访问空指针，获取节点高度都要通过该函数而非height字段。
更新当前节点的高度，应更新为左右子树的最大高度+1。
左旋与右旋：一定是三步操作而不是两步（不要忘记新的root的原子树）。注意更新节点高度的先后顺序。
插入与建树：插入操作基于二叉搜索树的插入。在root = NULL时进行新建节点并插入，在此处可以获得插入节点的信息。而在递归插入语句处，可以获取插入A节点之后距离A节点最近的父节点。因此在递归插入结束后就要对该节点进行更新高度，并在此处更新完之后检查平衡因子，并做LL、LR、RR、RL旋转。

3、对rootA的左子树做插入，导致rootA的左子树与右子树高度差为2，则对以rootA为根的树旋转。

4、调试的时候，可以取很少的几个节点，然后画出调试过程中树的形状。