最近在学数据结构，感觉 AVL 比较难理解，遂写一篇博客来记录。
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
| struct AVL {
int value;
int height;
AVL *left;
AVL *right;
explicit AVL(int x) : value(x), height(1), left(nullptr), right(nullptr) {}
static int max(int a, int b) {
return a > b ? a : b;
}
static int getHeight(AVL *root) {
if (!root)
return 0;
return root->height;
}
static AVL *insert(AVL *root, int value) {
if (!root)
return new AVL(value);
if (value < root->value) {
root->left = insert(root->left, value);
if (getHeight(root->left) - getHeight(root->right) == 2) {
if (value < root->left->value) {
root = rotateLeft(root);
} else {
root = rotateLR(root);
}
}
}
if (value > root->value) {
root->right = insert(root->right, value);
if (getHeight(root->left) - getHeight(root->right) == -2) {
if (value > root->right->value) {
root = rotateRight(root);
} else {
root = rotateRL(root);
}
}
}
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
return root;
}
static AVL *rotateLeft(AVL *root) {
AVL *new_root = root->left;
root->left = new_root->right;
new_root->right = root;
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
new_root->height = max(getHeight(new_root->left), root->height) + 1;
return new_root;
}
static AVL *rotateRight(AVL *root) {
AVL *new_root = root->right;
root->right = new_root->left;
new_root->left = root;
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
new_root->height = max(getHeight(new_root->right), root->height) + 1;
return new_root;
}
static AVL *rotateLR(AVL *root) {
root->left = rotateRight(root->left);
return rotateLeft(root);
}
static AVL *rotateRL(AVL *root) {
root->right = rotateLeft(root->right);
return rotateRight(root);
}
};
|