关于 Treap 的疑惑
  • 板块学术版
  • 楼主Exp10re
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/8/19 11:07
  • 上次更新2023/11/3 02:44:23
查看原帖
关于 Treap 的疑惑
403069
Exp10re楼主2023/8/19 11:07

Treap 的操作中有一个 rotate 操作,大概长这样:

void rotate(long long &p,long long d)
{
	long long t,v;
	if(d==1)//Right Rotate.
	{
		t=tree[p].son[0];
		v=tree[t].son[1];
		tree[p].son[0]=v;
		tree[t].son[1]=p;
	}
	else//Left Rotate.
	{
		t=tree[p].son[1];
		v=tree[t].son[0];
		tree[p].son[1]=v;
		tree[t].son[0]=p;
	}
	pushup(p);
	pushup(t);
	p=t;
	return;
}

其中,进行完一次 rotate 操作后就会进行对 pp 和 tt 分别进行一次 pushup(pushup操作),但很显然操作时 pp 一定是 tt 的孩子,也就是说,rotate 结束后需要先更新 pp 再更新 tt 才能保证正确性。

我的疑惑是,如果把 pushup 的顺序调换,似乎对结果没什么影响(这里指都能 AC,不代表对平衡树内的数据无影响),这与之前“rotate 结束后需要先更新 pp 再更新 tt 才能保证正确性”的结论相违背,所以是否先更新 tt 再更新 pp 与先更新 pp 再更新 tt 本质相同,又或是有影响,但是可以互相抵消导致对最终结果没有影响?

2023/8/19 11:07
加载中...