初学平衡树,关于splay里的delete函数的一些问题
  • 板块学术版
  • 楼主XSean
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/6/11 17:20
  • 上次更新2023/10/23 13:21:33
查看原帖
初学平衡树,关于splay里的delete函数的一些问题
546830
XSean楼主2023/6/11 17:20

以下是我的del函数:

void del(int v){
	int pre = get_pre(v), suc = get_suc(v);
	splay(pre, 0), splay(suc, pre);
	int del = ls(suc);
	if(ptr[del].cnt > 1) ptr[del].cnt--, ptr[del].siz--, splay(del, 0);
	else ls(suc) = 0, splay(suc, 0);
}

在这里面当 if(ptr[del].cnt > 1) 的时候我让 ptr[del].siz--,但是我发现没有这条语句也是对的不知道为什么

以下是我的其他函数:

void pushup(int x){
	ptr[x].siz = ptr[ls(x)].siz + ptr[rs(x)].siz + ptr[x].cnt;
}
void rotate(int x){ //旋x,y 
	int y = ptr[x].p, z = ptr[y].p;
	int k = rs(y) == x;
	//组x,z 
	ptr[z].s[rs(z) == y] = x; //swap(x,y) 
	ptr[x].p = z;
	//x.son的调换->y.son
	ptr[y].s[k] = ptr[x].s[k^1];
	ptr[ptr[x].s[k^1]].p = y;
	//组x,y
	ptr[x].s[k^1] = y;
	ptr[y].p = x; 
	//先y,后x 
	pushup(y), pushup(x);
}
void splay(int x, int k){
	while(ptr[x].p != k){
		int y = ptr[x].p, z = ptr[y].p;
		if(z != k) ((ls(z) == y) ^ (ls(y) == x)) ? rotate(x) : rotate(y);
		rotate(x);
	}
	if(k == 0) root = x;
}
void insert(int v){
	int x = root, p = 0;
	while(x && ptr[x].v != v){
		p = x, x = ptr[x].s[v > ptr[x].v]; 
	}
	if(x) ptr[x].cnt++;
	else{
		x = ++idx;
		ptr[p].s[v > ptr[p].v] = x;
		ptr[x].init(p, v);
	}
	splay(x, 0);
}
void find(int v){
	int x = root;
	while(ptr[x].s[v > ptr[x].v] && v != ptr[x].v){
		x = ptr[x].s[v > ptr[x].v];
	}
	splay(x, 0);
}
int get_pre(int v){
	find(v);
	int x = root;
	if(v > ptr[x].v) return x;
	x = ls(x);
	while(rs(x)) x = rs(x);
	splay(x, 0);
	return x;
}
int get_suc(int v){
	find(v);
	int x = root;
	if(v < ptr[x].v) return x;
	x = rs(x);
	while(ls(x)) x = ls(x);
	splay(x, 0);
	return x;
}
2023/6/11 17:20
加载中...