数据结构与算法之树（三）AVL树

柔情只为你懂 2024-04-19 12:35 101阅读 0赞

**数据结构与算法之树**

[数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）][Link 1]

[数据结构与算法之树（二）二叉查找树][Link 2]

[数据结构与算法之树（三）AVL树][AVL]

[数据结构与算法之树（四）红黑树][Link 3]

# 数据结构与算法之树（三）AVL树 #

### 文章目录 ###

*  数据结构与算法之树（三）AVL树
 *   *  一、什么是平衡二叉树？
     *  二、什么是AVL树？
     *  三、AVL树的调整策略
     *   *  3.1 旋转操作
         *   *  3.1.1 左旋
             *  3.1.2 右旋
         *  3.2 需要调整的节点
         *  3.3 情况分类
         *   *  3.3.1 LL
             *  3.3.2 LR
             *  3.3.3 RR
             *  3.3.4 RL
     *  四、总结

## 一、什么是平衡二叉树？ ##

上一篇文章在讲述二叉查找树的时候，在极端情况下二叉查找树的左右子树极不平衡，造成了搜索速率的低落，于是为了防止左右子树极不平衡的情况，有了平衡二叉查找树

所谓的“平衡”，没有一个绝对的测量标准，大致的意思是左右子树的高度差不多

不同的平衡条件，造就了不同的搜索、插入、删除的效率，以及不同的实现复杂度，常见的平衡二叉树有AVL树、红黑树等，本文将讲解AVL树

## 二、什么是AVL树？ ##

> AVL树规定，任何一个节点，左右子树的高度相差不大于1

如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]

左边的二叉树满足AVL树的要求，在插入值为2节点后，它不满足AVL树的要求了，因为值为4和5的节点它们的左右子树高度相差大于1

那么我们可以使用什么策略来进行调整，使其满足AVL树的要求呢？

## 三、AVL树的调整策略 ##

将不平衡的二叉搜索树调整成AVL树，需要对`指定节点`进行`旋转操作`，下面先来讲以下旋转操作

### 3.1 旋转操作 ###

旋转操作分为左旋和右旋

#### 3.1.1 左旋 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 1]

如上图所示，就是将`3节点`进行左旋操作

上图的操作中，是要进行左旋操作的节点它的右子节点没有左节点，也就是`5节点`没有左节点，设想一下如果`5节`点有`左节点`，那么对`3节点`进行左旋操作，会发生什么？

先想一下对下面这棵树的`3节点`进行左旋操作，会发生什么？

![在这里插入图片描述][20190918113423349.PNG]

没错，会发生冲突，`5节点`会有两个左节点，这是二叉树不允许的，如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 2]

那么怎么解决冲突？

解决冲突的方法就是将冲突节点插入到指定位置，如上图，我们冲突的节点是`4节点`，而`4节点`是`5节点`的左子节点，肯定比`5节点`小，那么在进行旋转之后，将`4节点`按二叉查找树的插入规则插入到`5节点`的左子树即可，如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 3]

**适当小结一下**

左旋操作会有两种情况

1.要左旋节点的右子节点`没有`左子节点，这种情况下不会发生冲突

2.要左旋节点的右子节点`有`左子节点，这种情况会发生冲突，解决冲突的方法就是将冲突节点插入到旋转后主节点的左子树

#### 3.1.2 右旋 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 4]

上图是对`8节点`进行右旋操作

如果`5节点`有右子节点，也会发生冲突，解决办法是将冲突节点插入到右子树中，如下所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 5]

**小结**

右旋操作也有两种情况

1.进行右旋操作的节点的左子节点`没有`右子节点，这种情况不会发生冲突

2.进行右旋操作的节点的左子节点`有`右子节点，这种情况会发生冲突，解决冲突的办法是将冲突的节点插入到旋转后主节点的右子树

在理解左旋和右旋操作后，下面将将讲解AVL的调整策略

### 3.2 需要调整的节点 ###

首先我们讨论在插入一个节点，使得二叉树不在是AVL树的时候，我们需要对哪个节点作出调整？

首先我们来看一个例子

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]

上述这个例子，在插入`2节点`后，二叉树不在是AVL树，此时是因为`4节点`和`5节点`不满足AVL树的规定

这里我们要解决`4节点`，只要将`4节点`进行一次右旋操作，就可以解决问题，如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 6]

我们可以得到一个规律是

> 需要调整的节点是不满足AVL树规定的节点中最深的那么节点（如4节点）

在清楚需要调整的节点后，我们来讲一讲需要调整的情况

### 3.3 情况分类 ###

调整的情况可以分为4中

> LL：插入节点在需要调整节点左子树的左子节点
> 
> LR：插入节点在需要调整节点左子树的右子节点
> 
> RR：插入节点在需要调整节点右子树的右子节点
> 
> RL：插入节点在需要调整节点右子树的左子节点

这四种情况都有各自的调整策略，下面将一一介绍

#### 3.3.1 LL ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 7]

对于这种情况，我们只需要将我们要调整的节点（4节点）进行一次右旋操作即可，如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 8]

#### 3.3.2 LR ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 9]

对于这种情况，我们需要将调整节点（4节点）的左子节点（2节点）进行一个左旋，然后再对调整节点（4节点）进行一次右旋，如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 10]

#### 3.3.3 RR ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 11]

对于这种情况我们只需要将调整节点（4节点）进行一次左旋即可，如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 12]

#### 3.3.4 RL ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 13]

对于这种情况，我们需要将调整节点（4节点）的右子节点（6节点）进行一次右旋，然后对调整节点（4节点）进行一次左旋，如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 14]

**小结**

AVL的调整策略有四种，LL、LR、RR、RL，其中LL和RR可以分为外侧调整，LR、RL可以分为内侧调整。对于外侧只需要进行一次单旋操作。对于内侧需要进行双旋，其中第一次将其变为外侧，第二次调整为AVL树

## 四、总结 ##

本篇文章讲解了平衡二叉查找树和AVL树的概念，重点讲解了AVL树的调整策略，其中需要重点掌握的是旋转操作

好了，本文到此就结束了，下一篇文章将讲解红黑树

[Link 1]: https://blog.csdn.net/weixin_42462202/article/details/100864133
[Link 2]: https://blog.csdn.net/weixin_42462202/article/details/100902052
[AVL]: https://blog.csdn.net/weixin_42462202/article/details/100979244
[Link 3]: https://blog.csdn.net/weixin_42462202/article/details/100996219
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190918111032863.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190918112112564.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[20190918113423349.PNG]: https://img-blog.csdnimg.cn/20190918113423349.PNG
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190918114158181.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190918114014975.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190918115707262.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20190918115930419.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20190918121000974.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20190918121919502.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20190918122413111.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20190918122914984.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20190918122822384.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20190918123056181.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20190918123341624.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20190918123524409.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20190918123942560.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70