在上一节中我们讨论了建立一个二叉搜索树。我们知道,当树变得不平衡时 get
和 put
操作会使二叉搜索树的性能降低到 O(n)
。在这一节中我们将看到一种特殊的二叉搜索树,它可以自动进行调整,以确保树随时都保持平衡。这种树被称为 AVL
树,命名源于其发明者:G.M. Adelson-Velskii 和 E.M. Landis。
AVL
树实现抽象数据类型 Map
就像一个普通的二叉搜索树,唯一不同的是这棵树的工作方式。为实现我们的 AVL
树我们需要在树中的每个节点加入一个平衡因子并跟踪其变化情况。我们通过比较每个节点的左右子树的高度完成比较。更正式地讲,我们定义一个节点的平衡因子为左子树和右子树的高度之差。
$$balanceFactor = height(leftSubTree) - height(rightSubTree)$$
利用以上对平衡因子的定义,如果平衡因子大于零,我们称子树“左重”( left-heavy
)。如果平衡因子小于零,那么子树“右重”( right-heavy
)。如果平衡因子为零,则树是完全平衡的。为实现 AVL
树,目的是得到一棵平衡的树,我们定义平衡因子如果是-1,0 或 1,那么这棵树是平衡的。一旦树中节点的平衡因子超出了这个范围,我们需要有一个把树恢复平衡的过程。图 1 是一个不平衡的“右重”树的例子,其中每个节点都标注了平衡因子。
图 1:一棵标注了平衡因子的不平衡的右重树
在我们继续进行之前让我们看看引入这个新的平衡因子的结果。我们的要求是,确保树上的平衡因子始终为-1,0 或 1。我们可以通过对键的操作得到更好的时间复杂度。首先,我们要思考如何利用这个平衡条件去改变最坏情况下的树。有两种可能性需要考虑,左重树和右重树。如果我们考虑树的高度为 0,1,2 和 3,图 2 举出了在新规则下可能出现的最不平衡的左重树的例子。
图 2:最坏情况下的左重 AVL
树
让我们看看树上的节点的总数。我们看到一棵高度为 0 的树有 1 个节点,一个高度为 1 的树有 1 + 1 = 2 个节点,一个高度为 2 的树有 1 + 1 + 2 = 4个节点,一棵高度为 3 的树有 1 + 2 + 4 = 7个节点。概括起来,高度为 h
的树的节点数(N h )为:
$$N_h = 1 + N_{h-1} + N_{h-2}$$
可能你很熟悉这个公式,因为它和斐波那契序列非常相似。我们可以利用这个公式通过树中的节点的数目推导出一个 AVL
树的高度。在我们的印象中,斐波那契数列与斐波那契数的关系为:
$$F_0 = 0$$
$$F_1 = 1$$
$$F_i = F_{i-1} + F_{i-2} /text{ for all } i /ge 2$$
数学中一个重要的结果是,随着斐波那契序列的数字越来越大,F i / F i −1 越来越接近于黄金比例Φ:
$$Φ = /frac{1 + /sqrt{5}}{2}$$
如果你想看到上式的推导过程你可以查阅相关的数学资料。我们简单地将这个方程近似为:
$$F_i : F_i =Φ^i//sqrt{5}$$
如果利用这种近似我们可以将 N h 的方程改写为:
$$N_h = F_{h+2} - 1, h /ge 1$$
通过黄金比例近似代替斐波那契数列的项我们可以得到:
$$N_h = /frac{Φ^{h+2}}{/sqrt{5}} - 1$$
如果我们整理这些方程的项,并且两边都以 2 为底取对数,然后求解 h
,则可以导出:
$$/log{N_h+1} = (H+2)/log{Φ} - /frac{1}{2} /log{5}$$
$$h = /frac{/log{N_h+1} - 2 /log{Φ} + /frac{1}{2} /log{5}}{/log{Φ}}$$
$$h = 1.44 /log{N_h}$$
这个推导过程告诉我们,在任何时候我们的 AVL
树的高度等于树中节点数以 2 为底的对数的常数(1.44)倍。这对我们搜索 AVL
树来说是好消息因为它限制了搜索的复杂度到 O(logN)。