GESP 六级 · GESP 202403 C++ 六级 第 23 题

二叉搜索树的查找操作的时间复杂度是 $O(N)$。

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

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

【考点】二叉搜索树｜平均时间复杂度｜最坏时间复杂度

1. 🎯 考纲定位

GESP 六级《数据结构》模块第 4.2 节"二叉搜索树的基本操作"。命题人专门在此处埋雷，就是要卡住那些死背"二叉搜索树查找是 O(log N)"的考生——六级及以上才开始系统学 BST，很多学生把平衡二叉树（AVL/红黑）的性质当成普通 BST 的通用性质，这道题就是检验你是否真懂 BST 的基本形态与平衡树的区别。