【数据结构】为什么AVL树查找总是O(log n)? | 408考研数据结构必看​

(AVL树的查找)

导读

大家好，很高兴又和大家见面啦！！！

在前面的内容中深入探讨了 ​​AVL树​​ 的插入与删除操作后，我们了解到其通过​​平衡因子​​的监控与​​旋转操作​​（LL、RR、LR、RL）来维持高度平衡，从而避免了树结构退化为链表的风险，为高效的数据操作奠定了基础。

然而，AVL树 的核心优势并不仅在于动态维护平衡的能力，更在于其能够提供的​​稳定且高效的查找性能​​。无论数据如何动态变化，AVL树 都能将其高度严格控制在​​对数级别​​，这使得查找操作的时间复杂度始终稳定在 ​​O(\log_2 n)​​。

​​核心问题​​：AVL树的高度究竟是如何被严格约束的？其查找效率卓越的数学本质是什么？

答案，就隐藏在 AVL树​​ 最小结点数的递推公式​​ n_h = n_{h-1} + n_{h-2} + 1之中。

• 那么这个递推公式从何而来？
• 其时间复杂度为什么能够稳定在 O(\log_2 n) ？

下面就让我一起来探讨一下这两个问题吧！！！

一、AVL树的查找

在 AVL树 上进行查找的过程与 BST 的查找相同。因此，在查找的过程中，进行关键字的比较次数不会超过树的深度。假设 AVL树 的树深为 h ，则 AVL树 的最少结点数为 n_h，我们不难得到以下数据：

• 当 h == 0 时，该 AVL树 为空树，其最少结点数为 n_0 = 0

graph TB
a((空树))

• 当 h == 1 时，该 AVL树 只存在根节点，其最少结点数为 n_1 = 1

graph TB
a((a))

• 当 h == 2 时，该 AVL树 只有一个孩子，其最少结点数为 n_2 = 2

graph TB
a((a))--->b((b))

• 当 h == 3 时，该 AVL树 有两个孩子和一个孙子，其最少结点数为 n_3 = 4

graph TB
a((a))--->b((b))
a--->c((c))
b--->d((d))

• 当 h == 4 时，该 AVL树 第二层有两个结点，第三层有三个结点，第四层有一个结点，其最少结点数为 n_4 = 7

graph TB
a((a))--->b((b))
a--->c((c))
b--->d((d))
b--->e((e))
c--->f((f))
d--->g((g))

• \cdots

对于一棵高度为 h 的 AVL树，我们要想保证该树的平衡，那么该树中的每一棵子树都需要满足以下条件：

• 左右子树的高度差的绝对值 <= 1
• 其中一棵子树的高度要保证最高，另一棵子树的高度要保证最低
• 子树中的结点要保证是最少的结点

那么以根结点的左右子树为例：

• 其中一棵子树的高度要尽可能的高，为了保证树的总高度为 h ，那么这棵子树的高度就应该为 h -1；要保证其结点数最少，那么该子树中的结点数为 n_{h-1}；
• 另一棵子树的高度哟啊尽可能的低，为了满足 AVL树 的平衡特性，那么该子树与另一棵子树的高度差的绝对值不能超过 1 ，即该子树的高度为 h - 2；要保证其结点数最少，那么该子树中的结点数为 n_{h - 2}

那么这棵树就可以视为三个部分：

• 根结点
• 高度为 h - 1 ，结点数为 n_{h - 1} 的子树
• 高度为 h - 2 ，结点数为 n_{h - 2} 的子树

graph TB
a((root<br>高度: h<br>平衡因子: 1))
b((left<br>高度: h - 1<br> 平衡因子: 1))
c((right<br>高度: h - 2<br>平衡因子: 0))
a--->b
a--->c
d((newnode<br>高度: 1<br>平衡因子: 0))
b--->d

那么该棵 AVL树 的总结点数为：n_{h} = n_{h - 1} + n_{h - 2} + 1

下面我们就借着前面的数据进行验证：

• 当 h == 2 时，h_2 = 2 = n_1 + n_ 0 + 1 = 1 + 0 + 1 = 2
• 当 h == 3 时，h_3 = 4 = n_2 + n_1 + 1 = 2 + 1 + 1 = 4
• 当 h == 4 时，h_4 = 7 = n_3 + n_2 + 1 = 4 + 2 + 1 = 7
• 当 h == 5 时，h_5 = n_4 + n_3 + 1 = 7 + 4 + 1 = 12

graph TB
a((a))--->b((b))
a--->c((c))
b--->d((d))
b--->e((e))
c--->f((f))
c--->g((g))
d--->h((h))
d--->i((i))
e--->j((j))
f--->k((k))
h--->l((l))

从上图中我们可以看到，当 h == 5 时，其最少的结点数也确实为 n_5 = 12；

二、AVL树的效率分析

由 AVL树 的最小结点数公式：n_h = n_{h - 1} + n_{h - 2} + 1 ，以及 n_{h - 1} > n_{h - 2}

同理，我们将 n_{h - 2} 继续展开，就能得到下一个不等式：

按照 AVL树 的最少结点递推公式不断展开，直到我们最终展开的结果为 n_2 + n_1 + 1；

注：本文中的举例是以根结点为第 1 层，对应的最少结点数 n_1 = 1；根结点的孩子为第 2 层，对应的最少结点数为 n_2 = 2；

因此我们就得到了最终的不等式：

这里我们不难发现 m 与 h 之间的关系为：2 * m = h - 1，即 m = \frac{h - 1}{2}；

现在我们将 m 的值带入即可得到 n_h > 2^{\frac{h - 1}{2}}

当 AVL树 的结点总数为 n 时，此时树的最大高度满足：

$$ \begin{align*} 2^{\frac{h - 1}{2}} &< n \ \frac{h - 1}{2} &< \log_2 n \ h &< 2*\log_2 n + 1 \end{align*} $$

也就是说，对于 n 个结点的 AVL树 的最大深度的量级为 O(\log_2 n)，因此，平均查找效率为 O(\log_2 n)

结语

通过今天的探讨，我们深入理解了 AVL树 能够提供稳定高效查找性能的数学根基。全文的核心可以概括为以下关键几步：

1. 平衡的代价： 为了维持严格平衡（任何节点左右子树高度差不超过1），AVL树 在构造时，高度为h的树所需的最少结点数 n_h 必须满足一个关键的递推关系：n_h = n_{h-1} + n_{h-2} + 1。 这个公式的直观理解是，一棵最“稀疏”的高度平衡树，由其根节点、一棵尽可能高的子树（高度 h-1）和一棵尽可能低但又满足平衡条件的子树（高度 h-2）构成。
2. 高度的约束： 基于上述递推关系，我们通过不等式放缩，推导出 n_h 大致大于 2^{\frac{h - 1}{2}}。 这意味着，当树的结点总数 n 固定时，树的高度 h 被严格限制在对数级别，即 h < 2 * \log_2n + 1
3. 效率的保证： 正是由于树高被约束在 O(\log_2 n)，从根到叶的查找路径长度最多也是对数级别。 因此，在 AVL树 上的查找、插入、删除操作的时间复杂度均能稳定在 O(\log_2 n)，这彻底避免了普通二叉搜索树在极端情况下退化为链表、性能骤降的风险。

总而言之，AVL树 通过精巧的平衡因子维护和旋转操作，以略微增加插入删除复杂度的代价，换取了查找性能的极致稳定，这正是其在大数据量场景下，作为数据库索引、高效字典等应用核心基础的魅力所在。

今天关于 AVL树 查找效率的深入分析就到这里。接下来，我们将一起继续探讨另一种应用广泛的自平衡二叉搜索树——红黑树，看看它是如何以一种不同的“平衡哲学”来保证高效性能的。

感谢您的阅读！如果本文对您有所帮助或启发，欢迎互动支持：

• 点赞 ⭐️：让我知道这份干货的价值。
• 关注 ➕：第一时间获取后续关于红黑树等数据结构的精彩解析。
• 收藏 💾：方便日后随时查阅复习。
• 转发 ➡️：分享给更多可能需要的朋友。

我也很想知道你的想法： 在您看来，AVL树 的这种“严格平衡”策略，与 红黑树 即将介绍的“近似平衡”策略，各有哪些优势和适用场景？欢迎在评论区留下您的见解！📝

我们下一篇再见！