关于splay的前驱和后继
  • 板块学术版
  • 楼主happybob
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/10/8 22:08
  • 上次更新2023/10/27 08:08:25
查看原帖
关于splay的前驱和后继
332914
happybob楼主2022/10/8 22:08

splay写假了,应该是查找前驱后继后没有 Splay 操作,那么找前驱后继应该是把什么点旋转到根?

int get_prev(int u, int x)
	{
		if (!u) return -INF;
		if (tr[u].v >= x) return get_prev(tr[u].s[0], x);
		return max(tr[u].v, get_prev(tr[u].s[1], x));
	}
	int get_next(int u, int x)
	{
		if (!u) return INF;
		if (tr[u].v <= x) return get_next(tr[u].s[1], x);
		return min(tr[u].v, get_next(tr[u].s[0], x));
	}

用的这个做法,显然里面没有 Splay 操作,但是貌似将前驱或后继所在的点 Splay 后还是 T 了

2022/10/8 22:08
加载中...