平衡二叉树

2019-09-25 本文已影响0人 ITsCLG

最近比较忙，没闲得下时间写简书。小编在之前的分享中有讲过二叉搜索树，如下的两颗树都满足二叉搜索树的条件。

图片1

图片1中两棵二叉搜索树都通过前面小编分享的代码进行构造。可发现二叉搜索树有一个缺点就是，树的结构是无法预料的，随意性很大，它只与节点的值和插入的顺序有关系，往往得到的是一个不平衡的二叉树。在最坏的情况下，可能得到的是一个单支二叉树，如上图1所示，其高度和节点数相同，相当于一个单链表，对其正常的时间复杂度有O(lgn)变成了O(n)，从而丧失了二叉排序树的一些应该有的优点【对于该部分时间复杂度的分析，可看下小编之前分享的另一篇简书】。

因此我们需要一种算法，能够改进在树上的查找、插入和删除等速率。G.M. Adelson-Velsky和 E.M. Landis率先发明了这样的一种树，也就是自平衡二叉查找树【Self-Balancing Binary Search Tree,简称平衡二叉树，AVL树的名字来源于它的发明作者】。平衡二叉树是对普通的二叉搜索树的改进，因此它一定满足二叉搜索树的所有条件，且平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。

平衡二叉树具备的两个特点：

① 它必须是二叉查找树

② 它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

接下来小编先简单介绍几个有关AVL树的概念。

（1）平衡因子

将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF（Balance Factor）。我们来看下图：

图片2

在该AVL树上：

节点60的左子树高度为2，右子树高度为2，BF=2-2 = 0；

节点45的左子树高度为1，右子树高度为0，BF=1-0= 1；

节点32的左子树高度为0，右子树高度为0，BF= 0-0 = 0；

节点65的左子树高度为0，右子树高度为1，BF= 0-1 = -1；

对于平衡二叉树，BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围，则需要对树进行调整。

（2）最小不平衡树

距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树.，我们称之为最小不平衡树。我们在上图中插入一个节点42得到下图的树：

图片3

其中，我们管32为插入节点，以节点32为树根的子树的BF=1，以节点45为树根的子树的BF=2，大于1。因此要对该树进行调整，该树称之为最小不平衡树。

因此，对于一棵不平衡树的节点，我们可以定义这么一个类来表示【后续代码添加还会对该类进行修改】，截图如下：

节点类

在类中定义节点的高度后续可用来计算节点的平衡因子BF。那如何对建立的二叉搜索树实时进行调整呢，我们来看看几种情况。

（1）LL型调整

首先我们来看一个最简单的例子，如下图4中的①。这是一棵简单的平衡二叉树，插入节点C得到的树的形状如②所示。这个时候节点A的平衡因子BF=2，大于1，因此树不平衡了，需要调整。当然要注意调整完的树也必须是二叉搜索树。这个时候，最小的失衡子树为以根节点为A的树。以该失衡节点A的左孩子节点B为固定的轴进行旋转。在下图中，我们将A绕B进行顺时针旋转，也就是右旋。得到的树的形状如③所示。这个时候B为根节点，且满足B的键值大于C的键值，B的键值小于A的键值，满足二叉搜索树的特征。

图片4

当然上图是比较简单的情况，如果是下面的情况，还需进行其它操作。

图片5

在图片5中的①，是一棵平衡二叉树，插入新节点F后，根节点A的左子树高度为3，右子树高度为1，BF=3-1=2>1，因此需要进行调整。其失衡节点为根节点A，以A的左孩子节点为轴进行旋转。使得以A为根节点的右子树成为节点B的右子树，也就是让A成为B的右孩子。因为节点B存在右子树，需让该右子树成为节点A的左子树，即让D成为A的左孩子。

所以所谓的LL型调整意思就是在最小失衡子树的左孩子的左子树上插入了新的结点。下图是通用的LL型调整的图。

图片6

在该图片6中的①，A的左子树高度为h+1，B的子树的高度为h。插入新节点后，A的左子树高度为h+2。先找到最小失衡子树的根A，以其左孩子结点B为轴，对不平衡结点A进行顺时针旋转（也称右旋）。右旋是让B顶替A的位置，并置A为B的右孩子，如果B存在右子树BR，则置BR为A的左子树。

该部分代码截图如下：

LL调整

小编这里提醒下，上图中用了空格+"\"进行换行，实则这是一个条件判断语句。

（2）RR型调整

在A的右孩子(R)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。下图是RR型的最简单形式。

图片7

显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转【左旋】一样。

这边来继续看一个最小平衡树应该注意的事项，通过下面的例子来看看。

图片8

在图片8中，在 ①所示的二叉树中插入键值为7的节点，得到②。很明显这是一棵非平衡二叉树。从键值为7这个插入节点往上看，发现对于键值为5的节点，其平衡因子BF=-2。故以该节点为根节点的树为最小非平衡二叉树，对其进行调整，最后得到③所示的平衡二叉树。

对于RR型，正好与LL型对称，对以A为根的最小失衡子树进行逆时针旋转（也称左旋)，如图所示。

图片9

RR型调整，表示在A的右孩子B的右子树BR（不一定为空）中插入结点【图中阴影部分所示】而导致不平衡（h表示子树的深度）。

这种情况调整如下：

① 将A的右孩子B提升为新的根结点

② 将原来的根结点A降为B的左孩子

③ 各子树按大小关系连接（AL和BR不变，BL调整为A的右子树）

代码截图如下：

RR调整

（3）LR型调整

由于在A的左孩子(L)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1变为2。总之，LR型指的是最小失衡子树的左孩子的右子树上插入了新的结点。处理办法为，首先找到以A为根的最小失衡子树，以该子树的左孩子结点B为轴，对右子树结点C进行左旋调整，使之变为LL型。再以C为轴，对不平衡结点A进行右旋调整。

我们先来看看最简单的例子。

图片10

在上图片9中的①，B的右子树上插入新节点C后，得到②。此时节点A的BF=2，需要对该树进行调整。由于调整后的树必须满足二叉搜索树的特征，故应将C作为根节点，B作为左孩子，A为右孩子。调整后的树的形状如③所示。

来看看下面的比较复杂的实例。

图片11

在图片10中的①这棵树，插入键值7，得到②。这是一棵非平衡树，需要进行调整。首先找到以键值8为根的最小失衡子树，以该子树的左孩子结点（键值为5）为轴，对右子树结点（键值为6）进行左旋调整（RR型调整），使之变为LL型，得到图③。以键值为8的根节点的左孩子节点（键值为6）为轴进行旋转。使得以键值为8的根节点的右子树成为键值为6的节点的右子树。因为键值为6的节点存在右子树，需让该右子树成为键值为8的节点的左子树，调整后得到图④。

下面是一般的LR型调整的变化图。