平衡二叉树

发表于 | 分类于
字数统计: 885 word | 阅读时长 ≈ 3 min
平衡二叉树概念

平衡二叉树建立在二叉排序树的基础上，目的是使二叉排序树的平均查找长度更小，即让各结点的深度尽可能小，因此，树中每个结点的两棵子树的深度不要偏差太大。

平衡二叉树的递归定义：平衡二叉树是一棵二叉树，其可以为空，或满足如下2个性质：①左右子树深度之差的绝对值不大于1。②左右子树都是平衡二叉树。

平衡因子的概念：结点的平衡因子 = 结点的左子树深度 — 结点的右子树深度。若平衡因子的取值为-1、0或1时，该节点是平衡的，否则是不平衡的。

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
 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<algorithm>
using namespace std;
typedef int ElementType;
typedef struct AVLNode{
	ElementType Data;
	struct AVLNode* Left;
	struct AVLNode* Right;
}*AVLTree;
//计算树高
int GetHeight(AVLTree A){
	int HL, HR, MaxH;
	if (A == NULL)
		return 0;
	else{
		HL = GetHeight(A->Left);
		HR = GetHeight(A->Right);
		MaxH = max(HL, HR);
		return (MaxH + 1);
	}
}
//左单旋（左左型LL：需顺时针转,即插入的结点在不平衡结点的左孩子的左子树上，导致根节点的平衡因子由1变为2）
AVLTree SingleLeftRotation(AVLTree A){
	AVLTree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	return B;
}
//右单旋（右右型RR：需逆时针转,即插入的结点在不平衡结点的右孩子的右子树上，导致根节点的平衡因子由1变为2）
AVLTree SingleRightRotation(AVLTree A){
	AVLTree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	return B;
}
//左-右双旋（左右型LR：即插入的结点在不平衡结点的左孩子的右子树上，导致根节点的平衡因子由1变为2）
//可以这样想：先对不平衡结点的左子树 A->Left 进行右单璇（即逆时针来转，转完后不平衡结点及其左子树就变成了左左的形式了，只需再对 A  进行前面简单的左单璇即顺时针转即可）
AVLTree DoubleLeftRightRotation(AVLTree A){
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}
//右-左双旋（右左型RL：即插入的结点在不平衡结点的右孩子的左子树上，导致根节点的平衡因子由1变为2）
//可以这样想：先对不平衡结点的左子树 A->Left 进行右单璇（即逆时针来转，转完后不平衡结点及其左子树就变成了左左的形式了，只需再对 A  进行前面简单的左单璇即顺时针转即可）
AVLTree DoubleRightLeftRotation(AVLTree A){
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}
//插入结点
AVLTree Insert(AVLTree A, ElementType X){
	if (!A){
		A = (AVLTree)malloc(sizeof(struct AVLNode));
		A->Data = X;
		A->Left = A->Right = NULL;
	}
	else if (X<A->Data){
		A->Left = Insert(A->Left, X);
		if (GetHeight(A->Left) - GetHeight(A->Right) == 2)
		if (X<A->Left->Data)
			A = SingleLeftRotation(A);//左左型(LL)需要右旋转
		else
			A = DoubleLeftRightRotation(A);//左右型(LR)需要左右旋转
	}
	else if (X>A->Data){
		A->Right = Insert(A->Right, X);
		if (GetHeight(A->Left) - GetHeight(A->Right) == -2)
		if (X>A->Right->Data)
			A = SingleRightRotation(A);//右右型(RR)需要左旋转
		else
			A = DoubleRightLeftRotation(A);//右左型(RL)需要右左旋转
	}
	return A;
}
int main(){
	AVLTree A = NULL;
	int n, t;
	cin >> n;
	for (int i = 0; i<n; i++){
		cin >> t;
		A = Insert(A, t);
	}
	//输出了根节点
	cout << A->Data << endl;
	return 0;
}
0%