algorithm - 从二叉树中删除重复的子树

Question

我要在额外的作业下设计一个算法。该算法必须通过删除重复子树并将所有这些连接重定向到一个左原始子树，将其转换为 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) 中做到这一点？

Answer 1

这发生在构建 oBDD 时。想法是:将树放入规范形式，并为每个节点构建一个包含条目的哈希表。哈希函数是节点的函数+左/右子节点的哈希函数。复杂度为 O(N)，但前提是哈希值是唯一的。递归子树 <--> 子树比较的最终比较(例如，解决冲突)仍将花费 o(N*N)。 More on BDDs或 the original Bryant paper

我目前使用的哈希函数:

#define SHUFFLE(x,n) (((x) << (n))|((x) >>(32-(n))))
/* a node's hashvalue is based on its value
 * and (recursively) on it's children's hashvalues.
 */
#define NODE_HASH2(l,r) ((SHUFFLE((l),5)^SHUFFLE((r),9)))
#define NODE_HASH3(v,l,r) ((0x54321u*(v) ^ NODE_HASH2((l),(r))))

典型用法:

void node_sethash(NodeNum num)
{
if (NODE_IS_NULL(num)) return;

if (NODE_IS_TERMINAL(num)) switch (nodes[num].var) {
        case 0: nodes[num].hash.hash= HASH_FALSE; break;
        case 1: nodes[num].hash.hash= HASH_TRUE; break;
        case 2: nodes[num].hash.hash= HASH_FALSE^HASH_TRUE; break;
        }
else if (NODE_IS_NAMED(num)) {
        NodeNum f,t;
        f = nodes[num].negative;
        t = nodes[num].positive;
        nodes[num].hash.hash = NODE_HASH3 (nodes[num].var, nodes[f].hash.hash, nodes[t].hash.hash);
        }
return ;
}

搜索哈希表:

NodeNum *hash_hnd(NodeNum num, int want_exact)
{
unsigned slot;
NodeNum *ptr, this;
if (NODE_IS_NULL(num)) return NULL;

slot = nodes[num].hash.hash % COUNTOF(hash_nodes);

for (ptr = &hash_nodes[slot]; !NODE_IS_NULL(this= *ptr); ptr = &nodes[this].hash.link) {
        if (this == num) break;
        if (want_exact) continue;
        if (nodes[this].hash.hash != nodes[num].hash.hash) continue;
        if (nodes[this].var != nodes[num].var) continue;
        if (node_compare( nodes[this].negative , nodes[num].negative)) continue;
        if (node_compare( nodes[this].positive , nodes[num].positive)) continue;
                /* duplicate node := same var+same children */
        break;
        }
return ptr;
}

递归比较函数:

int node_compare(NodeNum one, NodeNum two)
{
int rc;

if (one == two) return 0;

if (NODE_IS_NULL(one) && NODE_IS_NULL(two)) return 0;
if (NODE_IS_NULL(one) && !NODE_IS_NULL(two)) return -1;
if (!NODE_IS_NULL(one) && NODE_IS_NULL(two)) return 1;

if (NODE_IS_TERMINAL(one) && !NODE_IS_TERMINAL(two)) return -1;
if (!NODE_IS_TERMINAL(one) && NODE_IS_TERMINAL(two)) return 1;

if (VAR_RANK(nodes[one].var)  < VAR_RANK(nodes[two].var) ) return -1;
if (VAR_RANK(nodes[one].var)  > VAR_RANK(nodes[two].var) ) return 1;


rc = node_compare(nodes[one].negative,nodes[two].negative);
if (rc) return rc;
rc = node_compare(nodes[one].positive,nodes[two].positive);
if (rc) return rc;

return 0;
}