BST

Intro

BST 是二叉搜索树的简称，我们定义 BST 上每一个节点都有一个关键值，（就是点权好吧）。

BST 上每一个节点都满足以下性质：

1. 该节点所有左子树的关键值都小于等于该节点的关键值。
2. 该节点所有右子树的关键值都大于等于该节点的关键值。

实现

建立

出于避免越界，减少特殊判断的目的，我们一般会往 BST 里边丢一个负无穷的关键值和一个正无穷的关键值，仅有这两个节点组成的 BST 就是一颗空的 BST。

接下来我们假设 BST 里不会出现关键值相同的节点。

struct Bst {
    int l, r; // 左子树右子树的下标
    int val; // 关键值
}a[N];

int tot, rt;

int New(int val) {
    a[++tot].val = val; // 把一个关键值插入
    return tot; // 返回节点编号
}

void build() {
    New(-INF); // 先插入负无穷
    New(INF); // 再插入正无穷当负无穷的右子树
    rt = 1, a[1].r = 2; // 根弄成 1，1 的后继下标当然是 2 咯
}

查找

在 BST 中查找是否存在关键值为 $\operatorname{val}$ 的节点。

设变量 $p$ 等于根节点，执行：

1. 如果 $p$ 的关键值等于 $val$，已经找到了。
2. 如果 $p$ 的关键值小于 $val$，如果 $p$ 的右子树为空说明不存在 $val$，否则就进去找 $val$。
3. 如果 $p$ 的关键值大于 $val$，如果 $p$ 的左子树为空说明不存在 $val$，否则就进去找 $val$。

int get(int p, int val) {
    if(p == 0) return 0; // 都找不到了直接返回呗
    if(val == a[p].val) return p; // 找到了就直接返回呗
    return val < a[p].val ? get(a[p].l, val) : get(a[p].r, val); // 执行操作
}

插入

在 BST 中插入一个新值，和查找类似。找到要走向的 $p$ 的子节点为空，说明 $val$ 不存在，直接建立关键值为 $val$ 的新节点作为 $p$ 的子节点。

void insert(int &p, int val) {
    if(p == 0) {
        p = New(val);
        return ;
    }
    if(val == a[p].val) return ;
    if(val < a[p].val) ins(a[p].l, val);
    else insert(a[p].r, val);
}

求前驱后继

先谈谈后继吧：

后继是指在 BST 中关键值大于 $val$ 的前提下，关键值最小的节点。

我们定义这个节点的编号为 $ans$，跑去查找 $val$，会有以下结果：

1. 没有找到 $val$，这就说明 $val$ 的后继已经在经过的节点中更新过了，$ans$ 即为所求。
2. 找到了 $val$ 的节点 $p$，如果 $p$ 没有右子树，说明你已经找到了，$ans$ 即为所求。
3. 好吧 $p$ 它有右子树，没关系，我们进入右子树，然后向左子树跑，去找一个最贴近 $val$ 的值，然后这个 $val$ 对应的 $p$ 就是后继所在的节点。

int getnxt(int val) {
    int ans = 2; // 我觉得吧，答案节点要从 2 开始防止判断边
    int p = rt; // 从根开始找
    while(p) {
        if(val == a[p].val) { // 如果找到了 val
            if(a[p].r > 0) { // 如果还有右子树
                p = a[p].r; // 进入它的右子树，然后往左边跑去找更合适
                while(a[p].l > 0) p = a[p].l; // 往左边跑
                ans = p; // 更新下 ans
            }
            break;
        }

        if(a[p].val > val && a[p].val < a[ans].val) ans = p; // 沿途尝试更新 ans
        p = val < a[p].val ? a[p].l : a[p].r;
    }

    return ans;
}

找前驱同理。

int getpre(int val) {
    int ans = 1;
    int p = rt;
    while(p) {
        if(val == a[p].val) {
            if(a[p].l > 0) {
                p = a[p].l;
                while(a[p].r > 0) p = a[p].r;
                ans = p;
            }
            break;
        }

        if(a[p].val < val && a[p].val > a[ans].val) ans = p;
        p = val > a[p].val ? a[p].l : a[p].r;
    }

    return ans;
}

删除

删除关键值为 $val$ 的节点 $p$。还是先跑去查找 $val$，得到节点 $p$，如果 $p$ 的子节点个数小于 2，直接把 $p$ 删掉，然后把 $p$ 的子节点接到 $p$ 的位置就可以了。

好吧，$p$ 既有左子树又有右子树，我们直接去找出 $val$ 的后继节点 $nxt$，因为 $nxt$ 是没有左子树的（不然要你当什么后继？），直接把 $nxt$ 删掉，然后让 $nxt$ 的右子树顶到 $nxt$ 的位置，最后把 $nxt$ 丢到 $p$ 的位置上，然后删除 $p$。

void del(int &p, int val) { 
    if(p == 0) return ;
    if(val == a[p].val) {
        if(a[p].l == 0) p = a[p].r; 
        else if(a[p].r == 0) p = a[p].l;  
        else {
            int nxt = a[p].r;
            while(a[nxt].l > 0) nxt = a[nxt].l;
            del(a[p].r, a[nxt].val);
            a[nxt].l = a[p].l, a[nxt].r = a[p].r;
            p = nxt;
        }
        return ;
    }
    if(val < a[p].val) del(a[p].l, val);
    else del(a[p].r, val);
}

BST 的期望时间复杂度是 $\mathcal{O}(\log n)$ 的，坑人的是，BST 很容易退化，出题人随手扔给你一个有序的序列，BST 直接变成了 $\mathcal{O}(n)$。然后我们就只能在聊天框里发个 gg 了这样还能在 Hypixel 服务器里加上 5rp 值。

我们称这种左右子树差很大的 BST 是不平衡的，我们可以用一些奇妙的方法把它弄得平衡，怎么弄平衡呢？看下一篇博文吧。