除去二叉树重复子树 [英] Removing duplicate subtrees from binary tree

问题描述

我要设计下的附加作业的算法。该算法有COM preSS二叉树转化成DAG通过删除重复的子树，并重定向到一个离开原来的子树的所有这些连接。比如我有一个树（我给节点preorder）：

I have to design an algorithm under the additional homework. This algorithm have to compress binary tree by transforming it into DAG by removing repetitive subtrees and redirecting all these connections to one left original subtree. For instance I've got a tree (I'm giving the nodes preorder):

1 2 1 3 2 1 3

1 2 1 3 2 1 3

该算法必须删除正确的连接（右子树，这意味着2 1 3）1（根），重定向到左连接（因为这些substrees是相同的，剩下的就是先在preorder所以我们只能留下左）

The algorithm have to remove right connection (right subtree that means 2 1 3) of 1 (root) and redirect it to left connection (because these substrees are the same and left was first in preorder so we leave only the left)

我看到它的方式：我是路过的树preorder。对于当前节点'W'，我开始递归有检测（如果存在）的原子树等于同根树W。如果我发现相等的子树，我切了递归（我必须做什么），或者当我在寻找相同的子树递归到W。当然，我predict一些小的改进，如与同等数量的节点只比较​​子树。

The way I see it: I'm passing the tree preorder. For current node 'w', I start recursion that have to detect (if there exist) the original subtree equals to the subtree with root 'w'. I'm cutting the recursion if I find equal subtree (and I do what must be done) or when I get to 'w' in my finding the same subtrees recursion. Of course I predict some small improvements like comparing only subtrees with equal number of nodes.

如果我没看错它给复杂度为O（n ^ 2），其中n是给定的二叉树的节点数。是否有机会更快地做到这一点（我认为这是）。为线性算法可能吗？

If I'm not wrong it gives complexity O(n^2) where n is number of nodes of given binary tree. Is there any chance to do it faster (I think it is). Is the linear algorithm possible?

可惜的是我的算法终于有了复杂度为O（n ^ 3）。你的回答与哈希将可能对我来说非常有用了一段时间后，当我知道更多。对于现在太难了，我..

Pity that my algorithm finally has complexity O(n^3). Your answers with hashing probably will be very useful for me after some time, when I will know much more.. For now it's too difficult for me..

最后一个问题。是否有机会使用一些基本技巧（不哈希）？

The last question. Is there any chance to do it in O(n^2) using elementary techniques (not hashing)?

推荐答案

这恰好构建oBDDs时。我们的想法是：把树成一个规范的形式，构建一个哈希表与每个节点的条目。散列函数是节点+散列函数为左/右子节点的功能。复杂度为O（N），但前提是我们可以依靠hashvalues​​是唯一的。最终的比较（如解决冲突）仍然将花费O（N * N）的递归子树＆LT; - >子树进行比较。 更多BDDS 或的原来科比纸

This happens when constructing oBDDs. The Idea is: put the tree into a canonical form, and construct a hashtable with an entry for every node. Hash function is a function of the node + the hash functions for the left/right child nodes. Complexity is O(N), but only if one can rely on the hashvalues being unique. The final compare (e.g. for Resolving collisions) will still cost o(N*N) for the recursive subtree <--> subtree compare. More on BDDs or the original Bryant paper

该散列函数我目前使用的：

The hashfunction I currently use:

#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 ;
}

在搜索哈希表的：

Searching the hash table:

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;
}

递归比较功能：

The recursive compare function:

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;
}

这篇关于除去二叉树重复子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！