树哈希

假设我们定义一个有根树 $T$ 上一个节点为 $u$，其中其儿子为 $v$，则 $H(v) = f({H(u_1), H(u_2), ..., H(u_k)})$，则 $H(T) = H(root)$

其中 $f$ 通常为 $f(v) = hash(sort({v_i}))$，例如 $f(v) = \sum_{i=1}^k v_i$ 自然溢出。

假设此时有树 $T_1$ 和树 $T_2$，在不发生哈希碰撞的情况下，若 $H(T1) = H(T2)$ 则说明 $T_1$ 和 $T_2$ 同构，即$ T_1 \cong T_2 \implies H(T_1)=H(T_2)$。

如何证明？尝试先定义两棵树同构：

若树每个节点的子树结构相同，则这两棵树同构，也就是说，对于两颗同构的树，如果我们从树根出发（对于无根树，可以选择重心确保唯一性），以某种方式将所有子节点排序，那么这两颗树会恰好一样。

尝试证明，假设哈希函数 $f$ 为单射，即不存在哈希碰撞，且在输入时对子节点进行排序，此时我们需要证明： $T_1 \cong T_2 \iff H(T_1) = H(T_2)$。

考虑证明充分性：

用树同构定义：

若 $T_1 \cong T_2$，存在一个节点映射 $\phi$ 使得子树结构完全对应。

根据归纳假设：

• 对于单节点树显然成立，因为 $H(T_1) = f(\emptyset) = H(T_2)$
• 对于所有非单节点树，若所有子树对 $\phi(u_i)$ 满足 $H(u_i) = H(\phi(u_i))$，则因为排序保证顺序无关， $$H(v_1) = f(\text{multiset}{H(u_i)}) = f(\text{multiset}{H(\phi(u_i))}) = H(\phi(v_1))$$ 得证。

然后考虑必要性：

使用强归纳法：

• 若 $H(v_1)=H(v_2)$，则对应子哈希多重集相等（由 $f$ 单射性得出）。
• 因为多重集相等，我们可以一一匹配子节点哈希相同的子树；
• 由归纳假设，哈希相同的子树同构；
• 因此整棵树同构。

得证。

综上所述，若哈希函数 $f$ 为单射，则$ T_1 \cong T_2 \iff H(T_1)=H(T_2)$