FHQ Treap 的退化

众所周知。一棵树是 FHQ Treap 当且仅当：

其子树是 FHQ Treap。
其根 Priority $>$ 其儿子 Priority。
其根 Value 大于等于左子树 Value 小于等于右子树 Value。

注意到，若邪恶的出题人给你插入的 Value 全部相等，则整个 FHQ Treap 几乎可以说是任意排列，比如可以排列成一条链。

如果你的合并写的不好的话可能就会像我一样退化成

\mathcal{O}(n^2)

：

（一个典型的退化案例，FHQ Treap 的性质一直是满足的，但是若 cost 全部相等，则必然退化成严格链）

CPP

int imerge(int u, int v) {
	if (!u || !v) return u + v;

	if (t[u].priority < t[v].priority) 
		std::swap(u, v);

	int32_t p, q;
	split(v, t[u].cost, p, q);

	t[u].lson = imerge(t[u].lson, p);
	t[u].rson = imerge(t[u].rson, q);
	assert(t[u].priority >= t[t[u].rson].priority);
	assert(t[u].priority >= t[t[u].lson].priority);
	return maintain(u);
}

实测普通 split/merge 不会触发。

有没有大佬的平衡树有交合并写法不会出现这种问题呢。

讨论操作

回复

相关推荐

FHQ Treap 的退化