二叉搜索树及AVL树详解
# 二叉搜索树
# 特点
二叉搜索树,有如下特点:
- 若它的左子树不为空,则左子树上所有的节点值都小于它的根节点值
- 若它的右子树不为空,则右子树上所有的节点值均大于它的根节点值
- 它的左右子树也分别可以充当为二叉查找树 例如
# 优点
二叉搜索树的优点:能够快速找到想要查找的值。 以查找数值为14的节点为例,由于二叉搜索树的特性,我们可以很快找到它,其查找过程如下:
- 和根节点9比较
- 由于14>9,所以14只可能存在于9的右子树中,因此查看右孩子13
- 由于14>13,所以继续查看13的右孩子15
- 由于14<15,所以14只可能存在于15的左孩子中,因此查找15的左孩子14
- 这时候发现14正是自己查找的值,于是查找结束 这种查找二叉树的方式正是二分查找的思想,可以很快的找到目标节点,查找所需的最大次数等于二叉搜索树的高度。 在插入的时候也是一样,通过一层一层的比较,最后找到适合自己的位置。
# 缺点
二叉搜索树具有什么缺陷呢? 假设初始的二叉搜索树只有三个节点:
然后我们按照顺序陆续插入节点4、3、2、1、0。插入之后的结构如下:
可以观察到,所有的节点都倾向于一边了,当出现这种情况时,二叉搜索树在查找的性能就大打折扣,几乎变成线性了。
# 平衡二叉搜索树(AVL树)
为了解决二叉搜索树的缺点,平衡二叉树被提出
# 特点
其具有如下特点:
- 具有二叉搜索树的全部特性
- 每个节点的左子树和右子树的高度差至多等于1 例如:下图就是一颗AVL树
而这张图中的则不是AVL树(节点右边的数字为节点的高度)
对于上图而言,节点9的左孩子高度为2,而右孩子高度为0,他们之间的差值超过了1。AVL树可以保证不会出现大量节点偏向一边的情况。
# 左旋和右旋
听起来AVL树还不错,但思考一下,如果我们要插入一个节点3,按照查找二叉树的特性,我们只能把3作为节点4的左子树插进去,可是插进去之后,又会破坏了AVL树的特性,那我们那该怎么弄? 在这之前,先了解一下左旋和右旋的概念。 右旋: 我们在进行节点插入的时候,可能会出现节点都倾向于左边的情况,例如
我们把这种倾向于左边的情况称之为左-左型。这个时候,我们就可以对节点9进行右旋操作,使它恢复平衡。
即:顺时针旋转两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子 再举个例子:
节点4和9高度相差大于1。由于是左孩子的高度较高,此时是左-左型,进行右旋。
这里要注意,节点4的右孩子成为了节点6的左孩子了 用一个动图示例:
左旋: 左旋和右旋一样,就是用来解决当大部分节点都偏向右边的时候,通过左旋来还原。例如:
我们把这种倾向于右边的情况称之为右-右型。
# 详细示例
以一个具体实例详细讲解: 假设二叉树初试状态如下:
我们逐渐插入如下数值:1,4,5,6,7,10,9,8
插入1
此时为左-左型,需要右旋调整
插入4
继续插入5
此时为右-右型,需要左旋调整
继续插入6
右-右型,需要进行左旋
继续插入7
右-右型,需要进行左旋
继续插入10
继续插入9
出现了这种情况应该怎么办呢?对于这种右-左型的情况,单单一次左旋或右旋是不行的,下面我们先说说如何处理这种情况。
这种类型我们把他成为右-左型,处理方式是先对节点10进行右旋把它变成右-右型
然后再进行左旋
所以对这种右-左型的,我们需要进行一次右旋再左旋,依次类推,左-右型需要进行一次左旋再右旋,与右-左型相反
回到刚才那道题
对它进行右旋再左旋
到此,节点的插入结束
# 总结
在插入的过程中,会出现一下四种情况破坏AVL树的特性,我们可以采取如下相应的旋转。
- 左-左型:做右旋。
- 右-右型:做左旋。
- 左-右型:先做左旋,后做右旋。
- 右-左型:先做右旋,再做左旋。
# 代码示例
//定义节点
class AvlNode {
int data;
AvlNode lchild;//左孩子
AvlNode rchild;//右孩子
int height;//记录节点的高度
}
//在这里定义各种操作
public class AVLTree{
//计算节点的高度
static int height(AvlNode T) {
if (T == null) {
return -1;
}else{
return T.height;
}
}
//左左型,右旋操作
static AvlNode R_Rotate(AvlNode K2) {
AvlNode K1;
//进行旋转
K1 = K2.lchild;
K2.lchild = K1.rchild;
K1.rchild = K2;
//重新计算节点的高度
K2.height = Math.max(height(K2.lchild), height(K2.rchild)) + 1;
K1.height = Math.max(height(K1.lchild), height(K1.rchild)) + 1;
return K1;
}
//进行左旋
static AvlNode L_Rotate(AvlNode K2) {
AvlNode K1;
K1 = K2.rchild;
K2.rchild = K1.lchild;
K1.lchild = K2;
//重新计算高度
K2.height = Math.max(height(K2.lchild), height(K2.rchild)) + 1;
K1.height = Math.max(height(K1.lchild), height(K1.rchild)) + 1;
return K1;
}
//左-右型,进行右旋,再左旋
static AvlNode R_L_Rotate(AvlNode K3) {
//先对其孩子进行左旋
K3.lchild = R_Rotate(K3.lchild);
//再进行右旋
return L_Rotate(K3);
}
//右-左型,先进行左旋,再右旋
static AvlNode L_R_Rotate(AvlNode K3) {
//先对孩子进行左旋
K3.rchild = L_Rotate(K3.rchild);
//在右旋
return R_Rotate(K3);
}
//插入数值操作
static AvlNode insert(int data, AvlNode T) {
if (T == null) {
T = new AvlNode();
T.data = data;
T.lchild = T.rchild = null;
} else if(data < T.data) {
//向左孩子递归插入
T.lchild = insert(data, T.lchild);
//进行调整操作
//如果左孩子的高度比右孩子大2
if (height(T.lchild) - height(T.rchild) == 2) {
//左-左型
if (data < T.lchild.data) {
T = R_Rotate(T);
} else {
//左-右型
T = R_L_Rotate(T);
}
}
} else if (data > T.data) {
T.rchild = insert(data, T.rchild);
//进行调整
//右孩子比左孩子高度大2
if(height(T.rchild) - height(T.lchild) == 2)
//右-右型
if (data > T.rchild.data) {
T = L_Rotate(T);
} else {
T = L_R_Rotate(T);
}
}
//否则,这个节点已经在书上存在了,我们什么也不做
//重新计算T的高度
T.height = Math.max(height(T.lchild), height(T.rchild)) + 1;
return T;
}
}
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
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
- 01
- SpringCache基本配置类05-16
- 03
- Rpamis-security-原理解析12-13