BST

ShelTeR_Pr1me · 2022-08-22 10:13:48 · 个人记录

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 是不平衡的，我们可以用一些奇妙的方法把它弄得平衡，怎么弄平衡呢？看下一篇博文吧。