AVL树

什么是AVL树

AVL树是最早的自平衡二叉树。他通过标注节点的高度,计算节点的平衡因子,通过左右旋转保持树结构的平衡。
平衡二叉树:对于任意一个节点,左子树和右子树的高度差不能为超过1。平衡二叉树的高度和节点数量之间的关系也是O(logn)的

具体实现(注意看注释)

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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
package AVLTree;

import SetBasicsAndBSTSet.FileOperation;

import java.util.ArrayList;

/**
* @ Description:AVL树的实现
* @ Date: Created in 15:27 23/07/2018
* @ Author: Anthony_Duan
*/
public class AVLTree<K extends Comparable<K>, V> {

private class Node {
public K key;
public V value;
public Node left, right;
public int height;

public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
height = 1;
}
}

private Node root;
private int size;

public AVLTree() {
root = null;
size = 0;
}

public int getSize() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

// 判断该二叉树是否是一棵二分搜索树
public boolean isBST() {

ArrayList<K> keys = new ArrayList<>();
inOrder(root, keys);
for (int i = 1; i < keys.size(); i++) {
if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
return false;
}
}
return true;
}

//中序遍历
private void inOrder(Node node, ArrayList<K> keys) {

if (node == null) {
return;
}

inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}

// 判断该二叉树是否是一棵平衡二叉树
public boolean isBalanced() {
return isBalanced(root);
}

// 判断以Node为根的二叉树是否是一棵平衡二叉树,递归算法
private boolean isBalanced(Node node) {

if (node == null) {
return true;
}

int balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) {
return false;
}
return isBalanced(node.left) && isBalanced(node.right);
}

// 获得节点node的高度
private int getHeight(Node node) {
if (node == null) {
return 0;
}
return node.height;
}

// 获得节点node的平衡因子
private int getBalanceFactor(Node node) {
if (node == null) {
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}

// 对节点y进行向右旋转操作,返回旋转后新的根节点x
// y x
// / \ / \
// x T4 向右旋转 (y) z y
// / \ - - - - - - - -> / \ / \
// z T3 T1 T2 T3 T4
// / \
// T1 T2
private Node rightRotate(Node y) {
Node x = y.left;
Node T3 = x.right;

// 向右旋转过程
x.right = y;
y.left = T3;

// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

return x;
}

// 对节点y进行向左旋转操作,返回旋转后新的根节点x
// y x
// / \ / \
// T1 x 向左旋转 (y) y z
// / \ - - - - - - - -> / \ / \
// T2 z T1 T2 T3 T4
// / \
// T3 T4
private Node leftRotate(Node y) {
Node x = y.right;
Node T2 = x.left;

// 向左旋转过程
x.left = y;
y.right = T2;

// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

return x;
}

// 向二分搜索树中添加新的元素(key, value)
public void add(K key, V value) {
root = add(root, key, value);
}

// 向以node为根的二分搜索树中插入元素(key, value),递归算法
// 返回插入新节点后二分搜索树的根
private Node add(Node node, K key, V value) {

if (node == null) {
size++;
return new Node(key, value);
}

if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, value);
} else if (key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
{
node.value = value;
}

// 更新height
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

// 计算平衡因子
int balanceFactor = getBalanceFactor(node);

// 平衡维护
// LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
}

// RR
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
return leftRotate(node);
}

// LR
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}

// RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}

return node;
}

// 返回以node为根节点的二分搜索树中,key所在的节点
private Node getNode(Node node, K key) {

if (node == null) {
return null;
}

if (key.equals(node.key)) {
return node;
} else if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else // if(key.compareTo(node.key) > 0)
{
return getNode(node.right, key);
}
}

public boolean contains(K key) {
return getNode(root, key) != null;
}

public V get(K key) {

Node node = getNode(root, key);
return node == null ? null : node.value;
}

public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null) {
throw new IllegalArgumentException(key + " doesn't exist!");
}

node.value = newValue;
}

// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}

// 从二分搜索树中删除键为key的节点
public V remove(K key) {

Node node = getNode(root, key);
if (node != null) {
root = remove(root, key);
return node.value;
}
return null;
}

private Node remove(Node node, K key) {

if (node == null) {
return null;
}

Node retNode;
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
// return node;
retNode = node;
} else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
// return node;
retNode = node;
} else { // key.compareTo(node.key) == 0

// 待删除节点左子树为空的情况
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
// return rightNode;
retNode = rightNode;
}

// 待删除节点右子树为空的情况
else if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
// return leftNode;
retNode = leftNode;
}

// 待删除节点左右子树均不为空的情况
else {
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
//successor.right = removeMin(node.right);
successor.right = remove(node.right, successor.key);
successor.left = node.left;

node.left = node.right = null;

// return successor;
retNode = successor;
}
}

if (retNode == null) {
return null;
}

// 更新height
retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));

// 计算平衡因子
int balanceFactor = getBalanceFactor(retNode);

// 平衡维护
// LL
if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
return rightRotate(retNode);
}

// RR
if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
return leftRotate(retNode);
}

// LR
if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}

// RL
if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}

return retNode;
}

public static void main(String[] args) {

System.out.println("Pride and Prejudice");

ArrayList<String> words = new ArrayList<>();
if (FileOperation.readFile("/Users/duanjiaxing/IdeaProjects/Data-Structure/data-structure/src/AVLTree/pride-and-prejudice.txt", words)) {
System.out.println("Total words: " + words.size());

AVLTree<String, Integer> map = new AVLTree<String, Integer>();
for (String word : words) {
if (map.contains(word)) {
map.set(word, map.get(word) + 1);
} else {
map.add(word, 1);
}
}

System.out.println("Total different words: " + map.getSize());
System.out.println("Frequency of PRIDE: " + map.get("pride"));
System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));

System.out.println("is BST : " + map.isBST());
System.out.println("is Balanced : " + map.isBalanced());

for (String word : words) {
map.remove(word);
if (!map.isBST() || !map.isBalanced()) {
throw new RuntimeException();
}
}
}

System.out.println();
}
}
-------------End Of This ArticleThank You For Reading-------------