引言

二叉搜索树其实非常常用，但是......我好像从来没写过，一直用的 STL 的模板。为一手写过的二叉树可能就是堆了吧。趁着可靠大先辈学的时候稍微看了一下，大致理解了。（这么晚看这个真的该自裁）

Reference

由于内容...十分基础，所以直接放链接了，我觉得写的比较好的教程：

• https://oi-wiki.org/ds/bst/

模板题：洛谷 P5076

传送门: https://www.luogu.com.cn/problem/P5076

// 普通二叉搜索树模板
#include <iostream>
#define fuck cout << __LINE__ << endl

using namespace std;

const int maxn = 1e4+5;
int cnt = 0;
struct node { int val, cnt, size, l, r; } t[maxn];

void print(int u) {
    if (!u) return;
    print(t[u].l);
    for (int i = 0; i < t[u].cnt; i ++) cout << t[u].val << " ";
    print(t[u].r);
}

// 引用 u 的好处是能够在最后直接把新建的节点的编号赋给父亲的某个儿子
void insert(int &u, int val) {
    if (!u) {
        t[u = ++ cnt] = (node) {val, 1, 1, 0, 0};
        return;
    }
    t[u].size ++;
    if (t[u].val == val)
        t[u].cnt ++;
    else if (val < t[u].val)
        insert(t[u].l, val);
    else
        insert(t[u].r, val); 
}

int query_last(int u, int val, int ans) {
    if (val > t[u].val) {
        if (!t[u].r) return t[u].val;
        return query_last(t[u].r, val, t[u].val);
    } else {
        if (!t[u].l) return ans;
        return query_last(t[u].l, val, ans);
    }
}

int query_next(int u, int val, int ans) {
    if (val < t[u].val) {
        if (!t[u].l) return t[u].val;
        return query_next(t[u].l, val, t[u].val);
    } else {
        if (!t[u].r) return ans;
        return query_next(t[u].r, val, ans);
    }
}

int query_rank(int u, int val) {
    if (u == 0) return 1;
    if (t[u].val == val) return t[t[u].l].size + 1;
    if (val < t[u].val) return query_rank(t[u].l, val);
    return t[u].cnt + t[t[u].l].size + query_rank(t[u].r, val);
}

int query(int u, int rank) {
    if (rank > t[t[u].l].size && rank <= t[t[u].l].size + t[u].cnt) return t[u].val;
    if (rank <= t[t[u].l].size) return query(t[u].l, rank);
    return query(t[u].r, rank - t[t[u].l].size - t[u].cnt);
}

signed main() {
    int n; cin >> n;
    while (n --> 0) {
        int a, m; cin >> a >> m;
        if (a == 1) {
            cout << query_rank(1, m) << endl;
        } else if (a == 2) {
            cout << query(1, m) << endl;
        } else if (a == 3) {
            cout << query_last(1, m, -2147483647) << endl;
        } else if (a == 4) {
            cout << query_next(1, m, 2147483647) << endl;
        } else if (a == 5) {
            if (!cnt) {
                t[++ cnt] = (node) {m, 1, 1, 0, 0};
            } else {
                int a = 1;
                insert(a, m);
            }
        }
        // print(1);
    }
    return 0;
}

说几个要注意的点：

1. 插入第一个点的时候要特判
2. 插入使用了一个引用传参的 trick，可以用于方便的给新建节点的父节点赋值
3. 前继搜索和后继搜索的时候情况比较复杂，可能出现「如果递归下去就可能不再是答案的情况」，比方说「寻找后继，当前的节点的值却比搜索值小，但却没有右儿子（即这个节点不能作为答案，并且没有符合要求的子节点可以递归）」，所以我们会使用第三个参数 ans 记录上一个符合要求的答案，碰到这种情况直接 return