关于平衡树
  • 板块灌水区
  • 楼主Masna_Kimoyo
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/11/15 15:41
  • 上次更新2023/11/4 00:29:37
查看原帖
关于平衡树
199459
Masna_Kimoyo楼主2021/11/15 15:41

在网上找了treap和splay的模板,有几个不理解的地方求解答qwq

这是splay的旋转板子:


void update(int x) {
	if(x) {
		siz[x]=cou[x];
		if(son[x][0])siz[x]+=siz[son[x][0]];
		if(son[x][1])siz[x]+=siz[son[x][1]];
	}
}

这是traep的:

void rotate(int p, int &x)
{
    int y=T[x].son[!p];
    T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size;
    T[x].son[!p]=T[y].son[p];
    T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size;
    T[y].son[p]=x;
    x=y;
}

请问为什么一个点和他的儿子节点信息修改后他们的子树信息不用修改呢?

2021/11/15 15:41
加载中...