1. 简介
在本文中，我们将对比二叉搜索树（BST）与AVL 树在构建过程中的时间复杂度差异。重点分析在不同输入场景下，构建这两种树结构的最坏情况与平均情况的时间复杂度。
在空间复杂度方面，不论是 BST 还是 AVL 树，构建过程中都需要 $ O(n) $ 的空间，无论输入数据如何排列。
2. 二叉搜索树与 AVL 树
在二叉搜索树（BST）中，每个节点的值都小于其左子树中所有节点的值，且小于或等于其右子树中所有节点的值。
BST 的设计初衷是为了实现高效的查找操作。然而，BST 的结构形态依赖于节点插入的顺序。在最坏情况下，BST 会退化为链表，查找复杂度退化为 $ O(n) $：
为了解决这个问题，引入了平衡树的概念。其中，AVL 树是一种自平衡二叉搜索树，其任意节点的左右子树高度差不超过 1：
该性质保证了 AVL 树的高度为 $ O(\log n) $，从而使得查找、插入、删除等操作的时间复杂度维持在 $ O(\log n) $。但为了维持平衡，插入操作可能需要进行旋转调整，这会带来额外的开销。
我们接下来将分析从数组 $ A = [a_1, a_2, \ldots, a_n] $ 构建 BST 和 AVL 树的复杂度。
3. 最坏情况下的复杂度分析
构建 BST 或 AVL 树的基本算法如下：
algorithm ConstructTree(A):
// INPUT
// A = [a1, a2, ..., an] - the numerical array holding the future nodes' values
// OUTPUT
// An AVL tree or a BST containing a1, a2, ..., an
T <- make an empty BST or AVL tree
Set a1 as the root of T
for i <- 2 to n:
x <- find the future parent node by searching for ai in T
if ai < x.value:
x.left <- Node(ai)
else:
x.right <- Node(ai)
return T
该算法从空树开始，依次插入数组中的每个元素。每次插入时，先查找其在树中的插入位置，然后插入为左或右子节点。
3.1 构建 BST 的最坏情况
当输入数组为非递减序列时（如 $ a_1 \leq a_2 \leq \ldots \leq a_n $），BST 会退化为链表，插入操作的时间复杂度变为 $ O(n) $。
插入第 $ i $ 个元素时，最坏情况下需要遍历前 $ i-1 $ 个节点。因此，总时间复杂度为：
$$ \sum_{i=1}^{n} (i-1) = \frac{n(n-1)}{2} \in O(n^2) $$
✅ **结论：BST 构建的最坏时间复杂度为 $ O(n^2) $**。
3.2 构建 AVL 树的最坏情况
AVL 树的插入操作由于树高始终为 $ O(\log n) $，每次插入最多需要遍历 $ O(\log i) $ 条边。
因此，总时间复杂度为：
$$ \sum_{i=1}^{n} O(\log i) = O(n \log n) $$
✅ **结论：AVL 树构建的最坏时间复杂度为 $ O(n \log n) $**。
⚠️ 注意：虽然 AVL 插入时可能需要旋转操作，但这些操作的时间是常数级的，不影响整体复杂度。
4. 平均情况下的复杂度分析
我们假设输入数组的所有 $ n! $ 种排列是等概率的。
4.1 BST 的平均情况
BST 中节点的平均深度决定了插入操作的平均时间复杂度。
设 $ D(n) $ 为 $ n $ 个节点的 BST 的平均节点深度，则其递推公式为：
$$ D(n) = n-1 + \frac{2}{n} \sum_{i=0}^{n} D(i) $$
解得 $ D(n) \in O(\log n) $，因此插入所有元素的总时间为：
$$ \sum_{i=2}^{n} O(\log (i-1)) = O(n \log n) $$
✅ **结论：BST 构建的平均时间复杂度为 $ O(n \log n) $**。
4.2 AVL 树的平均情况
AVL 树的结构固定为平衡树，节点深度始终为 $ O(\log n) $。因此，其平均节点深度也为 $ O(\log n) $。
插入所有元素的总时间复杂度同样为：
$$ O(n \log n) $$
✅ **结论：AVL 树构建的平均时间复杂度也为 $ O(n \log n) $**。
5. 总结
| 场景 | BST 构建复杂度 | AVL 树构建复杂度 |
|---|---|---|
| 最坏情况 | $ O(n^2) $ | $ O(n \log n) $ |
| 平均情况 | $ O(n \log n) $ | $ O(n \log n) $ |
✅ 总结：
- 最坏情况下，BST 构建效率远低于 AVL 树。
- 平均情况下，两者构建效率相当，均为 $ O(n \log n) $。
- 踩坑提醒：若输入数据有序或接近有序，BST 性能将严重下降，建议使用 AVL 或其他平衡树结构。