GESP 八级 · GESP 202312 C++ 八级 第 24 题

在 $N$ 个元素的二叉排序树中查找一个元素，最好情况的时间复杂度是 $O(\log N)$。

拿到题先别急着背公式，把‘最好情况’四个字刻在脑子里：成功查找且目标就在根节点，比较次数就是1，跟树高没关系。

很多考生一看到二叉排序树就条件反射地写下O(log N)，其实那是‘平均情况’或‘平衡树最坏情况’的结论。这题专门考概念辨析，命题人用‘最好情况’这个词把那些只记结论不读定义的人卡住，选A就是掉进这个坑。

【考点】二叉排序树（BST）的时间复杂度辨析｜最好/平均/最坏情况的区别｜概念陷阱识别

GESP八级喜欢考算法复杂度的细节，尤其是‘最好、平均、最坏’这三档的区分。命题人为什么出这道题？因为很多学生背了‘二叉排序树查找是O(log N)’，却忘了这个结论成立的前提是‘平均情况’或者‘树保持平衡’。一旦树退化成链表（比如插入序列是1,2,3,4,5），最坏情况直接变成O(N)；而‘最好情况’——目标恰好是根节点——只需要一次比较，时间复杂度就是O(1)。题干特意用‘最好情况’来挖坑，就是看你能不能跳出肌肉记忆，真正理解定义。

解题心法：拿到题先锁定关键词‘最好情况’。在BST里，查找成功时，路径长度最短的情况就是根节点命中，比较次数=1，与N无关，所以是O(1)。如果题目问‘平均情况’，那要看树是否平衡，平衡时路径长度≈log₂N，平均O(log N)；如果问‘最坏情况’，树退化成链表，路径长度=N，最坏O(N)。这道题把‘平均’偷换成‘最好’，就是典型的命题视角陷阱。

避坑提醒：别一看到BST就写O(log N)，也别被‘O(log N)’这个漂亮的符号迷惑。记住：O(1)是常数级，跟N没关系；O(log N)是随着N增大而缓慢增长的；O(N)是线性增长。这题选A就是掉进‘只记结论不读定义’的坑里，而正确答案B才是真正理解了‘最好情况’的含义。

考频与趋势：二叉搜索树相关题目在题库中已考过183题，覆盖六级到八级多个级别，其中GESP八级就占了19题，说明这类概念辨析在八级中很常见。从历年分布看，2023年考了18题，2024年57题，2025年67题，2026年28题，整体呈上升趋势，尤其是2024-2026这几年，二叉树相关题目占比很高，命题人明显在加大这类题目的比重。

预测：基于近年考频和八级侧重算法细节的特点，未来GESP八级仍可能继续考BST的时间复杂度辨析，尤其是把‘最好/平均/最坏’混在一起出题，或者换一种说法（比如‘随机插入’‘特定序列’）来考最坏情况。暂无足够依据预测具体年份或题型变体，但‘概念陷阱’这一命题风格大概率会延续。