二叉查找树（BST） 是一种能存储特定数据类型的容器。二叉查找树允许快速查找，插入或者删除一节点。重要性质：左小右大，中序遍历是有序的。
Splay（伸展树） 是一种平衡二叉树，它通过将一个节点旋转到根结点，使得整个棵树仍然满足 BST 的性质，并且保持平衡而不至于退化成链。
1.旋转
struct node{
int s[2] ;//左右儿子
int p ; //父亲
int v ;//节点权值
int cnt;//权值出现次数
int size;// 子树大小
void init(int p1, int v1){
p = p1, v = v1 ;
cnt = size = 1 ;
}
}tr[N];
int root ;//根节点编号
int idx ;//节点个数
void rotate(int x){//旋转，x为旋转后往上走的节点
//y 为当前节点的 父节点， z 为原先当前节点父节点的父节点
int y = tr[x].p , z = tr[y].p ;
int k = tr[y].s[1] == x ;//k = 1 说明左旋 反之说明右旋
//以左旋为例
//旋转后， 当前节点的左儿子节点变成原先当前节点父节点的右儿子节点
tr[y].s[k] = tr[x].s[k^1] ;
//同时当前节点的左儿子节点的父节点变成原先当前节点的父节点
tr[tr[x].s[k^1]].p = y ;
//当前节点的左儿子节点变成原先当前节点父节点
tr[x].s[k^1] = y ;
//当前节点的父节点的父节点变成原先当前节点
tr[y].p = x ;
//当前父节点的父节点的儿子节点变成原先当前节点，替换原先父亲节点的位置
tr[z].s[tr[z].s[1]==y] = x ;
//当前节点的父节点变成原先父节点的父节点
tr[x].p = z ;
pushup(x) ;
pushup(y) ;
}
void pushup(x){
tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + tr[x].cnt ;
}
2. 伸展
访问一个节点
//k >0 时，把 x 转到 k 下面
//k = 0 时，把 x 转到根
void splay(int x,int k){
while(tr[x].p != k){
int y = tr[x].p, z = tr[y].p ;
if(z!= k){//直线型先转y后转x。折线形转两次x
((tr[z].s[0] == y) ^ (tr[y].s[0] == x)) : rotate(x) ? rotate(y) ;
}
rotate(x) ;
}
if(k == 0) root = x ;
}
3. 查找 find
找到 v 所在节点并把其转到根上
void find(int v){
int x = root ;
while(tr[x].s[v > tr[x].v] && v! = tr[x].v){//两个条件， 第一个是找不到目标节点， 第二个时，找到目标节点
x = tr[x].s[v > tr[x].v] ;
splay(x,0) ;
}
}
4. 前驱 get_pre
求
int get_pre(int v){
find(v) ;
int x = root ;
if(tr[x].v < v) retrun x ; //说明当前根节点就是 v 的前驱
//如果 tr[x].v = v，那么v 的前驱就一定在树伸展后的左子树的右下角
//如果 tr[x].v > v，因为此时的根节点与v一定是最接近的，所以此时v 大于当前根节点左儿子的v，也就是说其前驱也一样是当前伸展后根节点左子树的右下角
x = tr[x].s[0] ;//得到左子树右下角
while(tr[x].s[1]) x = tr[x].s[1] ;
return x ;
}
5. 后继 get_suc
求
//和前驱同理
int get_suc(int v){
find(v) ;
int x = root ;
if(tr[x].v > v) retrun x ; //说明当前根节点就是 v 的后继驱
x = tr[x].s[1] ;//得到右子树左下角
while(tr[x].s[0]) x = tr[x].s[0] ;
return x ;
}
6. 删除
删除
void del(int v){
int pre = get_pre(v) ;//把前驱节点放在根节点
int suc = get_suc(v) ;//后继节点放在根节点之下
splay(pre,0), splay(suc,pre) ;
//伸展后，比我们要删除的节点大的节点在suc的右子树上， 比其小的在 pre的左子树上，
int del = tr[suc].s[0] ;//也就是说我们现在要删除的节点没有子节点，为叶子节点
if(tr[del].cnt > 1){
tr[del].cnt --, splay(del,0) ;
}else{
tr[suc].s[0] = 0, splay(suc,0) ;
}
}
7. 插入
void insert(int v){
int x = root, p = 0 ;
while(x && tr[x],v !=v ){
p = x , x = tr[p].s[v>tr[x].v]
}
if(x) tr[x].cnt++ ;//该值第一次出现
else{//新出现的值
x = ++ idx ;
tr[p].s[v>tr[p].v] = x ;//记录新的节点是谁的哪个儿子节点
tr[x].init(p,v) ;
}
splay(x, 0);
}
8. 查询数据排名（该数也有可能不存在）
int get_rank(int v){
insert(v) ;//先添加一下这个值，可能不存在
int res = tr[tr[root].s[0]].size ;//为什么不用+1是因为还有哨兵节点无穷小
del(v);//最后删除，因为是辅助用，本不应该存在
return res ;
}
9. 查询排名为
int get_val(int k){
int x = root ;
while(1){
int y = tr[x].s[0] ;
if(tr[y].size() + tr[x].cnt < k){//说明目标在右子树上
k -= tr[y].size() + tr[x].cnt ;
x = tr[x].s[1] ;
}else{
if(tr[y].size() >= k) x = tr[x].s[0] ;
else break ;
}
}
splay(x,0) ;//避免变成链
return tr[x].v ;
}
完整代码
#include<bits/stdc++.h>
#define int long long
#define lc(x) tr[x].s[0] ;
#define rc(x) tr[x].s[1] ;
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f ;
struct node
{
int v ;//权值大小
int p ;//父亲节点
int cnt ; //权值数量
int siz ; //树的大小
int s[2] ; //儿子节点
void init(int p1, int v1){
p = p1 , v = v1 ;
cnt = siz = 1 ;
}
}tr[N];
int root ; //表示根节点的编号
int idx ; //表示新的节点的编号
void pushup(int x){
tr[x].siz = tr[tr[x].s[0]].siz + tr[tr[x].s[1]].siz + tr[x].cnt ;
}
void rotate(int x){//旋转节点
int y = tr[x].p, z = tr[y].p ;
int k = tr[y].s[1] == x ;//1说明要左旋
tr[y].s[k] = tr[x].s[k^1] ;//原来节点的左儿子，变成父节点的右儿子节点
tr[tr[x].s[k^1]].p = y ;//原来节点的左儿子节点的父亲节点变成原先节点的父亲节点
tr[x].s[k^1] = y ;//原来节点的左儿子变成其父亲节点
tr[y].p = x ;
tr[z].s[tr[z].s[1] == y] = x ;
tr[x].p = z ;
//更新树 大小
pushup(x) ;
pushup(y) ;
}
void splay(int x, int k){//伸展 两个参数， 第一个参数所代表的节点要变成 第二个参数的节点的儿子节点
while(tr[x].p != k){
int y = tr[x].p , z = tr[y].p ;
if(z != k){
(tr[z].s[0] == y) ^ (tr[y].s[0] == x) ? rotate(x) : rotate(y) ;
}
rotate(x) ;
}
if(k == 0) root = x ;
}
void insert(int v){
int x = root , p = 0 ;
while(x && tr[x].v != v){
p = x , x = tr[p].s[v > tr[x].v] ;
}
if(x){//说明不是新的点
tr[x].cnt ++ ;
}else{
x = ++idx ;
tr[p].s[v > tr[p].v] = x ;
tr[x].init(p,v) ;
}
splay(x,0) ;
}
void find(int v){//把v做权值所在节点转移到根节点上
int x = root ;
while(tr[x].s[v > tr[x].v] && tr[x].v != v){//还有可能目标节点不存在
x = tr[x].s[v > tr[x].v] ;
}
splay(x,0) ;
}
int get_pre(int v){
find(v) ;
int x = root ;
if(tr[x].v < v) return x ;
x = tr[x].s[0] ;
while(tr[x].s[1]){
x = tr[x].s[1] ;
}
return x ;
}
int get_suc(int v){
find(v) ;
int x = root ;
if(tr[x].v > v) return x ;
x = tr[x].s[1] ;
while(tr[x].s[0]){
x = tr[x].s[0] ;
}
return x ;
}
void del(int v){//要把目标节点放在叶子节点上
//让后继变成前驱的右儿子， 让当前变成后继的左儿子
int pre = get_pre(v) ;
int suc = get_suc(v) ;
splay(pre,0), splay(suc, pre) ;
int del = tr[suc].s[0] ;//这就是目标删除的节点
if(tr[del].cnt > 1){
tr[del].cnt -- ;
splay(del,0) ;
}else{
tr[suc].s[0] = 0 ;
splay(suc,0) ;
}
}
int get_rank(int v){
insert(v) ;
int res = tr[tr[root].s[0]].siz ;
del(v) ;
return res ;
}
int get_val(int k){
int x = root ;
while(1){
if(k <= tr[tr[x].s[0]].siz + tr[x].cnt){
if(k > tr[tr[x].s[0]].siz){
break ;
}else{
x = tr[x].s[0] ;
}
}else{
k -= tr[tr[x].s[0]].siz + tr[x].cnt ;
x = tr[x].s[1] ;
}
}
return x ;
}
int n ;
void solve(){
cin >> n ;
int op ;
int v ;
//两个哨兵
insert(INF) ;
insert(-INF) ;
while(n -- ){
cin >> op ;
cin >> v ;
if(op == 1){
insert(v) ;
}else if(op == 2){
del(v) ;
}else if(op == 3){
int res = get_rank(v) ;
cout << res << endl ;
}else if(op == 4){
int res = get_val(v + 1) ;
res = tr[res].v ;
cout << res << endl ;
}else if(op == 5){
int res = get_pre(v) ;
res = tr[res].v ;
cout << res << endl ;
}else{
int res = get_suc(v) ;
res = tr[res].v ;
cout << res << endl ;
}
}
}
signed main()
{
solve() ;
}
Comments NOTHING