AVL Tree

Definition

二叉平衡树,又称AVL树。它或者是一棵空树,或者是具有下列性质的树:

  1. 具备二叉排序树的所有性质;
  2. 左子树和右子树深度差的绝对值不超过1;
  3. 左子树和右子树都是二叉平衡树。

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。

平衡二叉树的前提是它是一棵二叉排序树。

距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树,称为最小不平衡子树。如下图所示,当插入结点37时,距离它最近的平衡因子的绝对值超过1的结点是58。
Screen Shot 2018-08-20 at 03.29.51.png


平衡二叉树实现原理

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

下面讲解一个平衡二叉树构建过程的例子。现在又a[10] = {3, 2, 1, 4, 5, 6, 7, 10,9,8}需要构建二叉排序树。在没有学习平衡二叉树之前,根据二叉排序树的特性,通常会将它构建成如下左图。虽然完全符合二叉排序树的定义,但是对这样高度达到8的二叉树来说,查找是非常不利的。因此,更加期望构建出如下右图的样子,高度为4的二叉排序树,这样才可以提供高效的查找效率。

Screen Shot 2018-08-20 at 03.31.15.png

现在来看看如何将一个数组构成出如上右图的树结构。 对于数组a的前两位3和2,很正常地构建,到了第个数“1”时,发现此时根结点“3”的平衡因子变成了2,此时整棵树都成了最小不平衡子树,需要进行调整,如下图图1(结点左上角数字为平衡因子BF值)。因为BF为正,因此将整个树进行右旋(顺时针),此时结点2成了根结点,3成了2的右孩子,这样三个结点的BF值均为0,非常的平衡,如下图图2所示。

Screen Shot 2018-08-20 at 03.32.17.png

然后再增加结点4,平衡因子没有改变,如上图图3。增加结点5时,结点3的BF值为-2,说明要旋转了。由于BF是负值,对这棵最小平衡子树进行左旋(逆时针旋转),如下图图4,此时整个树又达到了平衡。

Screen Shot 2018-08-20 at 03.32.34.png

继续增加结点6时,发现根结点2的BF值变成了-2,如下图图6所示。所以对根结点进行了左旋,注意此时本来结点3是结点3的左孩子,由于旋转后需要满足二叉排序树特性,因此它成了结点2的右孩子,如图7所示。

Screen Shot 2018-08-20 at 03.32.58.png

增加结点7,同样的左旋转,使得整棵树达到平衡,如下图8和9所示。
Screen Shot 2018-08-20 at 03.33.19.png

当增加结点10时,结构无变化,如图10所示。再增加结点9,此时结点7的BF变成了-2,理论上只需要旋转最小不平衡树7、9、10即可,但是,如果左旋转后,结点9变成了10的右孩子,这是不符合二叉排序树的特性的,此时不能简单的左旋。如图11所示。
Screen Shot 2018-08-20 at 03.33.37.png

仔细观察图11,发现根本原因在于结点7的BF是-2,而结点10的BF是1,也就是说,它们两个一正一负,符号并不统一,而前面的几次旋转,无论左还是右旋,最小不平衡子树的根结点与它的子结点符号都是相同的。这就是不能直接旋转的关键。 不统一,不统一就把它们先转到符号统一再说,于是先对结点9和结点10进行右旋,使得结点10成了9的右子树,结点9的BF为-1,此时就与结点7的BF值符号统一了,如图12所示。
Screen Shot 2018-08-20 at 03.34.00.png

这样再以结点7为最小不平衡子树进行左旋,得到如下图13。接着,插入8,情况与刚才类似,结点6的BF是-2,而它的右孩子9的BF是1,如图14,因此首先以9为根结点,进行右旋,得到图15,此时结点6和结点7的符号都是负,再以6为根结点左旋,最终得到最后的平衡二叉树,如图16所示。
Screen Shot 2018-08-20 at 03.34.06.png

通过这个例子,可以发现,当最小不平衡树根结点的平衡因子BF是大于1时,就右旋,小于-1时就左旋,如上例中的结点1、5、6、7的插入等。插入结点后,最小不平衡子树的BF与它的子树的BF符号相反时,就需要对结点先进行一次旋转以使得符号相同后,再反向旋转一次才能够完成平衡操作,如上例中结点9、8的插入时。


插入操作

在平衡二叉树进行插入操作时遇到的不平衡情况有多种,但是这么多种情况都可以分解为一下四中基础情景:把它叫做:左左、左右、右右、右左。

在解释这四种情景之前需要先明白一个定义:最小不平衡节点—插入一个节点之后,距离这个插入节点最近的不平衡节点就是最小不平衡节点。所有的旋转都是在最小不平衡节点的基础上进行的。

继续解释四种情景命名意义:

  1. 左左:节点插入在最小不平衡节点的左子树的左子树上。
  2. 左右:节点插入在最小不平衡节点的左子树的右子树上面。 
  3. 右右:节点插入在最小不平衡树的右子树的右子树上面。  
  4. 右左:节点插入在最小不平衡树的右子树的左子树上面。

解决办法为:
Screen Shot 2018-08-19 at 23.40.41.png

Screen Shot 2018-08-19 at 23.41.03.png

Screen Shot 2018-08-19 at 23.40.50.png

Screen Shot 2018-08-19 at 23.41.09.png

删除操作

删除的流程如下:

  1. 拿到要删除的数字 value,从根节点开始比对,知道找到一个要删除的节点:currNode

  2. 从左子树中找到一个最大值(左子树中的值都比 currNode 小):targetNode(如果左子树为空,那就直接把 right 节点上位;如果 right 也是空的,那就直接删掉 currNode 就好了)

  3. 把 targetNode 放到 currNode 的位置上:因为每个 节点都有 parent、left、right 三个关联点,要仔细处理

  4. 和 插入类似,从 targetNode 开始一路向上,找到第一个失衡点。此时只有 LL 和 RR 两种失衡情况,判断起来相对容易些

Donate article here