04-树5 Root of AVL Tree

04-树5 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
1
2

Sample Output 1:

70
1

Sample Input 2:

7
88 70 61 96 120 90 65
1
2

Sample Output 2:

88
1

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C++ (g++)

思路：

int max(int a,int b)：

返回两个数的最大值

int getHeight(AVLTree t)：

如果是空树，返回； 否则返回左右子树的高度最大值

AVLTree SingleLeftRotation(AVLTree a)：

左旋 将a的左孩子给b 然后将b的右孩子给a的左孩子 a变成b的右孩子 求a的高度，求b的高度，返回b。

AVLTree SingleRightRotation(AVLTree a)：

右旋 将a的右孩子给b 然后将b的左孩子给a的右孩子 a变成b的左孩子 求a的高度，b的高度，返回b。

AVLTree DoubleLeftRightRotation(AVLTree a)：

左右旋 对a的左孩子求右旋然后返回给a的左孩子 返回a的右旋

AVLTree DoubleRightLeftRotation(AVLTree a)：

右左旋 对a的右孩子求左旋然后返回给a的右孩子 返回a的左旋

AVLTree Insert(int x,AVLTree t)：

如果树空，那先创建一个树开辟空间赋值等一系列操作 否则判断插入左树还是右树 左树：如果平衡因子为2，如果x小于要插入的左树根结点，
返回左旋值 否则返回左右旋值 右树：同理，x大于 返回右旋值 否则返回右左旋值 求树的高度 返回树

主函数：
输入结点个数，讲树初始化为空，逐个插入值，输出根结点的值。

AC代码：

#include
using namespace std;

typedef struct AVLNode* AVLTree;

struct AVLNode{
	int val;
	AVLTree Left;
	AVLTree Right;
	int height;
};

//求树的深度的函数
int max(int a,int b)
{
	return a>b?a:b;
}
int getHeight(AVLTree t)
{
	if(t) return max(getHeight(t->Left),getHeight(t->Right))+1;
	else return 0;
}
AVLTree SingleLeftRotation(AVLTree a)
{
	//左旋
	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),getHeight(b->Right))+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->Left))+1;
	b->height=max(getHeight(b->Left),getHeight(b->Right))+1;
	return b;
}
AVLTree DoubleLeftRightRotation(AVLTree a)
{
	//左右旋
	a->Left=SingleRightRotation(a->Left);
	return SingleLeftRotation(a);
}
AVLTree DoubleRightLeftRotation(AVLTree a)
{
	//右左旋
	a->Right=SingleLeftRotation(a->Right);
	return SingleRightRotation(a);
}
AVLTree Insert(int x,AVLTree t)
{
	//插入x到AVL中，并返回调整后的AVL树
	if(!t){
		t=(AVLTree)malloc(sizeof(struct AVLNode));
		t->val=x;
		t->height=0;
		t->Left=t->Right=NULL;
	}
	else if(x<t->val){
		t->Left=Insert(x,t->Left);
		if(getHeight(t->Left)-getHeight(t->Right)==2){
			if(x<t->Left->val) t=SingleLeftRotation(t);
			else t=DoubleLeftRightRotation(t);
		}
	}
	else if(x>t->val){
		t->Right=Insert(x,t->Right);
        if(getHeight(t->Right)-getHeight(t->Left)==2){
		if(x>t->Right->val) t=SingleRightRotation(t);
		else t=DoubleRightLeftRotation(t);
        }
	}
	t->height=max(getHeight(t->Left),getHeight(t->Right))+1;
	return t;
}

int main()
{
	int N;
	cin>>N;
	AVLTree avl=NULL;
	for(int i=0;i<N;i++){
		int t;
		cin>>t;
		avl=Insert(t,avl);
	}
	cout<<avl->val;
	return 0;
}
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