xan*_*xan 9 compression algorithm tree binary-tree
我必须在额外的作业下设计算法.该算法必须通过删除重复子树并将所有这些连接重定向到一个左原始子树来将二进制树转换为DAG来压缩二进制树.例如,我有一棵树(我给节点预订):
1 2 1 3 2 1 3
该算法必须删除1(根)的右连接(右子树,意思是2 1 3)并将其重定向到左连接(因为这些子节是相同的,左边是先预订,所以我们只留下左边)
我看待它的方式:我正在通过树预订.对于当前节点'w',我开始递归,必须检测(如果存在)原始子树等于具有根'w'的子树.如果我找到相同的子树(并且我做了必须做的事情),或者当我在找到相同的子树递归时得到"w"时,我正在削减递归.当然,我预测一些小的改进,例如只比较具有相同节点数的子树.
如果我没有错,它会给出复杂度O(n ^ 2),其中n是给定二叉树的节点数.有没有机会更快地完成它(我认为是).线性算法是否可行？
可惜我的算法最终有复杂度O(n ^ 3).一段时间后,你对散列的回答对我来说可能会非常有用,届时我会知道更多...现在对我来说太难了..
最后一个问题.有没有机会使用基本技术(不是散列)在O(n ^ 2)中做到这一点？
我会采用散列方法。
叶子的哈希值是其值 mod P_1。节点的哈希值为(value+hash(left_son)*P_2+hash(right_son)*P_2^2) mod P_1，其中 P_1、P_2 是素数。如果你计算至少 5 个不同的大素数对的哈希值（大我的意思是接近 10^8-10^9，这样你就可以在不溢出的情况下进行数学计算），你可以安全地假设具有相同哈希值的节点是相同的。
然后你可以遍历树，首先检查儿子并进行变换。这将在 O(n) 时间内起作用。
请注意，您可以使用其他哈希函数，例如(value + hash(left_son)*P_2 + hash(right_son)*P_3) mod P_1等。