GESP 六级 · GESP 202309 C++ 六级 第 12 题

$N$ 个节点的二叉搜索树，其查找的平均时间复杂度为（ ）。

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

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

【考点】二叉搜索树结构｜平均情况时间复杂度分析｜平衡树性质

🎯 考纲定位：六级数据结构模块核心考点，卡住"只背结论不看前提"的学生——命题人用平均复杂度区分平衡树与非平衡树，检验你是否理解 BST 何时能 O(log N)。

🧠 解题思维：先确认 BST 性质（左小右大），再判断树形态：平衡时高度约 log₂N，平均查找步数≈高度，故 O(log N)；若树退化成链表则 O(N)。通法：遇到 BST 复杂度题，先问"是否保证平衡"，再推导。

🪤 陷阱拆解：A 项 O(1) 是哈希表特性，误用二叉树；B 项 O(N) 是极端情况，命题人故意放为干扰项，让你误以为"平均=最坏"；D 项 O(N²) 纯属凑数。最阴险的是 C 项看似正确，但仅当树平衡才成立——如果你只背"BST 平均 O(log N)"而忽略平衡前提，必掉坑。

🔄 反命题思维：若把"平均"换成"最坏"，答案变 B；若限定"随机插入"，答案仍为 C。刷到 BST 复杂度题，先自问：命题人想考平衡条件还是极端退化？