6.16.AVL平衡二叉搜索树

在我们继续之前，我们来看看执行这个新的平衡因子要求的结果。我们的主张是，通过确保树总是具有 -1,0或1 的平衡因子，我们可以获得更好的操作性能的关键操作。 让我们开始思考这种平衡条件如何改变最坏情况的树。有两种可能性，一个左重树和一个右重树。 如果我们考虑高度0,1,2和3的树，Figure 2 展示了在新规则下可能的最不平衡的左重树。

Figure 2

看树中节点的总数，我们看到对于高度为0的树，有1个节点，对于高度为1的树，有1 + 1 = 2个节点，对于高度为2的树 是1 + 1 + 2 = 4，对于高度为3的树，有1 + 2 + 4 = 7。 更一般地，我们看到的高度h(Nh) 的树中的节点数量的模式是：

这种可能看起来很熟悉，因为它非常类似于斐波纳契序列。 给定树中节点的数量，我们可以使用这个事实来导出AVL树的高度的公式。 回想一下，对于斐波纳契数列，第i个斐波纳契数字由下式给出：

一个重要的数学结果是，随着斐波纳契数列越来越大，Fi/Fi-1 的比率越来越接近黄金比率 Φ= (1 +√5)/2。 如果要查看上一个方程的导数，可以查阅数学文本。 我们将简单地使用该方程来近似 Fi，如 Fi =Φ^i / 5。 如果我们利用这个近似，我们可以重写 Nh 的方程为：

通过用其黄金比例近似替换斐波那契参考，我们得到：

如果我们重新排列这些项，并取两边的底数为2的对数，然后求解 h，我们得到以下推导：

这个推导告诉我们，在任何时候，我们的AVL树的高度等于树中节点数目的对数的常数（1.44）倍。 这是搜索我们的AVL树的好消息，因为它将搜索限制为O(logN）。