Python平衡二叉树(AVL树)

平衡二叉树是一种特别形式的二叉搜索树,它采用平衡化旋转来避免二叉搜索树出现退化的情况。

二叉搜索树的效率

理论上来说,对二叉搜索树进行一次操作的时间复杂度是 O(lgn),这是因为二叉搜索树在理想状态下是近似于完全二叉树的。但是,在实际操作中,二叉搜索树很容易退化成线性的数据结构。例如,往二叉搜索树中插入一个有序序列,这时会得到一条链,如图 1 所示。
二叉搜索树退化成线性
图 1:二叉搜索树退化成线性

这时候,对二叉搜索树进行操作的平均时间复杂度就会退化成 O(n)。左右子树的大小相差巨大的二叉搜索树,就处于非常不平衡的状态。这样的状态会使操作的时间复杂度大大提高。为了维持二叉搜索树的平衡状态,就出现了不同的平衡二叉树算法。

AVL树

本节教程要讲到的平衡二叉树,又称为 AVL 树。它维持二叉搜索树平衡的根本在于持续维护这样一个性质:二叉搜索树中,每一个节点的左右子树深度差的绝对值不大于1。

举例来说,图 2(a)所示为 AVL 树,而图 2(b)所示则不是 AVL 树。

图 2:两棵二叉树

那么,如何判断一棵树是否符合 AVL 树的性质?答案就是维护每个节点的平衡因子。每个节点的平衡因子即为节点左子树的深度减去右子树的深度得到的差。在符合 AVL 性质的情况下,平衡因子只能取 -1、0、1。

正因为这样,在插入或删除一个节点之后,要从插入或删除的位置沿通向根的路径回溯,更新这些经过的节点的平衡因子。在检测到当前节点的平衡因子的绝对值大于1时,停止回溯,根据回溯路径中当前节点以及当前节点深度+1 和深度+2 两层节点的位置,选择旋转方法对二叉树的结构进行调整。

如果一棵平衡二叉树中的节点发生了变化,使二叉树不再平衡,此时需要采用平衡化旋转来调整树的结构,使得在不破坏二叉搜索树性质的情况下,让二叉树重新达到平衡。

平衡化旋转分为两种:单向旋转和双向旋转。如果回溯路径中当前节点以及下两层节点处于一条直线上,就可以采用单向旋转。如果在下两层的节点中,每一个节点都是父亲节点的右孩子,那么如图 3 所示,此时采用单向左旋。
单向左旋
图 3:单向左旋

由于此处 A<B<C,所以左旋后并不破坏二叉搜索树的性质,而刚好使得平衡因子恢复到符合 AVL 树性质的大小。

这样的过程同样可以用图来展示。举例来说,在图 4 这样一棵平衡二叉树中插入节点后,整棵树就变得不平衡了。每个节点上方的数字就是该节点的平衡因子,而长方形代表子树,长方形里面的式子等于它的深度。
插入节点后平衡因子变化
图 4:插入节点后平衡因子变化

要想调整二叉树的结构,这里就要用到平衡左旋了。我们取每一棵子树的根节点来代表这一整棵子树,用一共 5 个节点来演示单向左旋的过程。图 5 所示就是单向左旋的效果。
单向左旋
图 5:单向左旋

平衡树的结构最后被调整成了图 6 所示这样,而平衡因子也重新变得符合 AVL 树性质了。
调整完毕
图 6:调整完毕

同样的道理,如果需要进行平衡旋转时,当前节点的下两层节点都是父节点的左孩子,那么就需要采用单向右旋。单向右旋的道理和单向左旋非常相似,下面就主要用图来演示,不多做讲解了。单向右旋的过程如图 7~图 9 所示。
单向右旋
图 7:单向右旋
插入节点后平衡因子变化
图 8:插入节点后平衡因子变化
单向右旋
图 9:单向右旋

同样,此处 A<B<C,所以右旋后并不破坏二叉搜索树的性质。

下面看看如何用代码实现单向平衡旋转:
#单向左旋函数,其中parent是p的父节点
def SingleTurnL(parent, p):
    q = p.right #找到下一层的节点
    #重新连接子树的位置
    p.right = q.left
    q.left = p
    if p == parent.left: #把q连接到原来p的父节点
        parent.left = q
    else:
        parent.right = q
#单向右旋函数,其中fa是p的父节点
def SingleTurnR(parent,p):
    q = p.left
    #重新连接子树的位置
    p.left = q.right
    q.right = p
    if p == parent.left: #把q连接到原来p的父节点
        parent.left = q
    else:
        parent.right = q

双向旋转实际上是进行两次不同方向的单向旋转操作。在当前节点以及下两层的节点构成折线形状时,需要进行双向旋转。根据进行不同方向单向旋转的先后顺序,双向旋转也被分为两类:先左后右双向旋转和先右后左双向旋转。

在经过的回溯路径中,如果深度为当前节点深度+1 的节点是当前节点的左孩子,而深度为当前节点深度+2 的节点是深度+1 层节点的右孩子时,使用先左后右双向旋转。

图 10 所示为旋转的过程。可以看出,在调整二叉树结构的过程中,先进行一次单向左旋,再进行一次单向右旋。
先左后右双向旋转
图 10:先左后右双向旋转

根据原本的结构可以推断出,B<A<C,经过双向旋转后,二叉搜索树的性质仍然保留着。把每个节点的子树用长方形表示出来,我们再来模拟一下二叉搜索树的平衡被破坏时的情况(见图 11)。
插入节点后平衡因子变化
图 11:插入节点后平衡因子变化

在破坏之后,为了维持二叉搜索树的平衡,我们进行先左后右双向旋转。首先我们要对 A、B 以及它们的子树做单向左旋,如图 12 所示。
单向左旋
图 12:单向左旋

对 A、B 的单向左旋结束后,把 A 与 C 相连,然后再对 A 和 C 做单向右旋。如图 13 所示,在单向右旋的过程中,B 和 B 的子树被看作一个整体。
单向右旋
图 13:单向右旋

经过两次旋转后,二叉树又重新变得平衡了。按同样的规律,先右后左双向旋转适用于这种情况:深度为当前节点深度+1 的节点是当前节点的右孩子,而深度为当前节点深度+2 的节点是深度+1 层节点的左孩子。

这种情况下,先对 A、B 两节点进行单向右旋,再对 A、C 两节点进行单向左旋,如图 14 所示。
先右后左双向旋转
图 14:先右后左双向旋转

同样地,我们以图示的形式把旋转过程展现出来。如图 15 所示,在二叉树中插入节点后,二叉树的平衡性被破坏了。
插入节点后平衡因子变化
图 15:插入节点后平衡因子变化

把节点A、B单独拿出来进行单向右旋,如图 16 所示。
单向右旋
图 16:单向右旋

把 B 和它的子树看成一个整体,作为 A 的右子树,再对节点 A、C 进行单向左旋,如图 17 所示。
单向左旋
图 17:单向左旋

这样,二叉树又重新变得平衡了。而在写好了单向旋转函数的基础上,双向旋转函数的逻辑就很简单了,即调用两次单向旋转函数。

代码可以这么写:
#先左后右双向旋转,fa是p父节点的位置,p是当前节点
def DoubleLR(fa,p):
    SingleTurnL(p,left[p]) #调用单向左旋函数
    SingleTurnR(fa,p) #调用单向右旋函数

#先右后左双向旋转,fa是p父节点的位置,p是当前节点
def DoubleRL(fa,p):
    SingleTurnR(p,right[p]) #调用单向右旋函数
    SingleTurnL(fa,p) #调用单向左旋函数

到这里,维持 AVL 树平衡的4种旋转方法就学习完毕了。有了这些旋转方法,再加上前面所学到的二叉搜索树基本操作函数,就可以编写出一棵完整的平衡二叉树了。除 AVL 树,还有 TREAP(树堆)、红黑树等数据结构,都是以维持二叉搜索树平衡的宗旨来设计的。