定义
AVL树是带有平衡条件的二叉查找树。它要求在AVL树中任何节点的两个子树的高度(高度是指节点到一片树叶的最长路径的长) 最大差别为1,如下图所示:
为什么有AVL树
大多数BST操作，例如查找，找最大，最小值，插入，删除等操作，基本上消耗O(h)时间，h是BST的高度。对于倾斜的二叉树，这些操作的成本可能会变成O(n)。
如果我们在每次插入和删除之后确保树的高度保持O(logn)，那么我们就可以保证所有这些操作的O(logn）的上界。而AVL树的高度总是O(logn)，其中n是树中节点的数量。
所以AVL树很好的解决了二叉搜索树退化成链表的问题，把插入，查找，删除的时间复杂度的最好情况和最坏情况都维持在O(logn)。
插入操作
当我们执行插入一个节点时，很可能会破坏AVL树的平衡特性，所以我们需要调整AVL树的结构，使其重新平衡，而调整的方式称之为旋转。
这里我们针对父节点的位置分为左-左，左-右，右-右，右-左这4类情况分析，而对左-左，右-右情况进行单旋转，也就是一次旋转，对左-右，右-左情况进行双旋转，两次旋转，最终恢复其平衡特性。
1.左-左情况
2.左-右情况
3.右-右情况
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
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
| package com.pjmike.tree.AVL;
public class AVLTree {
private Node root;
private int height(Node node) {
return node == null ? 0 : node.height;
}
private int max(int a, int b) {
return a > b ? a : b;
}
Node rightRotate(Node y) {
Node x = y.left;
Node T1 = x.right;
x.right = y;
y.left = T1;
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
return x;
}
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return y;
}
int getBalance(Node node) {
return node == null ? 0 : (height(node.left) - height(node.right));
}
Node insert(Node node, int val) {
if (node == null) {
return new Node(val);
}
if (val < node.val) {
node.left = insert(node.left, val);
} else if (val > node.val) {
node.right = insert(node.right, val);
} else {
return node;
}
node.height = 1 + max(height(node.left), height(node.right));
int balance = getBalance(node);
if (balance > 1 && val < node.left.val) {
return rightRotate(node);
}
if (balance < -1 && val > node.right.val) {
return leftRotate(node);
}
if (balance > 1 && val > node.left.val) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && val < node.right.val) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
avlTree.root = avlTree.insert(avlTree.root, 10);
avlTree.root = avlTree.insert(avlTree.root, 20);
avlTree.root = avlTree.insert(avlTree.root, 30);
avlTree.root = avlTree.insert(avlTree.root, 40);
avlTree.root = avlTree.insert(avlTree.root, 50);
avlTree.root = avlTree.insert(avlTree.root, 23);
avlTree.Preorder(avlTree.root);
}
void Preorder(Node node) {
if (node != null) {
System.out.println(node.val+" ");
Preorder(node.left);
Preorder(node.right);
}
}
}
class Node {
int val;
Node left;
Node right;
int height;
public Node(int val) {
this.val = val;
height = 1;
}
}
|
删除操作
对于二叉查找树，我们都知道它的删除要分三种情况：
- 删除的节点为叶子节点
- 删除的节点左子树或右子树有一个为空
- 删除的节点有两个子树
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
| Node deleteNode(Node root, int val) {
if (root == null) {
return root;
}
if (val < root.val) {
root.left = deleteNode(root.left, val);
} else if (val > root.val) {
root.right = deleteNode(root.right, val);
} else {
if (root.left != null && root.right != null) {
root.val = findMin(root.right);
root.right = deleteNode(root.right, root.val);
} else {
root = (root.left != null) ? root.left : root.right;
}
}
if (root == null) {
return root;
}
root.height = max(height(root.left), height(root.right)) + 1;
int balance = getBalance(root);
if (balance > 1 && getBalance(root.left) >= 0) {
return rightRotate(root);
}
if (balance > 1 && getBalance(root.left) < 0)
{
root.left = leftRotate(root.left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root.right) <= 0) {
return leftRotate(root);
}
if (balance < -1 && getBalance(root.right) > 0)
{
root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}
private int findMin(Node root) {
if (root.left == null) {
return root.val;
} else {
return findMin(root.left);
}
}
|
这里的删除后的平衡操作实际上与插入后的平衡操作是不一样的，删除可能造成树的一边比另一边浅的情况，还可能造成整个二叉树中有两个子树一样深的情况。
小结
显然，AVL树的优势在于插入，删除，查找操作的平均时间复杂度都为O(logn),但是它的缺陷是为了保持AVL树的平衡性质，动态插入和删除的代价也是很大的
参考资料