BST初探

定义

BST（二叉搜索树）是一种树形结构，有如下性质。

空树是二叉搜索树。
若左子树非空，那么左子树上所有点的权值均小于其根节点的值。
若左子树非空，那么其右子树上所有点的权值均大于其根节点的值。
二叉搜索树的左右子树均为二叉搜索树。

操作

BST 的单次操作最坏为 $O(n)$ ， $n$ 表示 BST 内的节点数，即树的形态是一条链。

节点定义

struct node{  
    int val, ch[2], size;//节点权值，左/右儿子，子树大小  
}d[N];  
#define ls(x) d[x].ch[0]  
#define rs(x) d[x].ch[1]  
int tot, root;//第几个节点没用，根节点  
int newnode(int val){//返回新建节点的编号  
    int w = ++tot;  
    d[w].val = val, ls(w) = rs(w) = 0, d[w].size = 1;  
    return w;  
}  
void pushup(int x){//更新子树大小。  
    d[x].size = d[ls(x)].size + d[rs(x)].size + 1;  
}

插入

我们设插入节点权值为 $val$ ，当前节点是 $now$ 。
从根节点开始，我们需要满足 BST 的第 $2$ 、 $3$ 条性质。
如果当前是空节点那么就直接新建。
那么如果 $val < now_{val}$ ，那么由于第 $2$ 条性质，左子树的权值都 $< val$ ，所以只能插入到右子树。
否则根据第 $3$ 条性质，我们要插入在左子树。

void insert(int&now, int val){  
    if(!now)return void(now = newnode(val));  
    if(d[now].val < val)insert(rs(now), val);  
    else insert(ls(now), val);  
    pushup(now);
}

删除

我们设删除节点权值为 $val$ ，动迁节点是 $now$ 。
如果当前节点为空，说明没有。
否则如果 $val < now_{val}$ ，说明目标节点在右子树。
否则目标节点在左子树。

我们现在找到了要删除的节点。
但是如果要删除的节点有儿子节点呢？

如果它有一个儿子，我们可以直接用它的儿子顶替它的位置。
如果它有两个儿子，那么我们找到它的后缀，将它的权值变成其后缀的权值，然后继续向下删除后继即可。
我们只需要先向右走一步，然后一直往左走，最后一个就是后继了。

void del(int&now, int val){  
    if(!now)return;//空节点返回  
    if(d[now].val == val){//找到目标节点  
        int w = now;  
        if(ls(now) && (w = rs(now))){  
            while(ls(w))w = ls(w);//和后缀交换。  
            d[now].val = d[w].val, del(rs(now), d[w].val);//删除后缀  
        }  
        else now = ls(now) ? ls(now) : rs(now);//被儿子顶替  
    }  
    else if(d[now].val < val)del(rs(now), val);  
    else del(ls(now), val);  
    if(now)pushup(now);
}

查 x 排名

如果 $val < val_{rt}$ ，那么左子树的全部小于 $val$ ，那么答案加上左子树的大小，进入右子树。
否则，进入左子树。
平衡树内可能有好几个权值为 $val$ 的节点，但我们要找的是严格小于的。

int query_rank(int val){  
    int ans = 1, now = root;  
    while(now)  
        if(d[now].val < val)ans += d[d[now].ls].size + 1, now = d[now].rs;  
        else now = d[now].ls;  
    return ans;  
}

第 k 小

如果 $size_{ls} + 1 = k$ 说明找到答案了。
如果 $size_{ls} \ge k$ ，说明答案在左子树。
否则我们减去左儿子的大小，进入右子树。

int kth(int x){  
    int now = root, siz = 0, z = x;  
    while(now){  
        if((siz = d[ls(now)].size + 1) == x)return d[now].val;//找到节点  
        else now = ((siz > x) ? ls(now) : (x -= siz, rs(now)));  
    }  
    return -1;  
}

前驱

第一种：
我们可以先找到 $val$ 的排名为 $k$ ，然后在询问第 $k - 1$ 小的数。

1	int ask_pre(int val){return kth(query_rank(val) - 1);}

第二种：
若当前节点是叶子节点，如果 $< k$ 更新答案，返回答案。
否则，如果 $val_{ls} \ge k$ ，进入左儿子找答案。
否则，用左儿子更新答案，进入右儿子。

int ask_pre(int val){  
    int now = root, ans = -1e9;  
    while(now)  
        if(d[now].val >= val)now = ls(now);  
        else ans = d[now].val, now = rs(now);  
    return ans;  
}

后继

询问 $val + 1$ 的排名为 $x$ ，然后查询第 $x$ 小即可。
第一种：

1	int ask_next(int val){return kth(query_rank(val + 1));}

第二种：
和前驱相差不大。

int ask_next(int val){  
    int now = root, ans = 1e9;  
    while(now){  
        if(d[now].val <= val)now = rs(now);  
        else ans = d[now].val, now = ls(now);  
    }  
    return ans;  
}

优化

树的形态是链的时候，BST 的时间复杂的会退化成 $O(n)$ 。
那么我们可以尽可能的让树尽可能的不变成链。

能解决这个问题的就是平衡树。
平衡树大多会定义一个平衡状态，在树不满足平衡时，会通过旋转来改变树的形态。
接下来我会列举几个比较常见的平衡树：

AVL：最早发明的自平衡二叉树，要使左右子树的高度差不大于 $1$ 。
RBT（红黑树）：由 B 树改良，需要满足自身的 $5$ 个性质。
旋转 treap，无旋treap：将 tree 和 heap 结合，来保证树的形态。
splay：将要操作的点旋转到根，做到均摊复杂度。
WBLT：由线段树和加权平衡树结合，常数优秀。
B 树：不再是二叉树，而是多叉树，由于信息紧贴，在不区分堆栈的磁盘会更优秀。
替罪羊树：加权平衡树的另一种实现，在树不平衡时，直接推倒重建。

旋转

rotate 操作是把某个给定节点上移一个位置，并保证二叉搜索树的性质不改变。
旋转操作分为左旋和右旋（图上节点是编号）。

我们来模拟一下右旋的操作（红色是要删除的，蓝色是更改后的）。

这样就完成了一次旋转。
而在实现中，我会把左右旋写在一起。
这里的 rotate(x, 0) 表示将 $x$ 的左儿子提到 $x$ 的高度。
这里的 rotate(x, 1) 表示将 $x$ 的右儿子提到 $x$ 的高度。

void rotate(int&now, int dir){  
    int t = d[now].ch[dir];  
    d[now].ch[dir] = d[t].ch[!dir];  
    d[t].ch[!dir] = now;  
    pushup(now), pushup(t), now = t;  
}