GESP 六级 · GESP 202506 C++ 六级 第 20 题

如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构，这时其查找、插入、删除操作的时间复杂度会从理想情况下的 $O(\log n)$ 退化到 $O(n \log n)$。

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

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

【考点】二叉搜索树平衡性｜时间复杂度分析｜链表结构

本题考查GESP六级「数据结构」模块中二叉搜索树的时间复杂度分析。命题人专门设计这道题卡住那些背了「平衡树O(log n)」却混淆「单操作复杂度」与「n次操作总复杂度」的考生。

看到「二叉搜索树退化」先想高度变化：链表结构意味着树高为n，查找、插入、删除均需线性遍历，复杂度为O(n)。而O(n log n)是n次操作在平衡树上的总耗时，单步操作不可能达到。关键观察：命题人把「单步操作复杂度」偷换成了「n次操作总复杂度」。

选项A是典型语义陷阱。命题人利用考生对「复杂度退化」的模糊记忆：知道链表是O(n)，却错误地认为比O(log n)更慢就会变成O(n log n)。绝对化表述「所有节点都偏向一侧」暗示了最坏情况，但考生容易忽略「单步操作」与「批量操作」的区别。如果你只背结论「BST操作是O(log n)」，看到「退化」就下意识想「更慢」，就会掉进这个陷阱。

命题人视角：若把「单次操作复杂度」改为「n次操作总耗时」，答案就会变成A。刷到类似题时，先问自己「题目说的是单步还是批量？」——这才是区分O(n)与O(n log n)的本质。