确定性树同构算法

zhoumurui · 2026-03-09 12:08:52 · 算法·理论

我猜测我大概率是在重复造轮子，不过还是写出来一下。

如果是假算请告知我，我改投休闲娱乐分区。

特别鸣谢：省选联考 2026 D2T3 出题人。

使用场景

在得到一棵树的情况下，通过 O(n) 的预处理，可以 每次询问 O(1) 比较这棵树的两棵子树是否相等。

对于多棵树的情形，可以将这些树挂在同一个根上，转化为上述问题。

一些准备工作

考虑对两棵树定义 \ge 操作（为了与大小关系区分，称之为强弱关系，A \ge B 称为 A 不弱于 B），使得：

• 若 A \ge B，B \ge C，则 A \ge C。
• 两棵树 A,B 同构当且仅当 A \ge B 且 B \ge A。

我们发现 D2T3 对两棵树大小关系的定义就很好地满足了这些条件。

定义 1 定义 A \ge B，当且仅当下面条件中至少一个满足：

• 设 A 和 B 的所有儿子的子树按强弱关系从强到弱排序后分别为 a_1,\dots,a_n 和 b_1,\dots,b_m，则 a 数组的字典序不小于 b 数组。

两个数同构定义为 A = B。<,>,\le,\not = 等符号的定义类似，下不赘述。

一些显而易见的性质：

性质 1 若 A \ge B，B \ge C，则 A \ge C。

性质 2 两棵树 A,B 同构当且仅当 A \ge B 且 B \ge A。

证明一个有关强弱关系的性质：

性质 3 若两个树 A 和 B 满足 A 的高度大于 B 的高度，则 A > B。

证明 用数学归纳法。

若 B 的高度为 1，A 的高度大于 1，则 B 的点数为 1。A > B 显然。

假设 B 的高度不大于 k 时结论都成立。当 B 的高度为 k+1 时，根据归纳假设，令 A 和 B 的所有儿子的子树中，最强的分别为 A_1 和 B_1。根据归纳假设，有 A_1 的高度为 A 的高度 -1，B_1 的高度为 B 的高度 -1 也就是 k。因为 A 的高度大于B 的高度，所以 A_1 的高度大于 B_1 的高度，由归纳假设知 A_1 > B_1，于是由定义 A>B。

由数学归纳法，命题得证。

为了判断一棵树的两棵子树是否同构，容易想到把所有子树按照强弱排序，然后比较排序后相邻的两棵子树是否同构，在此之上求出 rk_i 表示子树的排名，使得：

注意这里的 rk 定义与习惯有所区别，这里是为了方便实现。

接下来的篇幅将展示如何实现上述步骤。

算法过程

由于要比较两棵树就要比较它们所有儿子的子树。因此考虑将所有的 u 按照高度从小到大排序，然后将高度相等的分成一组，并且一组一组求，求完一组计算一组的 rk。

高度为 1 的所有树都同构显然，不用求了。

考虑将高度为 k 的树按照强弱关系排序。由于它们所有儿子的大小关系前面都已经求出来了，直接比较 rk 就可以了，因此将待求的点的所有儿子按照 rk 从大到小排序。这个时候我们发现只要将这些点按照字典序排序就可以了。

上基数排序即可，将这些点按照子树从弱到强排序。随后扫一遍，如果一个子树和上一个同构，则 rk 与上一个相等，否则 rk 等于上一个 +1。判断同构直接暴力比较字典序即可。

所有点的儿子序列长度之和是 O(n) 的，因此基数排序的过程实现较好可以做到 O(n)。判断同构的时候，每个点最多被判断两次，因此均摊也是 O(n) 的，所以预处理的复杂度是 O(n)。

然后是查询，直接查 rk 就行了，这不是 O(1)？

应用前景

不知道，感觉没啥前景，和树哈希比不知道优秀在哪，码量也比树哈希大几倍。