15
面试官提到的 AVL 树，到底是个啥
source link: http://developer.51cto.com/art/202003/612059.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
了解过平衡二叉树的朋友们，对它一定有印象，今天阿粉就与大家一起深入了解一下AVL树!
一、摘要
在上篇文章，我们详细的介绍了二叉树的算法以及代码实践，我们知道不同的二叉树形态结构，对查询效率也会有很大的影响，尤其是当树的形态结构变成一个链条结构的时候，查询最后一个元素的效率极底，如何解决这个问题呢?
关键在于如何最大限度的减小树的深度，从而提高查询效率，正是基于这一点，平衡二叉查找树出现了!
平衡二叉查找树，算法由Adel'son-Vel'skii和 Landis两位大神发明，同时也俗称AVL 树，来自两位大神的姓名缩写，特性如下：
- 它的左子树和右子树都是平衡二叉树;
- 且它的左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1;
简单的说，就是为了保证平衡，当前节点的左子树、右子树的高度差不超过1!
废话也不多说了，直奔主题，算法思路如下!
二、算法思路
平衡二叉查找树的查找思路，与二叉树是一样，每次查询的时候对半分，只查询一部分，以达到提供效率的目的，插入、删除也一样，最大的不同点：每次插入或者删除之后，需要计算节点高度，然后按需进行调整!
如何调整呢?主要方法有：左旋转、右旋转!
下面我们分别来分析一下插入、删除的场景调整。
2.1、插入场景
我们来分析一下插入的场景，如下：
场景一
当我们在40的左边或者右边插入的时候，也就是50的左边，只需绕80进行右旋转，即可达到树高度差不超过1!
场景二
当我们在60的左边或者右边插入的时候，也就是50的右边，需要进行两次旋转，先会绕50左旋转一次，再绕80右旋转一次，即可达到树高度差不超过1!
场景三
当我们在120的左边或者右边插入的时候，也就是90的右边，只需绕80进行左旋转，即可达到树高度差不超过1!
场景四
当我们在85的左边或者右边插入的时候，也就是90的左边，需要进行两次旋转，先会绕90右旋转一次，再绕80左旋转一次，即可达到树高度差不超过1!
总结
对于插入这种操作，总共其实只有这四种类型的插入，即：单次左旋转、单次右旋转、左旋转-右旋转、右旋转-左旋转，总结如下：
- 当插入节点位于需要旋转节点的左节点的左子树时，只需右旋转;
- 当插入节点位于需要旋转节点的左节点的右子树时，需要左旋转-右旋转;
- 当插入节点位于需要旋转节点的右节点的右子树时，只需左旋转;
- 当插入节点位于需要旋转节点的右节点的左子树时，需要右旋转-左旋转;
2.2、删除场景
接下来，我们分析一下删除场景!
其实，删除场景跟二叉树的删除思路是一样的，不同的是需要调整，删除的节点所在树，需要层层判断节点的高度差是否大于1，如果大于1，就进行左旋转或者右旋转!
场景一
当删除的节点，只有左子树时，直接将左子树转移到上层即可!
场景二
当删除的节点，只有右子树时，直接将右子树转移到上层即可!
场景三
当删除的节点，有左、右子树时，因为当前节点的左子树的最末端的右子树或者当前节点的右子树的最末端的左子树，最接近当前节点，找到其中任意一个，然后将其内容替换并移除最末端节点，即可实现删除!
总结
第三种场景稍微复杂了一些，但基本都是这么一个套路，与二叉树不同的是，删除之后需要判断树高，对超过1的进行调整，类似上面插入的左旋转、右旋转操作!
三、代码实践
接下来，我们从代码层面来定义一下树的实体结构，如下：
1public class AVLNode<E extends Comparable<E>> {
2
3 /**节点关键字*/
4 E key;
5
6 /**当前节点树高*/
7 int height;
8
9 /**当前节点的左子节点*/
10 AVLNode<E> lChild = null;
11
12 /**当前节点的右子节点*/
13 AVLNode<E> rChild = null;
14
15 public AVLNode(E key) {
16 this.key = key;
17 }
18
19 @Override
20 public String toString() {
21 return "AVLNode{" +
22 "key=" + key +
23 ", height=" + height +
24 ", lChild=" + lChild +
25 ", rChild=" + rChild +
26 '}';
27 }
28}
我们创建一个算法类AVLSolution，完整实现如下：
1public class AVLSolution<E extends Comparable<E>> {
2
3 /**定义根节点*/
4 public AVLNode<E> root = null;
5
6 /**
7 * 插入
8 * @param key
9 */
10 public void insert(E key){
11 System.out.println("插入[" + key + "]:");
12 root = insertAVL(key,root);
13 }
14
15 private AVLNode insertAVL(E key, AVLNode<E> node){
16 if(node == null){
17 return new AVLNode<E>(key);
18 }
19 //左子树搜索
20 if(key.compareTo(node.key) < 0){
21 //当前节点左子树不为空,继续递归向下搜索
22 node.lChild = insertAVL(key,node.lChild);
23 //出现不平衡，只会是左子树比右子树高，大于1的时候，就进行调整
24 if(getHeight(node.lChild) - getHeight(node.rChild) == 2){
25 if(key.compareTo(node.lChild.key) < 0){
26 //如果插入的节点位于当前节点的左节点的左子树，进行单次右旋转
27 node = rotateRight(node);
28 }else{
29 //如果插入的节点位于当前节点的左节点的右子树，先左旋转再右旋转
30 node = rotateLeftRight(node);
31 }
32 }
33 }else if(key.compareTo(node.key) > 0){
34 //当前节点右子树不为空,继续递归向下搜索
35 node.rChild = insertAVL(key,node.rChild);
36 //出现不平衡，只会是右子树比左子树高，大于1的时候，就进行调整
37 if(getHeight(node.rChild) - getHeight(node.lChild) == 2){
38 if(key.compareTo(node.rChild.key) < 0){
39 //如果插入的节点位于当前节点的右节点的左子树，先右旋转再左旋转
40 node = rotateRightLeft(node);
41 }else{
42 //如果插入的节点位于当前节点的右节点的右子树，进行单次左旋转
43 node = rotateLeft(node);
44 }
45 }
46 } else{
47 //key已经存在，直接返回
48 }
49 //因为节点插入，树高发生变化，更新节点高度
50 node.height = updateHeight(node);
51 return node;
52 }
53
54 /**
55 * 删除
56 * @param key
57 */
58 public void delete(E key){
59 root = deleteAVL(key,root);
60 }
61
62 private AVLNode deleteAVL(E key, AVLNode<E> node){
63 if(node == null){
64 return null;
65 }
66 if(key.compareTo(node.key) < 0){
67 //左子树查找
68 node.lChild = deleteAVL(key,node.lChild);
69 //可能会出现，右子树比左子树高2
70 if (getHeight(node.rChild) - getHeight(node.lChild) == 2){
71 node = rotateLeft(node);
72 }
73 } else if(key.compareTo(node.key) > 0){
74 //右子树查找
75 node.rChild = deleteAVL(key, node.rChild);
76 //可能会出现，左子树比右子树高2
77 if (getHeight(node.lChild) - getHeight(node.rChild) == 2){
78 node = rotateRight(node);
79 }
80 }else{
81 //找到目标元素，删除分三种情况
82 //1.当前节点没有左子树，直接返回当前节点右子树
83 //2.当前节点没有右子树，直接返回当前节点右子树
84 //3.当前节点有左子树、右子树的时候，寻找当前节点的右子树的最末端的左子树，进行替换和移除
85 if(node.lChild == null){
86 return node.rChild;
87 }
88 if(node.rChild == null){
89 return node.lChild;
90 }
91 //找到当前节点的右子树的最末端的左子树，也就是右子树最小节点
92 AVLNode<E> minLChild = searchDeleteMin(node.rChild);
93 //删除最小节点，如果高度变化，进行调整
94 minLChild.rChild = deleteMin(node.rChild);
95 minLChild.lChild = node.lChild;//将当前节点的左子树转移到最小节点上
96
97 node = minLChild;//覆盖当前节点
98 //因为是右子树发生高度变低，因此可能需要调整
99 if(getHeight(node.lChild) - getHeight(node.rChild) == 2){
100 node = rotateRight(node);
101 }
102 }
103 node.height = updateHeight(node);
104 return node;
105 }
106
107 /**
108 * 搜索
109 * @param key
110 * @return
111 */
112 public AVLNode<E> search(E key){
113 return searchAVL(key, root);
114 }
115
116 private AVLNode<E> searchAVL(E key, AVLNode<E> node){
117 if(node == null){
118 return null;
119 }
120 //左子树搜索
121 if(key.compareTo(node.key) < 0){
122 return searchAVL(key, node.lChild);
123 }else if(key.compareTo(node.key) > 0){
124 return searchAVL(key, node.rChild);
125 } else{
126 //key已经存在，直接返回
127 return node;
128 }
129 }
130
131 /**
132 * 查找需要删除的元素
133 * @param node
134 * @return
135 */
136 private AVLNode<E> searchDeleteMin(AVLNode<E> node){
137 if (node == null){
138 return null;
139 }
140 while (node.lChild != null){
141 node = node.lChild;
142 }
143 return node;
144 }
145
146 /**
147 * 删除元素
148 * @param node
149 * @return
150 */
151 private AVLNode<E> deleteMin(AVLNode<E> node){
152 if(node == null){
153 return null;
154 }
155 if (node.lChild == null){
156 return node.rChild;
157 }
158 //移除最小节点
159 node.lChild = deleteMin(node.lChild);
160 //此时移除的是左节点，判断是否平衡高度被破坏
161 if(getHeight(node.rChild) - getHeight(node.lChild) == 2){
162 //进行调整
163 node = rotateLeft(node);
164 }
165 return node;
166
167 }
168
169 /**
170 * 单次左旋转
171 * @param node
172 * @return
173 */
174 private AVLNode<E> rotateLeft(AVLNode<E> node){
175 System.out.println("节点：" + node.key + "，单次左旋转");
176 AVLNode<E> x = node.rChild;//获取旋转节点的右节点
177 node.rChild = x.lChild;//将旋转节点的右节点的左节点转移，作为旋转节点的右子树
178 x.lChild = node;//将旋转节点作为旋转节点的右子树的左子树
179
180 //更新调整节点高度(先调整旋转节点node)
181 node.height = updateHeight(node);
182 x.height = updateHeight(x);
183 return x;
184 }
185
186 /**
187 * 单次右旋转
188 * @return
189 */
190 private AVLNode<E> rotateRight(AVLNode<E> node){
191 System.out.println("节点：" + node.key + "，单次右旋转");
192 AVLNode<E> x = node.lChild;//获取旋转节点的左节点
193 node.lChild = x.rChild;//将旋转节点的左节点的右节点转移，作为旋转节点的左子树
194 x.rChild = node;//将旋转节点作为旋转节点的左子树的右子树
195
196 //更新调整节点高度(先调整旋转节点node)
197 node.height = updateHeight(node);
198 x.height = updateHeight(x);
199 return x;
200 }
201
202 /**
203 * 左旋转-右旋转
204 * @param node
205 * @return
206 */
207 private AVLNode<E> rotateLeftRight(AVLNode<E> node){
208 System.out.println("节点：" + node.key + "，左旋转-右旋转");
209 //先对当前节点的左节点进行左旋转
210 node.lChild = rotateLeft(node.lChild);
211 //再对当前节点进行右旋转
212 return rotateRight(node);
213 }
214
215 /**
216 * 右旋转-左旋转
217 * @param node
218 * @return
219 */
220 private AVLNode<E> rotateRightLeft(AVLNode<E> node){
221 System.out.println("节点：" + node.key + "，右旋转-左旋转");
222 //先对当前节点的右节点进行右旋转
223 node.rChild = rotateRight(node.rChild);
224 return rotateLeft(node);
225
226 }
227
228 /**
229 * 获取节点高度，如果为空，等于-1
230 * @param node
231 * @return
232 */
233 private int getHeight(AVLNode<E> node){
234 return node != null ? node.height: -1;
235 }
236
237 /**
238 * 更新节点高度
239 * @param node
240 * @return
241 */
242 private int updateHeight(AVLNode<E> node){
243 //比较当前节点左子树、右子树高度，获取节点高度
244 return Math.max(getHeight(node.lChild), getHeight(node.rChild)) + 1;
245 }
246
247 /**
248 * 前序遍历
249 * @param node
250 */
251 public void frontTreeIterator(AVLNode<E> node){
252 if(node != null){
253 System.out.println("key:" + node.key);
254 frontTreeIterator(node.lChild);//遍历当前节点左子树
255 frontTreeIterator(node.rChild);//遍历当前节点右子树
256 }
257 }
258
259 /**
260 * 中序遍历
261 * @param node
262 */
263 public void middleTreeIterator(AVLNode<E> node){
264 if(node != null){
265 middleTreeIterator(node.lChild);//遍历当前节点左子树
266 System.out.println("key:" + node.key);
267 middleTreeIterator(node.rChild);//遍历当前节点右子树
268 }
269 }
270
271 /**
272 * 后序遍历
273 * @param node
274 */
275 public void backTreeIterator(AVLNode<E> node){
276 if(node != null){
277 backTreeIterator(node.lChild);//遍历当前节点左子树
278 backTreeIterator(node.rChild);//遍历当前节点右子树
279 System.out.println("key:" + node.key);
280 }
281 }
282
283}
测试代码，如下：
1public class AVLClient {
2
3 public static void main(String[] args) {
4 //创建一个Integer型的数据结构
5 AVLSolution<Integer> avlTree = new AVLSolution<Integer>();
6
7 //插入节点
8 System.out.println("========插入元素========");
9 avlTree.insert(new Integer(100));
10 avlTree.insert(new Integer(85));
11 avlTree.insert(new Integer(120));
12 avlTree.insert(new Integer(60));
13 avlTree.insert(new Integer(90));
14 avlTree.insert(new Integer(80));
15 avlTree.insert(new Integer(130));
16 System.out.println("========中序遍历元素========");
17
18 //中序遍历
19 avlTree.middleTreeIterator(avlTree.root);
20 System.out.println("========查找key为100的元素========");
21
22 //查询节点
23 AVLNode<Integer> searchResult = avlTree.search(120);
24 System.out.println("查找结果：" + searchResult);
25 System.out.println("========删除key为90的元素========");
26
27 //删除节点
28 avlTree.delete(90);
29 System.out.println("========再次中序遍历元素========");
30
31 //中序遍历
32 avlTree.middleTreeIterator(avlTree.root);
33 }
34}
输出结果如下：
四、总结
平衡二叉树查找树，俗称AVL树，在查询的时候，操作与普通二叉查找树上的查找操作相同;插入的时候，每一次插入结点操作最多只需要单旋转或双旋转;如果是动态删除，删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子，也就是高度差，如果超过1就需要调整，最多可能需要O(logN)次旋转。
整体上来说，平衡二叉树优于普通二叉查找树!
五、参考
[1] 简书 - nicktming - 二叉平衡树: https://www.jianshu.com/p/22c00b3731f5
[2] iteye - Heart.X.Raid - 平衡二叉查找树 [AVL]: https://www.iteye.com/blog/hxraid-609949
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK