返回介绍

6.16.AVL平衡二叉搜索树

发布于 2024-06-08 22:44:10 字数 10099 浏览 0 评论 0 收藏 0

6.16.AVL平衡二叉搜索树

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

6.16.AVL平衡二叉搜索树.figure1

Figure 2

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

Nh=1+Nh1+Nh2N_h = 1 + N_{h-1} + N_{h-2}N​h​​=1+N​h−1​​+N​h−2​​

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

F0=0F1=1Fi=Fi1+Fi2 for all i2\begin{aligned} F_0 = 0 \\ F_1 = 1 \\ F_i = F_{i-1} + F_{i-2} \text{ for all } i \ge 2 \end{aligned}​F​0​​=0​F​1​​=1​F​i​​=F​i−1​​+F​i−2​​ for all i≥2​​

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

Nh=Fh+21,h1N_h = F_{h+2} - 1, h \ge 1N​h​​=F​h+2​​−1,h≥1

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

Nh=Φh+251N_h = \frac{\Phi^{h+2}}{\sqrt{5}} - 1N​h​​=​√​5​​​​​Φ​h+2​​​​−1

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

logNh+1=(H+2)logΦ12log5h=logNh+12logΦ+12log5logΦh=1.44logNh\begin{aligned} \log{N_h+1} = (H+2)\log{\Phi} - \frac{1}{2} \log{5} \\ h = \frac{\log{N_h+1} - 2 \log{\Phi} + \frac{1}{2} \log{5}}{\log{\Phi}} \\ h = 1.44 \log{N_h} \end{aligned}​logN​h​​+1=(H+2)logΦ−​2​​1​​log5​h=​logΦ​​logN​h​​+1−2logΦ+​2​​1​​log5​​​h=1.44logN​h​​​​

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文