平衡树首先要弄清最重要的两个操作:左旋与右旋
其中P始终记录为根结点,以右旋为例,可理解为右旋使当前根结点变为右儿子,左儿子取代成为根节点
(感觉就像向右偏移) 旋转完有两个结点信息需要更新,x和y,即当前根结点和它的右儿子
void zig(int &p) //右旋
{
int q = tr[p].l; //让q指向x的左儿子y
tr[p].l = tr[q].r; //将x的左儿子变为y的右儿子
tr[q].r = p; //将y的右儿子变为x
p = q; //让p仍然指向当前根节点
pushup(tr[p].r); //旋转完更新右儿子信息
pushup(p); //更新根节点信息
}
弄清楚了左右旋,(以大根堆为例)只需要维护使得当前根节点的val最大,不满足时旋转
然后即可愉快地维护BST(二叉搜索树)的key值了
代码如下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, INF = 1e8;
int n;
struct node{ //此处使用大根堆
int l, r; //左右儿子指针
int key, val; //key是搜索树关键字, val是堆的随机关键字
int cnt, size;
}tr[N];
int root, idx;
void pushup(int p) //向上更新
{
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key) //用key生成结点
{
tr[++ idx].key = key;
tr[idx].val = rand(); //随机数关键字维护堆结构
tr[idx].cnt = tr[idx].val = 1;
return idx;
}
void zig(int &p) //右旋
{
int q = tr[p].l;
tr[p].l = tr[q].r;
tr[q].r = p;
p = q;
pushup(tr[p].r);
pushup(p);
}
void zag(int &p) //左旋
{
int q = tr[p].r;
tr[p].r = tr[q].l;
tr[q].l = p;
p = q;
pushup(tr[p].l);
pushup(p);
}
void build() //初始化建树
{
get_node(-INF), get_node(INF); // 1号2号为负(正)无穷哨兵
root = 1, tr[1].r = 2;
pushup(root);
if(tr[1].val < tr[2].val) zag(root);
}
void insert(int &p, int key) //插入key
{
if(!p) p = get_node(key); //当前结点不存在则创立
else if(tr[p].key == key) tr[p].cnt ++;
else if(tr[p].key > key) //往左子树插入
{
insert(tr[p].l, key);
if(tr[tr[p].l].val > tr[p].val) zig(p);
}
else //往右子树插入
{
insert(tr[p].r, key);
if(tr[tr[p].r].val > tr[p].val) zag(p);
}
pushup(p);
}
void remove(int &p, int key) //删除key
{
if(!p) return;
if(tr[p].key == key)
{
if(tr[p].cnt > 1) tr[p].cnt --;
else if(tr[p].l || tr[p].r) //如果有左儿子或者右儿子
{ //如果不存在右儿子或者左儿子的val要比右儿子的val大,应该右旋
if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r, key); //此时原来的根结点被右旋为右儿子,remove右儿子
}
else //反之左旋
{
zag(p);
remove(tr[p].l, key);
}
}
else p = 0;
}
else if(tr[p].key > key) remove(tr[p].l, key);
else remove(tr[p].r, key);
pushup(p);
}
int get_rank_by_key(int p, int key) //通过数值找排名
{
if(!p) return 0; //该数值不存在
if(tr[p].key == key) return tr[tr[p].l].size + 1;
if(tr[p].key > key) return get_rank_by_key(tr[p].l, key);
return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}
int get_key_by_rank(int p, int rank) //通过排名找数值
{
if(!p) return INF; //不存在该排名的数
if(tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
if(tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
int get_prev(int p, int x) // 找到严格小于x的最大数
{
if(!p) return -INF;
if(tr[p].key >= x) return get_prev(tr[p].l, x);
return max(tr[p].key, get_prev(tr[p].r, x));
}
int get_next(int p, int x) // 找到严格大于x的最大数
{
if(!p) return INF;
if(tr[p].key <= x) return get_next(tr[p].r, x);
return min(tr[p].key, get_next(tr[p].l, x));
}
int main()
{
build();
scanf("%d", &n);
while (n -- )
{
int opt, x;
scanf("%d%d", &opt, &x);
if (opt == 1) insert(root, x);
else if (opt == 2) remove(root, x);
else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1));
else if (opt == 5) printf("%d\n", get_prev(root, x));
else printf("%d\n", get_next(root, x));
}
return 0;
}