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

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

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

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

【考点】二叉排序树结构｜平衡树概念｜平均与最坏情况

1. 🎯 考纲定位

二叉排序树（BST）是《GESP 八级》数据结构模块的核心内容，命题人正是要卡住大量考生对"树的结构性质"的认知盲区——他们背了 BST 的定义，却把"二叉搜索树"误当成"平衡二叉树"，导致根本搞不清查找性能与树形结构的绑定关系。