关于数据结构中平衡二叉树的介绍和代码实现
1 平衡二叉树
1.1 二叉排序树缺陷
当我们将数组
[1, 2, 3, 4, 5, 6, 7]转变成二叉排序树。会出现树变成链表的形式，虽然插入/删除速度改变不大，但搜索查询的速度大大降低了。
因此，提出了平衡二叉树的概念（AVL树）
1.2 平衡二叉树介绍
平衡二叉树： 也称为平衡二叉搜索树（Self-balancing binary search tree），又被称为AVL，可以保证查询效率较高
特点： 树的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是有个平衡二叉树
应用： 平衡二叉树的常用实现方法有：红黑树、AVL算法、替罪羊树、Treap、伸展树等
2 单旋转
2.1 单旋转介绍
单旋转： 分为左旋转和右旋转。当左子树比右子树的高度要低，且高度差>1，就使用左旋转将树转变成平衡二叉树，反之右旋转。
左旋转的目的是将根节点的右子节点作为新的根节点，右旋转则以左子节点作为新的根节点
- 下面以数组
[4, 3, 6, 5, 7 ,8]为例，使用单旋转（左旋转）将树转变成平衡二叉树 - （1）创建二叉排序树
- （2）创建一个跟根节点一样的节点
- 该节点的左子节点指向根节点的左子节点，其右子节点指向根节点的右子节点的左子节点
- （3）根节点的值更改为其右子节点的值
- （4）根节点右子节点指向右子节点的右子节点，根节点左子节点指向新创建的节点
- （5）整理后树的形状
2.2 代码
- （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
87
88
89
90
91
92
93
94
95
96
97
98public class AVLTree {
/**
* 子类 - 节点
*/
private class Node implements Comparable<Node>{
public int value;
public Node left;
public Node right;
public Node(int value) {
this(value, null, null);
}
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
public int compareTo(Node o) {
return value - o.value;
}
public String toString() {
return "Node{value = " + value + "}";
}
}
// -----------------------------------------------------------------------
//根节点
private Node root;
/**
* 添加数据
* @param value 值
*/
public void add(Integer value) {
Node node = new Node(value);
if (root == null) {
root = node;
return;
}
//循环寻找合适位置添加数据
Node temp = root;
while (true) {
if (temp.value < node.value) {
//向右寻找位置
if (temp.right != null) {
temp = temp.right;
}else {
temp.right = node;
break;
}
} else {
//向左寻找位置
if (temp.left != null) {
temp = temp.left;
}else {
temp.left = node;
break;
}
}
}
}
/**
* 中序遍历
*/
public void infixPrint() {
if (root == null) {
System.out.println("树为空！");
return;
}
infixRecursion(root);
}
/**
* 中序遍历 - 递归本体
* @param node 节点
*/
private void infixRecursion(Node node) {
if (node.left != null) {
infixRecursion(node.left);
}
System.out.println(node);
if (node.right != null) {
infixRecursion(node.right);
}
}
}
- （2）计算树高度方法
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/**
* 获取当前节点树的高度（递归）
* @param node 节点
* @return int
*/
public int getTreeHeight(Node node) {
//如果节点为null，不能存在树，为0
if (node == null) {
return 0;
}
//获取该节点左子树高度
int leftHeight;
if (node.left == null) {
leftHeight = 0;
} else {
//递归求左子树高度
leftHeight = getTreeHeight(node.left);
}
//获取该节点右子树高度
int rightHeight;
if (node.right == null) {
rightHeight = 0;
} else {
//递归求右子树高度
rightHeight = getTreeHeight(node.right);
}
//返回左右子树中的最大值+1（算上该节点，所以+1）作为树的整体高度
return Math.max(leftHeight, rightHeight) + 1;
}
- （3）左、右旋转方法
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/**
* 对当前节点进行左旋转
* @param node 节点
*/
private void leftRotate(Node node) {
//（1）创建一个与根节点一样的新节点
Node temp = new Node(node.value);
//（2）新节点左子节点指向根节点左子节点
temp.left = node.left;
//（3）新节点的右子节点指向根节点右子节点的左子节点
temp.right = node.right.left;
//（4）根节点的值 = 根节点右子节点的值
node.value = node.right.value;
//（5）根节点的左子节点指向新建的节点
node.left = temp;
//（6）根节点的右子节点指向右子节点的右子节点
node.right = node.right.right;
}
/**
* 对当前节点进行右旋转
* @param node 节点
*/
private void rightRotate(Node node) {
//跟左旋转大致相似，只有左右方向区别，就不再多写注释
Node temp = new Node(node.value);
temp.right = node.right;
temp.left = node.left.right;
node.value = node.left.value;
node.right = temp;
node.left = node.left.left;
}
- （4）递归平衡 二叉树方法
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/**
* 平衡二叉树
*/
public void balanceTree() {
balanceTreeRecursion(root);
}
/**
* 平衡二叉树 - 递归本体
* @param node 节点
*/
public void balanceTreeRecursion(Node node) {
//从下往上平衡，优先平衡子节点
if (node.left != null) {
balanceTreeRecursion(node.left);
}
if (node.right != null) {
balanceTreeRecursion(node.right);
}
balance(node);
}
/**
* 平衡本体方法
* @param node 节点
*/
private void balance(Node node) {
int leftHeight = getTreeHeight(node.left);
int rightHeight = getTreeHeight(node.right);
//两棵树高度差值 > 1，对树使用单旋转
if (Math.abs(leftHeight - rightHeight) > 1) {
//左子树小，使用左旋转
if (leftHeight < rightHeight) {
leftRotate(node);
}
//右子树小，使用右旋转
if (leftHeight > rightHeight) {
rightRotate(node);
}
}
}
3 双旋转
3.1 双旋转介绍
单旋转问题：在某些特定的情况下，一个节点不是平衡二叉树，但其子树都是属于平衡二叉树，此时对节点进行单旋转，但旋转过后仍然不是平衡二叉树，此时提出双旋转
双旋转：顾名思义，就是旋转两次的意思。例上图要对根节点使用右旋转，则需要判断一下左子树。左子树满足：左子树的左子树的高度 < 左子树的右子树高度，则满足双旋转条件。在对根节点进行右旋转前，先对根节点的左子树进行左旋转，来降低树的高度。同理使用左旋转前，先判断右子树是否满足条件
3.2 代码
- 双旋转就是在原来平衡节点方法上，多做一层判断，来对比子节点的左右子树高度，进而判断是否要使用双旋转
- 更新平衡节点方法
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/**
* 平衡节点方法
* @param node 节点
*/
private void balance(Node node) {
int leftHeight = getTreeHeight(node.left);
int rightHeight = getTreeHeight(node.right);
//两棵树高度差值 > 1，对树使用单旋转
int childLeftHeight; //子节点左右子树高度
int childRightHeight;
if (Math.abs(leftHeight - rightHeight) > 1) {
//左子树小，使用左旋转
if (leftHeight < rightHeight) {
childLeftHeight = getTreeHeight(node.right.left);
childRightHeight = getTreeHeight(node.right.right);
//判断是否要双旋转
if (childLeftHeight > childRightHeight) {
rightRotate(node.right);
}
leftRotate(node);
}
//右子树小，使用右旋转
if (leftHeight > rightHeight) {
childLeftHeight = getTreeHeight(node.left.left);
childRightHeight = getTreeHeight(node.left.right);
//判断是否要双旋转
if (childLeftHeight < childRightHeight) {
leftRotate(node.left);
}
rightRotate(node);
}
}
}
4 总代码
- （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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236public class AVLTree {
/**
* 子类 - 节点
*/
private class Node implements Comparable<Node>{
public int value;
public Node left;
public Node right;
public Node(int value) {
this(value, null, null);
}
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
public int compareTo(Node o) {
return value - o.value;
}
public String toString() {
return "Node{value = " + value + "}";
}
}
// -----------------------------------------------------------------------
//根节点
private Node root;
/**
* 添加数据
* @param value 值
*/
public void add(Integer value) {
Node node = new Node(value);
if (root == null) {
root = node;
return;
}
//循环寻找合适位置添加数据
Node temp = root;
while (true) {
if (temp.value < node.value) {
//向右寻找位置
if (temp.right != null) {
temp = temp.right;
}else {
temp.right = node;
break;
}
} else {
//向左寻找位置
if (temp.left != null) {
temp = temp.left;
}else {
temp.left = node;
break;
}
}
}
//每添加一个数据，就平衡一次二叉树
balanceTree();
}
/**
* 获取当前节点树的高度（递归）
* @param node 节点
* @return int
*/
public int getTreeHeight(Node node) {
//如果节点为null，不存在树，为0
if (node == null) {
return 0;
}
//获取该节点左子树高度
int leftHeight;
if (node.left == null) {
leftHeight = 0;
} else {
//递归求左子树高度
leftHeight = getTreeHeight(node.left);
}
//获取该节点右子树高度
int rightHeight;
if (node.right == null) {
rightHeight = 0;
} else {
//递归求右子树高度
rightHeight = getTreeHeight(node.right);
}
//返回左右子树中的最大值+1（算上该节点，所以+1）作为树的整体高度
return Math.max(leftHeight, rightHeight) + 1;
}
/**
* 平衡二叉树
*/
public void balanceTree() {
balanceTreeRecursion(root);
}
/**
* 平衡二叉树 - 递归本体
* @param node 节点
*/
public void balanceTreeRecursion(Node node) {
//从下往上平衡，优先平衡子节点
if (node.left != null) {
balanceTreeRecursion(node.left);
}
if (node.right != null) {
balanceTreeRecursion(node.right);
}
balance(node);
}
/**
* 平衡节点方法
* @param node 节点
*/
private void balance(Node node) {
int leftHeight = getTreeHeight(node.left);
int rightHeight = getTreeHeight(node.right);
//两棵树高度差值 > 1，对树使用单旋转
int childLeftHeight;
int childRightHeight;
if (Math.abs(leftHeight - rightHeight) > 1) {
//左子树小，使用左旋转
if (leftHeight < rightHeight) {
childLeftHeight = getTreeHeight(node.right.left);
childRightHeight = getTreeHeight(node.right.right);
//判断是否要双旋转
if (childLeftHeight > childRightHeight) {
rightRotate(node.right);
}
leftRotate(node);
}
//右子树小，使用右旋转
if (leftHeight > rightHeight) {
childLeftHeight = getTreeHeight(node.left.left);
childRightHeight = getTreeHeight(node.left.right);
//判断是否要双旋转
if (childLeftHeight < childRightHeight) {
leftRotate(node.left);
}
rightRotate(node);
}
}
}
/**
* 对当前节点进行左旋转
* @param node 节点
*/
private void leftRotate(Node node) {
//（1）创建一个与根节点一样的新节点
Node temp = new Node(node.value);
//（2）新节点左子节点指向根节点左子节点
temp.left = node.left;
//（3）新节点的右子节点指向根节点右子节点的左子节点
temp.right = node.right.left;
//（4）根节点的值 = 根节点右子节点的值
node.value = node.right.value;
//（5）根节点的左子节点指向新建的节点
node.left = temp;
//（6）根节点的右子节点指向右子节点的右子节点
node.right = node.right.right;
}
/**
* 对当前节点进行右旋转
* @param node 节点
*/
private void rightRotate(Node node) {
//跟左旋转大致相似，只有左右方向区别，就不再多写注释
Node temp = new Node(node.value);
temp.right = node.right;
temp.left = node.left.right;
node.value = node.left.value;
node.right = temp;
node.left = node.left.left;
}
/**
*中序遍历
*/
public void infixPrint() {
if (root == null) {
System.out.println("树为空！");
return;
}
infixRecursion(root);
}
/**
* 中序遍历 - 递归本体
* @param node 节点
*/
private void infixRecursion(Node node) {
if (node.left != null) {
infixRecursion(node.left);
}
System.out.println(node);
if (node.right != null) {
infixRecursion(node.right);
}
}
}
- （2）测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void avlTreeTest() {
//创建平衡二叉树
AVLTree avlTree = new AVLTree();
//循环遍历添加数据
int[] arr = new int[]{1, 2, 3, 4, 5 ,6};
for (int i : arr) {
avlTree.add(i);
}
//中序遍历查看是否按顺序
avlTree.infixPrint();
System.out.println("/------------------------------------/");
//为了明显效果，再写了个前序遍历，查看树结构是否真发生变化（代码没有前序，自己按需自行添加）
avlTree.prePrint();
}
