GESP 六级 · GESP 202312 C++ 六级 第 22 题

二叉搜索树查找的平均时间复杂度为 $O(\log N)$。（ ）

这道题考二叉搜索树（BST）的平均查找时间复杂度。拿到题先抓‘平均’二字：命题人想让你区分期望与最坏情况。随机插入时树高期望为O(log N)，所以平均复杂度就是O(log N)。

最容易错选B，原因是把‘平均’当成‘最坏’或‘任意情况’。BST退化成链表时最坏要O(N)，但题干限定的是平均情况。若把题肢改成‘任意二叉搜索树’，答案立刻变错，这就是偷换概念。

【考点】二叉搜索树（BST）的性质｜查找时间复杂度｜平均与最坏情况的区别

【概念人话版】二叉搜索树有个铁律：左子树所有节点都小于根，右子树所有节点都大于根。顺着这个规则往下找，每次都能把一半多的节点排除掉，所以理想情况下找一次就能砍掉一半搜索空间。

【命题人怎么挖坑】这题的坑就在‘平均’二字。命题人故意不写‘最坏’，也不写‘随机插入’，而是直接断言‘平均时间复杂度为O(log N)’。很多学生会想：‘万一树退化成链表呢？那不是O(N)吗？’于是慌里慌张选B。其实命题人考的是数学期望：对随机插入生成的BST，树高的期望是O(log N)，因此平均查找次数也是O(log N)。若把题肢改成‘任意二叉搜索树’，答案立刻变错，这就是典型的偷换概念。

【思考心法】拿到这类题先问自己三个问题： 1）树是否平衡？（BST不一定平衡，但随机插入的期望高度是log N） 2）问的是‘平均’还是‘最坏’？（平均看期望，最坏看极端退化） 3）有没有可能退化成链表？（有可能，但那只是极端情况，不影响平均）

【具体怎么算】对N个节点随机插入的BST，期望树高约为O(log N)。查找时每次比较能排除一半以上节点，所以平均比较次数就是O(log N)。若树是平衡的（如AVL、红黑树），最坏情况也保持O(log N)；但普通BST的最坏情况是O(N)，不过题干问的是平均，所以答案仍是O(log N)。

【避坑提醒】选错B的考生往往混淆‘平均’与‘最坏’：BST退化成链表时查找需O(N)，但这是极端情况；命题人用绝对化表述‘平均时间复杂度为O(log N)’精准卡住——你答‘不一定’就错了，因为随机插入的期望确实收敛到O(log N)。若把题肢改成‘任意二叉搜索树’，答案立刻变错，这就是偷换概念。

【考频与趋势】二叉树基础在题库中占比最高，共220题，其中2025年达67题、2024年60题，呈明显上升趋势；二叉树应用185题，2025年66题、2024年57题；BST专题183题，2025年67题、2024年57题。搜索专题仅1题（2009年NOIP普及组），几乎未考。可见命题人近年偏爱在GESP六级、七级、八级以及CSP提高级中考察BST与平衡树相关概念。

【预测】基于数据，未来GESP六级、七级、八级以及CSP提高级仍会高频出现BST平均/最坏复杂度辨析题，且更可能以‘随机插入’‘期望高度’等表述替代直白的‘平均’，增加理解难度。暂无足够依据预测是否会引入新题型（如动态平衡树查找），因为搜索专题至今仅1题，数据支撑不足，故不臆测。

综上，题干断言‘二叉搜索树查找的平均时间复杂度为O(log N)’是正确的，答案选A。