图解：什么是AVL树？

引子

上一次我给大家介绍了什么是二叉搜索树，但是由于二叉搜索树查询效率的不稳定性，所以很少运用在实际的场景中，所以我们伟大的前人就对二叉搜索树进行了改良，发明了AVL树。

AVL树是一种自平衡二叉搜索树，因为AVL树任意节点的左右子树高度差的绝对值不超过1，所以AVL树又被称为高度平衡树。

AVL树本质上是一棵带有平衡条件的二叉搜索树，它满足二叉搜索树的基本特性，所以本次主要介绍AVL树怎么自平衡，也就是理解它的旋转过程。

二叉搜索树特性忘了的小伙伴可以看之前的文章：搞定二叉搜索树，9图足矣！同时我也将基本性质给大家再回顾一遍：

1. 若它的左子树不为空，则左子树上所有节点的值均小于根节点的值。

2. 若它的右子树不为空，则右子树上所有节点的值均大于根节点的值。

3. 它的左、右子树也分别为二叉搜索树。

平衡条件：每个节点的左右子树的高度差的绝对值不超过1。

我们将每个节点的左右子树的高度差的绝对值又叫做平衡因子。

AVL树的旋转行为一般是在插入和删除过程中才发生的，因为插入过程中的旋转相比于删除过程的旋转而言更加简单和直观，所以我给大家图解一下AVL树的插入过程。

插入过程

最开始的时候为空树，没有任何节点，所以我们直接用数据构造一个节点插入就好了，比如第一个要插入的数据为18。

第一个节点插入完成，开始插入第二个节点，假如数据为20。

插入第三个节点数据为14。

第四个节点数据为16。从根节点位置开始比较并寻找16的对应插入位置。

第五个要插入的数据为12。还是一样，从树的根节点出发，根据二叉搜索树的特性向下寻找到对应的位置。

此时插入一个数据11，根据搜索树的性质，我们不难找到它的对应插入位置，但是当我们插入11这个节点之后就不满足AVL树的平衡条件了。

此时相当于18的左子树高了，右子树矮了，所以我们应该进行一次右单旋，右单旋使左子树被提起来，右子树被拉下去，相当于左子树变矮了，右子树变高了，所以一次旋转之后，又满足平衡条件了。

简单分析上图的旋转过程：**因为左子树被提上去了，所以14成为了新的根节点，而18被拉到了14右子树的位置，又因为14这个节点原来有右子节点为16，所以18与16旋转之后的位置就冲突了，但是因为16小于18，**所以这个时候根据二叉搜索树的特性，将16调整到18的左子树中去，因为旋转之后的18这个节点的左子树是没有节点的，所以16可以直接挂到18的左边，如果18的左子树有节点，那么还需要根据二叉搜索树的性质去将16与18左子树中的节点比较大小，直到确定新的位置。

经过上面的分析我们可以知道：如果新插入的节点插入到根节点较高左子树的左侧，则需要进行一次右单旋，我们一般将这种情况简单记为左左情况，第一个左说的是较高左子树的左，第二个左说的是新节点插入到较高左子树的左侧。

分析完了左左的情况，我想小伙伴们不难推出右右的情况(第一个右说的是较高右子树的右，第二个右说的是新节点插入到较高右子树的右侧)，就是一次左单旋，这里就不一步一步地分析右右的情况了，因为它和左左是对称的。给大家画个图，聪明的你一眼就可以学会！

现在两种单旋的情况已经讲完了，分别是左左和右右，还剩下两种单旋的情况，不过别慌，因为双旋比你想象中的简单，而且同样，双旋也是两种对称的情况，实际上我们只剩下一种情况需要分析了，所以，加油，弄懂了的话，面试的时候就完全不用慌了！

双旋

我们假设当前的AVL树为下图。

这个时候我们新插入一个节点，数据为15，根据搜索树的性质，我们找到15对应的位置并插入，如图

我们此时再次计算每个节点的平衡因子，发现根节点18的平衡因子为2，超过了1，不满足平衡条件，所以需要对他进行旋转。

我们将刚才需要进行右单旋的左左情况和现在的这种情况放在一起对比一下，聪明的你一定发现，当前的情况相比于左左的情况只是插入的位置不同而已，左左情况插入的节点在根节点18较高左子树的左侧，而当前这种情况插入节点是在根节点18较高左子树的右侧，我们将它称为左右情况。

那么可能正看到这里的你可能不禁会想：这不跟刚才左左差不多嘛，直接右单旋不就完事了。真的是这样吗？让我们来一次右单旋看看再说。

简单分析该右单旋：**节点14上提变成新的根节点，18下拉变成根节点的右子树，又因为当前根节点14原来有右子树16，所以18与16位置冲突，**比较18与16大小之后，发现18大于16，根据搜索树的性质，将以16为根节点的子树调整到18的左子树，因为18的左子树目前为空，所以以16为根的子树直接挂在18的左侧，若18的左子树不为空，则需要根据搜索树的性质继续进行比较，直到找到合适的挂载位置。

既然一次右单旋不行，那么我们应该怎么办呢？答案就是进行一次双旋，一次双旋可以拆分成两次单旋，对于当前这种不平衡条件，我们可以先进行一次左单旋，再进行一次右单旋，之后就可以将树调整成满足平衡条件的AVL树了，话不多说，图解一下。

简单分析左右双旋：先对虚线框内的子树进行左单旋，则16上提变成子树的新根，以14为根节点的子树下拉，调整到16的左子树，此时发现16的左子树为15，与14这棵子树冲突，所以根据搜索树规则进行调整，将15挂载到以14为根节点子树的右子树，从而完成一次左单旋，之后再对整棵树进行一次右单旋，节点16上提成为新的根节点，18下拉变成根节点的右子树，因为之前16没有右子树，所以以18为根节点的子树直接挂载到16的右子树，从而完成右旋。

同样，对于左右情况的对称情况右左情况我就不给大家分析了，还是将图解送给大家，相信聪明的你一看就会！

到此为止，我将AVL树的四种旋转情况都给大家介绍了一遍，仔细想想，其实不止这四种情况需要旋转，严格意义上来说有八种情况需要旋转，比如之前介绍的左左情况吧，我们说左左就是将新的节点插入到了根节点较高左子树的左侧，这个左侧其实细分一下又有两种情况，只不过这两种情况实际可以合成一种情况来看，也就是新的节点插入到左侧的时候可以成为它父亲节点的左孩子，也可以成为它父亲节点的右孩子，那么这样的话就是相当于两种情况了，简单画个图看一下吧。

就是这样上图这样，每个新插入的节点都可以是它父亲节点的左孩子或者右孩子，这取决于新插入数据的大小，比如11就是12的左孩子，13就是12的右孩子，这两种情况都属于左左情况，也就是说他们本质上是一样的，都插在了节点18较高左子树的左侧。

那么这样看来这四种旋转情况严格上看都可以多分出一种情况，变成八种情况。

后话

emmm…这样看来AVL树确实解决了二叉搜索树可能不平衡的缺陷，补足了性能上不稳定的缺陷，但是细细想来AVL树的效率其实不是很好，这里说的不是查询效率，而是插入与删除效率，上面所说的这四大种八小种情况还是很容易命中的，那么这样的话就需要花费大量的时间去进行旋转调整，我的天，这样也太难搞了！

不过聪明的前人早就为我们想好了更加利于实际用途的搜索树，在现实场景中AVL树和二叉搜索树一样，基本上用不到，我们接下来要讲的这种二叉类的搜索树才是我们经常应用的，相信见多识广的你一定猜到了它的名字，对，就是它，大名鼎鼎的红黑树！我们下次来盘他！

鄙人才疏学浅，若有任何差错，还望各位海涵，不吝指教！

喜欢本文的少侠们，欢迎关注公众号雷子的编程江湖，修炼更多武林秘籍。

一键三连是中华民族的当代美德！