前言

在准备考研复习专业课数据结构,所以我在mooc平台上找了浙江大学的数据结构课程重新学习,感觉老师留的课后题都很有趣,所以想记录下自己的学习过程。

题目:

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.

F1.jpg

F2.jpg

F3.jpg

F4.jpg

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:

1
2
5
88 70 61 96 120

Sample Output 1:

1
70

Sample Input 2:

1
2
7
88 70 61 96 120 90 65

Sample Output 2:

1
88

题解

题目分析

​ 这道题目的要求是给出一个建立二叉平衡树的插入序列,然后要求输出建立好后平衡二叉树的头节点。

​ 首先建立平衡二叉树的结构,然后插入节点,插入结点之后要判断是否破坏了平衡二叉树的平衡因子,如果破坏了就需要调整为平衡的状态。

​ 有四种情况需要调整,分别是 左左旋转 、右右旋转 、左右旋转 、 右左旋转。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<cstdio>
#include<cstdlib>
//定义平衡二叉树结构
struct AVL_Node {
int data; //节点数据
int height; //树高
AVL_Node* left; //左子树
AVL_Node* right; //右子树
};
typedef AVL_Node *AVLTree;

AVLTree avl = NULL;

//取最大值
int Max(int a,int b){
return a > b ? a : b;
}

//获取树的高度
int GetHeight(AVLTree avl){
if(!avl)
return 0;
else
return Max(GetHeight(avl->left), GetHeight(avl->right)) + 1;
}

AVLTree SingleLeftRotation ( AVLTree A ){
/* 注意:A必须有一个左子结点B */
/* 将A与B做左单旋,更新A与B的高度,返回新的根结点B */

AVLTree B = A->left;
A->left = B->right;
B->right = A;
A->height = Max( GetHeight(A->left), GetHeight(A->right) ) + 1;
B->height = Max( GetHeight(B->left), A->height ) + 1;

return B;
}

AVLTree SingleRightRotation ( AVLTree A ){
AVLTree B = A->right;
A->right = B->left;
B->left = A;
A->height = Max( GetHeight(A->left), GetHeight(A->right) ) + 1;
B->height = Max( GetHeight(B->left), A->height ) + 1;

return B;
}

AVLTree DoubleLeftRightRotation ( AVLTree A ){
/* 注意:A必须有一个左子结点B,且B必须有一个右子结点C */
/* 将A、B与C做两次单旋,返回新的根结点C */

/* 将B与C做右单旋,C被返回 */
A->left = SingleRightRotation(A->left);
/* 将A与C做左单旋,C被返回 */
return SingleLeftRotation(A);
}

AVLTree DoubleRightLeftRotation ( AVLTree A ){
A->right = SingleLeftRotation(A->right);
return SingleRightRotation(A);
}

//给平衡二叉树插入结点
AVLTree InsertAVLNode(AVLTree avl,int x){
if(avl==NULL){
avl = (AVLTree)malloc(sizeof(struct AVL_Node));
avl->data = x;
avl->left = avl->right = NULL;
avl->height = 1;
}
else if(x < avl->data){
/* 插入T的左子树 */
avl->left = InsertAVLNode( avl->left, x);
/* 如果需要左旋 */
if ( GetHeight(avl->left)-GetHeight(avl->right) == 2 )
if ( x < avl->left->data )
avl = SingleLeftRotation(avl); /* 左单旋 */
else
avl = DoubleLeftRightRotation(avl); /* 左-右双旋 */
}
else if(x > avl->data){
/* 插入T的右子树 */
avl->right= InsertAVLNode( avl->right, x);
/* 如果需要右旋 */
if ( GetHeight(avl->right)-GetHeight(avl->left) == 2 )
if ( x > avl->right->data )
avl = SingleRightRotation(avl); /* 右单旋 */
else
avl = DoubleRightLeftRotation(avl); /* 右-左双旋 */
}

avl->height = Max(GetHeight(avl->left), GetHeight(avl->right)) + 1;
return avl;
}


int main(){
int n, x;
scanf("%d", &n);
for (int i = 0; i < n;i++){
scanf("%d", &x);
avl = InsertAVLNode(avl, x);
}
printf("%d", avl->data);
return 0;
}