GESP 八级 · GESP 202403 C++ 八级 第 8 题

在有 $n$ 个元素的二叉排序树中进行查找，其最好、最差时间复杂度分别为（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二叉排序树（BST）｜时间复杂度分析｜平衡与非平衡树

看到题先想“二叉排序树”的定义：左子树所有节点值 < 根节点 < 右子树所有节点值。查找本质是“二分决策”——目标值比根小就往左，比根大就往右，相等即找到。所以最好情况是目标值就在根节点，一步到位 → O(1)；最坏情况是树退化成链表（比如按顺序插入 1,2,3,...,n），此时查找第 n 个元素或不存在元素必须遍历所有 n 个节点 → O(n)。

错误选项都源于对“平衡性”的混淆。B、C 把 BST 默认当成平衡树（像 AVL/红黑树）来算，忽略了题目未说明平衡的前提；D 把最好情况误判为 O(log n)，其实只要目标在根就是 O(1)。最阴险的是“二叉排序树”这个表述——它只保证有序性，不保证高度，命题人就是用这个模糊词卡住只背结论的考生。

如果题目改成“在平衡二叉排序树中查找”，答案立刻变成 C（O(log n), O(log n)）。刷到 BST 相关题，先问自己“这棵树是否平衡？”——不平衡就按链表想（O(n) 最坏），平衡就按树高想（O(log n) 最坏）。