一个关于splay的问题。
查看原帖
一个关于splay的问题。
423520
wizard(偷开O2楼主2024/11/24 12:17

这是rotate的代码

void rotate(int now){
	int fax=fa[now],grfax=fa[fax],son=getwhich(now);
	ch[fax][son]=ch[now][son^1];//爸爸的右儿子设为now的左儿子/爸爸的左儿子设为now的右儿子
	fa[ch[now][son^1]]=fax;//双向关系
	ch[now][son^1]=fax;//???
	fa[fax]=now;
	fa[now]=grfax;
	if(grfax){
		ch[grfax][ch[grfax][1]==fax]=now;
	}
	update(fax);
	update(now);
}

我的问题是

ch[now][son^1]=fax;

这句话的含义是什么。

rotate应该是把now转上去,father直接和孙子建立关系,now和grandfa建立关系就OK了吗,为啥还要让儿子的儿子连爸爸,不理解,求解答。

2024/11/24 12:17
加载中...