【Data Structure】平衡二叉搜索树 - AVL树

Posted by 西维蜀黍 on 2019-05-30, Last Modified on 2021-10-02

AVL 树

在 1962 年,俄罗斯数学家 G. M. Andel’son-Vel-skii 和 E. M. Landis 发明了第一种自平衡二叉搜索树,叫做 AVL 树。AVL 树必须维持如下平衡条件,对每个节点 n:节点 n 的左子树的高度与右子树的高度的差至多是 1

节点的左子树或者右子树的高度可以通过上面描述的步骤来计算。如果节点仅有一个子节点,则无子节点侧的高度为 -1。

下图展示了概念上 AVL 树节点的两侧子树高度需要保持的关系。

下面是一些二叉搜索树。节点中的数字代表着节点的值,左右两侧的数字代表着左右子树的高度。其中树(a)和树(b)是合法的 AVL 树,而树(c)和树(d)则不合法,因为树中不是所有的节点都满足 AVL 的平衡性质要求。

AVL 树的平衡

当创建一棵 AVL 树时,难点在于如何保证 AVL 的平衡性质要求,而不用关注对树的具体操作。

也就是说,无论是向树添加节点还是删除节点,最重要的事情就是保持树的平衡。AVL 树通过 “旋转操作(rotations)” 来保持树的平衡。旋转操作可以重塑树的拓扑结构来恢复树的平衡,更重要的是,重塑后的树依然符合二叉搜索树的性质要求。

当向一棵 AVL 树中插入一个新的节点时,需要经过两阶段的过程。首先,插入新节点的操作将使用与向 BST 树中插入新节点时使用的相同的查找算法。新的节点将做为一个叶子节点被添加到树中合适的位置,以满足 BST 的性质要求。在添加完节点后,将导致树的结构可能已经违背 AVL 树的性质要求。所以在第二个阶段中,将遍历访问路径,来检查每个节点左右子树高度。如果存在某节点的左右子树的高度差大于 1 时,则需要使用旋转操作来处理。

平衡二叉树的修正机制

当我们计算出某个结点的平衡因子的绝对值超过1时, 我们就要对其进行修正, 即通过平衡化的处理,使得不平衡的二叉树重新变得平衡。

平衡化操作的四种情况

AVL在构造的时候失衡以及平衡处理的方式包括以下四种:

LL失衡 - 右旋(Zig)

RR失衡 - 左旋(Zag)

LR失衡 - 先左旋后右旋(Zig-zag)

RL失衡 - 先右旋后左旋(Zag-zig)

第四种情况与第三种情况类似,为RL失衡,处理方式是先右旋后左旋(Zag-zig)。

平衡动图

这里我们可以很明显地看到平衡二叉树的优势所在: 使得查找的平均深度降低, 优化各个API的性能开销。

平衡二叉树和普通二叉搜索树区别主要在于动态方法(put,delete) ,而它们的静态方法(get,min,max,floor,ceiling, rank,select)基本是相同的。

Reference