平衡二叉树 java_Java集合源码分析之基础（五）：平衡二叉树（AVL Tree）

墨蓝 2022-11-01 15:50 8阅读 0赞

二叉排序树很好的平衡了插入与查找的效率，但不平衡的二叉排序树效率大打折扣。今天介绍的AVL树就是一种解决此问题的方案。

定义

平衡二叉树(Self-Balancing Binary Search Tree 或Height-Balanced Binary Search Tree)，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1 。它是一种高度平衡的二叉排序树。意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1 。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor)，那么平衡二叉树上所有结点的平衡因子只可能是-1 、0 和1。

如下图就不是一棵AVL树，因为结点18的左子树高度为2，右子树高度为0，高度差大于1。

![4f5eca987990][]

不平衡

但通过一定的步骤调整之后，可以将其转为一棵平衡二叉树，如下图：

![4f5eca987990][]

平衡二叉树

实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。最小不平衡子树是指距离插入结点最近的，且平衡因子的绝对值大于1 的结点为根的子树。

下面通过一个实例，了解平衡二叉树的构建过程。

假如我们要将数组int\[\] a = \{3, 2, 1, 4, 5, 6, 7, 10, 9, 8\}构建成一棵二叉排序树，如果直接按照二叉排序树的定义，会得到下面的结果：

![4f5eca987990][]

二叉排序树

这样的结果对查找是十分不利的，树的高度达到了8，而且大多数只有一个孩子。所以我们需要一些操作，将它变成一棵AVL树。

首先，插入元素3和2时，没有什么影响，此时3的平衡因子为1，2的平衡因子为0，结果如下：

![4f5eca987990][]

插入3和2

现在，要把1插入树中，这时结果如下所示：

![4f5eca987990][]

插入1

此时3的平衡因子为2了，不再符合平衡二叉树的规则。此时，整棵树就是最小不平衡子树，我们将其右旋：

![4f5eca987990][]

右旋

再插入4，也不会影响平衡，结果如下：

![4f5eca987990][]

插入4

此时，插入元素5，以3为根结点的子树成为了最小不平衡子树，如下所示：

![4f5eca987990][]

插入5

现在要对其进行左旋：

![4f5eca987990][]

左旋

现在继续插入元素6，此时以2为根结点的右子树为最小不平衡子树，结果如下：

![4f5eca987990][]

插入6

这时再次需要对其进行左旋，这次旋转后要将4的左孩子变为2的右孩子，以满足二叉排序树的定义，如下所示：

![4f5eca987990][]

左旋

再插入7时，情况和之前有些类似了，结果如下：

![4f5eca987990][]

插入7

左旋后结果如下：

![4f5eca987990][]

左旋

现在，继续插入10，此时无需调整，结果如下：

![4f5eca987990][]

插入10

下一步，插入元素9，此时结果如下：

![4f5eca987990][]

插入9

按照之前的经验，这时我们应该进行左旋了，但是左旋之后9将变为10的右孩子，这会不符合二叉排序树的定义。和之前不同的是，7和10的平衡因子符号相反，这是造成这一结果的原因。这种情况下，要先以10为根节点右旋，再进行左旋，结果如下所示：

![4f5eca987990][]

右旋

![4f5eca987990][]

左旋

最后插入元素8，如下所示：

![4f5eca987990][]

插入8

此时情况和上述类似，6是最小不平衡子树的根结点，9和6的平衡因子符号相反，所以先以9为根结点右旋：

![4f5eca987990][]

右旋

然后再以6左旋：

![4f5eca987990][]

左旋

可以看到，此树的高度仅为4，与之前的8相差很多，性能自然也好很多。

平衡二叉树的删除操作与插入类似，这里将不再介绍。大家可以自己思考如何最高效地删除元素，可以分叶结点、仅有一个子结点和有两个子结点三种情况考虑，这里还用到了递归的思想。

接下来我们将介绍另一种实现方式，红黑树。

我是飞机酱，如果您喜欢我的文章，可以关注我~

编程之路，道阻且长。唯，路漫漫其修远兮，吾将上下而求索。

[4f5eca987990]: /images/20221024/395fc6a36b184fb1a0027c00898fac8f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关平衡二叉树（AVL树）

一、基本介绍　　1）平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以**保证查询效率较高。...

拼搏现实的明天。/ 2024年04月18日 21:24/ 0 赞/ 119 阅读

相关平衡二叉树（AVL树）

我们先看看二叉排序树可能的问题：一个数列\{1,2,3,4,5,6\}，要求创建一颗二叉排序树(BST), 并分析问题所在 ![在这里插入图片描述][20200306

刺骨的言语ヽ痛彻心扉/ 2023年07月11日 15:02/ 0 赞/ 55 阅读

相关平衡二叉树（AVL树）

平衡二叉树的实现过程如下： include <stdio.h> include <malloc.h> typedef int KeyType;

今天药忘吃喽~/ 2023年03月13日 03:00/ 0 赞/ 35 阅读

相关二叉树平衡（AVL树）

一、前言 [《二叉查找树全面详细介绍》][Link 1]中讲解了二叉树操作：搜索（查找）、遍历、插入、删除。[《二叉树遍历详解（递归遍历、非递归栈遍历，Morris遍历）

傷城~/ 2023年02月22日 15:00/ 0 赞/ 54 阅读

相关 AVL树-平衡二叉树

![在这里插入图片描述][20210516102909842.png] AVL树目录: 一.概念&原理二.平衡因子

末蓝、/ 2023年01月21日 05:26/ 0 赞/ 48 阅读

相关二叉平衡树（AVL树）

平衡二叉树定义平衡二叉树全称叫做 `平衡二叉搜索（排序）树`，简称 AVL树。英文：Balanced Binary Tree （BBT），注：二叉查找树(BST)

小鱼儿/ 2022年12月12日 15:03/ 0 赞/ 316 阅读

相关平衡二叉树 java_Java集合源码分析之基础（五）：平衡二叉树（AVL Tree）

二叉排序树很好的平衡了插入与查找的效率，但不平衡的二叉排序树效率大打折扣。今天介绍的AVL树就是一种解决此问题的方案。定义平衡二叉树(Self-Balancing Bi

墨蓝/ 2022年11月01日 15:50/ 0 赞/ 9 阅读

相关平衡二叉树（AVL树）

优质文档值得推荐： [数据结构-AVL树的旋转][-AVL] [图解数据结构树之AVL树][AVL] 例题： ![watermark_type_ZmFuZ3poZW5n

た入场券/ 2022年03月12日 12:42/ 0 赞/ 357 阅读

相关平衡二叉树（AVL树）

> 本文来自：https://blog.zhenlanghuo.top/2017/08/22/AVL%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E

刺骨的言语ヽ痛彻心扉/ 2022年01月30日 04:55/ 0 赞/ 392 阅读

相关转载：平衡二叉树(AVL Tree)

[平衡二叉树（AVL Tree）][AVL Tree] 转载至：https://www.cnblogs.com/jielongAI/p/9565776.html 在学习

柔光的暖阳◎/ 2021年11月11日 14:22/ 0 赞/ 380 阅读