GESP 六级 · GESP 202512 C++ 六级 第 13 题

在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（ ）。

bool find(Node* root, int x) {
    while (root) {
        if (root->val == x) return true;
        root = (x < root->val) ? root->left : root->right;
    }
    return false;
}

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

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

【考点】二叉排序树｜最坏情况｜时间复杂度

1. 考纲定位（考点定位）

GESP C++六级数据结构模块核心考点。命题人卡住的是"把BST想当然等同于平衡树"——学生一看到BST就默认O(log n)，却忘了BST本身允许退化。这题就是专门用来戳破这个幻觉的。