luogu 阅读链接。
定义
BST(二叉搜索树)是一种树形结构,有如下性质。
- 空树是二叉搜索树。
- 若左子树非空,那么左子树上所有点的权值均小于其根节点的值。
- 若左子树非空,那么其右子树上所有点的权值均大于其根节点的值。
- 二叉搜索树的左右子树均为二叉搜索树。
操作
BST 的单次操作最坏为 O(n),n 表示 BST 内的节点数,即树的形态是一条链。
节点定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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<nowval,那么由于第 2 条性质,左子树的权值都 <val,所以只能插入到右子树。
否则根据第 3 条性质,我们要插入在左子树。
1 2 3 4 5 6
| 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<nowval,说明目标节点在右子树。
否则目标节点在左子树。
我们现在找到了要删除的节点。
但是如果要删除的节点有儿子节点呢?
如果它有一个儿子,我们可以直接用它的儿子顶替它的位置。
如果它有两个儿子,那么我们找到它的后缀,将它的权值变成其后缀的权值,然后继续向下删除后继即可。
我们只需要先向右走一步,然后一直往左走,最后一个就是后继了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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<valrt,那么左子树的全部小于 val,那么答案加上左子树的大小,进入右子树。
否则,进入左子树。
平衡树内可能有好几个权值为 val 的节点,但我们要找的是严格小于的。
1 2 3 4 5 6 7
| 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 小
如果 sizels+1=k 说明找到答案了。
如果 sizels≥k,说明答案在左子树。
否则我们减去左儿子的大小,进入右子树。
1 2 3 4 5 6 7 8
| 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 更新答案,返回答案。
否则,如果 valls≥k,进入左儿子找答案。
否则,用左儿子更新答案,进入右儿子。
1 2 3 4 5 6 7
| 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));}
|
第二种:
和前驱相差不大。
1 2 3 4 5 6 7 8
| 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 的高度。
1 2 3 4 5 6
| 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; }
|