Structure 分类

何为二叉搜索树（Binary Search Tree, BST）：二叉，说明了这棵树是棵二叉树；搜索，说明这棵树有搜索的功能。接下来我们通过一个实例来理解一下这里搜索的意思。

假如你有一个序列，然后我要询问你一个问题：和是不是在这个序列当中。如果我们不考虑任何优化，那么暴力的做法就是一个个比对，直到比对上或者序列结束，复杂度。当数据规模小的时候还能够接受，数据规模一大就显得有点太过复杂。当然了，有人会说可以用 STL 里面的set解决这个问题，如下列所示代码：

#include <bits/stdc++.h>

using namespace std;

set<int> seq;

int main()
{
    int n;
    cin >> n;
    while (n--) {
        int tmp;
        cin >> tmp;
        seq.insert(tmp);
    }
    int q;
    cin >> q;
    while (q--) {
        int tmp;
        cin >> tmp;
        if (seq.find(tmp) == seq.end()) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
        }
    }
}

Andy Shen2023/7/12大约 14 分钟