谈谈你对AVL树的了解

小灰灰 2023-10-13 13:14 32阅读 0赞

### 谈谈你对AVL树的了解 ###

*  AVL树的定义
 *  平衡因子
 *  插入操作
 *   *  调整策略
     *   *  LL型状态
         *  RR型状态
         *  LR型状态
         *  RL型状态
     *  插入操作总结
     *  4种调整方法过程图

# AVL树的定义 #

AVL树是二叉搜索树的一种，是一种自平衡二叉搜索树。

# 平衡因子 #

在AVL树中每个结点中存有一个量为平衡因子。

平衡因子定义为该节点的左子树高度减去右子树的高度的值。有一些定义是右边减去左边，但区别不大。

![在这里插入图片描述][b7dad3e236e94d43874f463356eae66d.png]  
同理，每个节点都按照这样计算，就得到了所有节点的平衡因子。AVL树规定每个结点的平衡因子的绝对值不大于1，即每个结点的左右子树高度查不大于1。这样二叉搜索树可以保持高度的平衡。

如果结点的平衡因子绝对值不大于1，则说明该结点的子树不平衡，则需要对该节点进行调整。

# 插入操作 #

我们要将0插入到这个avl树中，首先我们按照常规二叉搜索树的插入操作。即不断比较直到叶子节点为止。

![在这里插入图片描述][f48791c4f99748dd84630f38e62f9306.png]  
注意，这个比较的路径需要记录。因为后续调整需要沿着路径从下往上进行。当插入一个元素的时候，该元素可能会打破avl树的平衡。所以我们要沿着路径依次检查路径的平衡因子。

若结点的平衡因子绝对值不大于1，则不需要操作，看到这时检测到4结点平衡因子为2，平衡被打破了，那么4结点就要执行调整方法。

![在这里插入图片描述][83bc67fd77f3458baf6607c03dbcd663.png]

## 调整策略 ##

按照插入元素的落点，调整策略分为四种情况，插入元素落入以上4个子树的情况分别对应着4种状态。

### LL型状态 ###

当插入元素落在1号子树上，此时为LL型状态。

![在这里插入图片描述][73972edd63a049ec8bf19d76c59d6d86.png]  
这时对根节点，也就是A结点使用右旋操作进行调整。这时使用右旋操作进行调整，具体方法是将B结点向上提拔作为根结点，并重新连接结点关系。

![在这里插入图片描述][85a199f630094250816d78dc4a23d7cc.png]  
可以看到带有插入元素的子树向上移动了一层，这样就可以平衡两边的高度差。因为其他子树原来就保持平衡状态，所以移动后仍然保持平衡。这个可以自行证明。

### RR型状态 ###

与其对应的是RR型状态，此时插入元素落入4号子树中，同理对根结点使用左旋操作调整。

![在这里插入图片描述][35ee538b0836484ea62eb72ea44c192e.png]  
将C结点向上提拔为根节点，并重新连接结点关系。

![在这里插入图片描述][7dbaf51a991c4d14908bf9d31b9e328e.png]  
同样带有插入元素的子树向上移动了一层，平衡了两边的高度差。左旋和右旋是avl树最基础的调整方法。当插入元素落在2号子树或3号子树时，则要使用双旋操作，但双旋操作也仅仅是左右旋操作的组合。  
![在这里插入图片描述][bd60b903f21c4ad49d5c7e134bc7fd0e.png]  
在讲双旋前，我们不妨看一个左右旋操作的例子，我们回到之前插入的例子中，我们检测到4号结点不平衡，所以要对其进行调整。

将4号结点和其子树放入之前的模板里比较。

![在这里插入图片描述][1eaa9b789bcd4630a4e3dc739f5f0af9.png]  
![在这里插入图片描述][eba6c43de2c04dd7832fa3332d1cd0d6.png]  
0号结点是插入元素，而0又在模板对应的1号子树中，所以对4号结点进行的是右旋操作。

![在这里插入图片描述][27d16836f78a4696a61eddd68135a2d9.png]  
操作完成后可以观察到其回复了平衡。我们回到检查路径中，最后检查到根节点，结点平衡插入完成。这个例子层数比较少，所以路径上只有一个结点不平衡。如果路径中出现了多个不平衡点，只要进行多次调整方法即可。

### LR型状态 ###

当插入元素在2号子树时，这种情况称为LR型状态，这种情况稍微复杂一点。我们需要拆开2号子树。如图所示，其结点为D，其左右子树标为5和6，插入元素落在5还是6号子树上都是一样的处理。

因为处理后5和6号子树都会向上移动。这时我们对根结点A使用双旋操作来调整。

![在这里插入图片描述][71484a3ebfc84af9bfa78a425202a95b.png]  
将D向上提拔到根节点，并重新连接。这时树就可以恢复平衡。

![在这里插入图片描述][7f9fe28f7b2b4f33a8e3fba76049828d.png]  
如果仔细观察这个结果，可以发现这个操作等效于先对B结点作左旋操作，再对A结点作右旋操作。这样就可以复用之前写的代码了。

### RL型状态 ###

与其对称的是RL型状态，同样拆开3号子树，将D结点提拔为根结点，并重新连接。

![在这里插入图片描述][e70918e471944a279cf416f57c3b2137.png]  
这个操作等效于先对C结点作右旋操作，再对A结点作左旋操作。

我们来看一个简单的例子，如图所示，我们将3号元素插入到AVL中，标出插入的比较路径，然后依次检查，检查到2号结点发现不平衡，则要进行调整。

![在这里插入图片描述][7a6b7b8cd0a7461aa07e4fbbbadff8ac.png]  
按照模板的位置，3号元素是在3号子树中，所以是RL型状态。

![在这里插入图片描述][26bc377e0bf74d79834770a402bfafa9.png]  
可以看到树恢复了平衡，同时2号元素是原来的根节点。所以插入调整结束。

## 插入操作总结 ##

![在这里插入图片描述][98732a23dc1d40c2899a880b692fd370.png]  
首先我们按照常规二叉搜索树插入，然后按照比较路径回溯检查。如果结点平衡，则无需操作。当遇到平衡因子绝对值大于1的结点，就进入判断方法。按照插入元素的位置，判断是4种状态中的哪一种，然后使用对应的方法进行调整。该节点调整结束后，回到路径继续检查，重复以上操作，也就是继续回溯直到根节点结束。

## 4种调整方法过程图 ##

![在这里插入图片描述][96cfcade5af84e97b26322246f4e5738.png]  
![在这里插入图片描述][d792b73a170f4f42a2f19f7ba00c1feb.png]  
**参考资料**：[【AVL树的定义 .调整 .插入操作】如何理解AVL树这个数据结构][AVL_ ._ ._AVL]

[b7dad3e236e94d43874f463356eae66d.png]: https://img-blog.csdnimg.cn/b7dad3e236e94d43874f463356eae66d.png
[f48791c4f99748dd84630f38e62f9306.png]: https://img-blog.csdnimg.cn/f48791c4f99748dd84630f38e62f9306.png
[83bc67fd77f3458baf6607c03dbcd663.png]: https://img-blog.csdnimg.cn/83bc67fd77f3458baf6607c03dbcd663.png
[73972edd63a049ec8bf19d76c59d6d86.png]: https://img-blog.csdnimg.cn/73972edd63a049ec8bf19d76c59d6d86.png
[85a199f630094250816d78dc4a23d7cc.png]: https://img-blog.csdnimg.cn/85a199f630094250816d78dc4a23d7cc.png
[35ee538b0836484ea62eb72ea44c192e.png]: https://img-blog.csdnimg.cn/35ee538b0836484ea62eb72ea44c192e.png
[7dbaf51a991c4d14908bf9d31b9e328e.png]: https://img-blog.csdnimg.cn/7dbaf51a991c4d14908bf9d31b9e328e.png
[bd60b903f21c4ad49d5c7e134bc7fd0e.png]: https://img-blog.csdnimg.cn/bd60b903f21c4ad49d5c7e134bc7fd0e.png
[1eaa9b789bcd4630a4e3dc739f5f0af9.png]: https://img-blog.csdnimg.cn/1eaa9b789bcd4630a4e3dc739f5f0af9.png
[eba6c43de2c04dd7832fa3332d1cd0d6.png]: https://img-blog.csdnimg.cn/eba6c43de2c04dd7832fa3332d1cd0d6.png
[27d16836f78a4696a61eddd68135a2d9.png]: https://img-blog.csdnimg.cn/27d16836f78a4696a61eddd68135a2d9.png
[71484a3ebfc84af9bfa78a425202a95b.png]: https://img-blog.csdnimg.cn/71484a3ebfc84af9bfa78a425202a95b.png
[7f9fe28f7b2b4f33a8e3fba76049828d.png]: https://img-blog.csdnimg.cn/7f9fe28f7b2b4f33a8e3fba76049828d.png
[e70918e471944a279cf416f57c3b2137.png]: https://img-blog.csdnimg.cn/e70918e471944a279cf416f57c3b2137.png
[7a6b7b8cd0a7461aa07e4fbbbadff8ac.png]: https://img-blog.csdnimg.cn/7a6b7b8cd0a7461aa07e4fbbbadff8ac.png
[26bc377e0bf74d79834770a402bfafa9.png]: https://img-blog.csdnimg.cn/26bc377e0bf74d79834770a402bfafa9.png
[98732a23dc1d40c2899a880b692fd370.png]: https://img-blog.csdnimg.cn/98732a23dc1d40c2899a880b692fd370.png
[96cfcade5af84e97b26322246f4e5738.png]: https://img-blog.csdnimg.cn/96cfcade5af84e97b26322246f4e5738.png
[d792b73a170f4f42a2f19f7ba00c1feb.png]: https://img-blog.csdnimg.cn/d792b73a170f4f42a2f19f7ba00c1feb.png
[AVL_ ._ ._AVL]: https://www.bilibili.com/video/BV1dr4y1j7Mz/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb