GESP 八级 · GESP 202409 C++ 八级 第 19 题

二叉排序树的查找操作的平均时间复杂度，正比于树的高度。

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

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

【考点】二叉排序树｜树高｜时间复杂度

A. 正确

【1. 考纲定位】GESP 八级数据结构模块，命题人专卡"平衡性"误区——许多考生死记 O(log n) 却忽略树高可退化为 O(n) 的极端情况。

【2. 解题思维】二叉排序树查找本质是沿比较路径从根节点向下遍历，每层比较一次，路径长度≤树高，故时间复杂度 O(h) 与树高线性相关；算法题中"最坏/平均/随机"复杂度需结合树形态具体分析。

【3. 陷阱拆解】错项常设"平均即对数级"陷阱，利用考生混淆"平衡树"与"任意 BST"；更阴险的是把"正比"偷换为"等于"，树高为 n 时复杂度仍为 O(n)，命题人正是用绝对化表述诱导误判。

【4. 反命题思维】若改命题为"平衡二叉搜索树平均查找复杂度为 O(log n)"则正确，或问"最坏情况是否仍为 O(log n)"则错误；刷题时先反问自己"命题人想考我哪个概念边界"。