【数据结构】什么是平衡二叉搜索树(AVL树)?

📌AVL树的概念

我们之前一起学习过二叉搜索树,知道它具有较好的搜索性能, 但是普通的二叉搜索树会有一个问题,那就是它可能会因为输入的值不够随机,也可能因为经过某些插入或删除的操作,导致其失去平衡退化为单支树并导致搜索效率降低的情况, 如下不平衡搜索树:

可以发现,如果搜索二叉树退化到这样极端的不平衡状态,其搜索效率就会大大降低, 时间复杂度会从

O(log_{2}N)

退化到

O(N)

.为了解决这种情况,我们将引入AVL树的概念.

AVL树是一个 “加上了额外平衡条件” 的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为

O(log_{2}N)

。直观上的最佳平衡条件是每个节点的左右子树有着相同的高度，但这未免太过严苛，我们很难插入新元素而又保持这样的平衡条件。AVL树于是退而求其次，要求任何节点的左右子树高度相差最多1。这是一个较弱的条件，但仍能够保证“对数深度(logarithmic depth)”平衡状态。 因此, AVL树是一种二叉搜索树, 其中每一个结点的左子树和右子树的高度差至多等于1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor), 那么平衡二叉树上所有结点的平衡因子只可能是-1/ 0/ 1.

📌AVL树的操作

🎏AVL树的插入操作

我们知道,对于一颗AVL树而言,新插入的结点是很有可能破坏其平衡结构的,如:

那么AVL树是如何解决这种情况的呢?下面我将通过模拟一组AVL树结点的插入来讲清楚AVL树是如何维持其平衡特性的.

下面我们将以这组数据为例,详细剖析一下AVL树维持其平衡的插入过程:

14 9 5 17 11 12 7 19 16 27

首先我们插入第一个结点14:

然后我们插入第二个结点9:

此时AVL树仍然是平衡状态,然后我们插入下一个结点5:

可以看到,插入结点5之后,AVL树的根节点14就已经不满足平衡搜索二叉树的条件了,即它左子树的高度减去右子树的高度已经大于1,因此我们下面就要运用AVL树对不平衡的第一种处理方式,也就是右单旋:

↩️右单旋

右单旋处理应用的情况为:

• 失衡结点平衡因子 = 2
• 失衡结点左孩子平衡因子 = 1

右单旋的处理操作步骤为:

• 将失衡结点左孩子的右子树链接到失衡结点的左孩子的位置
• 将失衡结点链接到失衡结点左孩子的右孩子位置

所以我们下面采取右单旋的方式使AVL树重新平衡, 因为失衡结点14的左孩子9并没有右孩子,所以我们可以直接将失衡结点14链接到失衡结点左孩子9的右孩子位置, 右单旋示意图如下:

经过右单旋操作之后,我们得到的AVL树就又重新满足平衡二叉搜索树了:

接下来我们继续插入新结点17:

再继续插入新结点11:

再继续插入新结点12:

可以看到,插入结点12之后,AVL树的根节点9就已经不满足平衡搜索二叉树的条件了,即它左子树的高度减去右子树的高度已经成了-2,因此我们下面就要运用AVL树对不平衡的第二种处理方式,也就是右左双旋:

↩️↪️右左双旋

右左双旋处理应用的情况为:

• 失衡结点平衡因子 = -2
• 失衡结点右孩子平衡因子 = 1

右左双旋的处理操作步骤为:

• 将失衡结点的右孩子右单旋
• 再将失衡结点左单旋

所以我们下面采取右左双旋的方式使AVL树重新平衡, 我们先将失衡结点9的右孩子14进行右单旋, 再将失衡结点9进行左单旋,右左双旋操作示意图如下:

经过右左双旋操作之后,我们得到的AVL树就又重新满足平衡二叉搜索树了:

我们继续插入新结点7:

可以看到,插入结点7之后,AVL树的节点9就已经不满足平衡搜索二叉树的条件了,即它左子树的高度减去右子树的高度已经成了2,因此我们下面就要运用AVL树对不平衡的第三种处理方式,也就是左右双旋:

↪️↩️左右双旋

左右双旋处理应用的情况为:

• 失衡结点平衡因子 = 2
• 失衡结点左孩子平衡因子 = -1

左右双旋的处理操作步骤为:

• 将失衡结点的左孩子左单旋
• 再将失衡结点右单旋

所以我们下面采取左右双旋的方式使AVL树重新平衡, 我们先将失衡结点9的左孩子5进行左单旋, 再将失衡结点9进行右单旋,左右双旋操作示意图如下:

经过左右双旋操作之后,我们得到的AVL树就又重新满足平衡二叉搜索树了:

然后我们继续插入新结点19:

继续插入新结点16:

最后插入结点27:

可以看到,插入结点27之后我们发现AVL树的根节点11和其右孩子14都失衡了.这个时候我们只需要调整距离新插入结点最近的失衡结点即可,调整完这个最近失衡结点之后,其余的祖先失衡结点会自动恢复平衡的。我们下面就要运用AVL树对不平衡的第四种处理方式,也就是左单旋:

↪️左单旋

左单旋处理应用的情况为:

• 失衡结点平衡因子 = -2
• 失衡结点右孩子平衡因子 = -1

左单旋的处理操作步骤为:

• 将失衡结点右孩子的左子树链接到失衡结点的右孩子的位置
• 将失衡结点链接到失衡结点右孩子的左孩子位置

所以我们下面采取左单旋的方式使AVL树重新平衡, 先将失衡结点14的右孩子17的右子树16链接到失衡结点14的右孩子的位置,再将失衡结点14链接到失衡结点右孩子17的左孩子位置, 左单旋示意图如下:

经过左单旋操作之后,我们得到的AVL树就完成了所有的插入操作并满足平衡二叉搜索树了:

在经历了四种旋转操作之后,我们将旋转的方式以及其对应的影响因子的特征总结如下:

🎏AVL树的删除操作

前面讲了AVL树的插入操作需要保证其不失衡, 对于AVL树的删除操作来说也一样, 同样需要保证其操作后树不失衡, 和插入操作不同的是, 删除操作可能会导致不只一次的失衡, 所以我们不能像插入那样只调节最近的失衡结点就行, 在删除时可以参考之前讲过的二叉搜索树的删除操作,但是AVL树在删除之后需要沿着祖先结点一直向上继续查找是否有结点失衡的情况,如果有,就需要进行旋转调整,其旋转规则和插入时我们总结的影响因子特征相同。 下图附上二叉搜索树的删除逻辑,有兴趣的朋友可以自行研究一下:

结语

希望这篇关于 平衡二叉搜索树(AVL树) 的博客能对大家有所帮助,欢迎大佬们留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!