0

私は2本の木を持っています。ツリー ノードは次のように定義されます。

class Node{
  String treeId; 
  String type;       //Each node has type which has fixed value. For example, its color: RED, BLANK, GREEN
  Set<Node> children;
  String ref;        //The ref is a string and allowed value are "0", "1",..."10". The value is null if it is not leaf. 
};

リーフの場合、子セットは空です。

与えられた 2 つのツリーの同等のサブツリーを識別する方法が既に効率的に実行されているかどうか疑問に思っています。同等のものは次のように定義されます。

1) Both subtree leaves are setsets leaves of original tree. 
2) Both subtrees leaves have same ref value. 
3) for non-leaves node, the equivalent refers to both node have same type and equivalent children.

ありがとう。この問題に対処するJavaライブラリがあればもっと良いでしょう。

入力は 2 つのツリー ルートである必要があり、出力は同等のサブツリーのルートであるノードです。ツリーの高さは 100 ~ で、500 以上のノードがあります。

私が今やったことは、クラス Node の新しいフィールドを追加したことです。

class Cache{
   Map<String, Set<String>> map = new LinkedHashMap<String, Set<Str>>();
}

マップのキーはノード ID で、値はこのノード ID のこのノードが到達できる参照セットです。ノードの初期化時に開始されるキャッシュ。

isEquivalent 比較フェーズ中に、2 つのルートの参照セット間にオーバーラップが存在するかどうかを確認します。存在しない場合は false を返します。

これにより、比較スペースの数を減らすことができると思います。

4

1 に答える 1

0

1) Both subtree leaves are leaves of original tree.と競合しているように見えるため、要件についてはわかりませんhow to identify equivalent substree for two given tree.。それ以外の場合、再帰的な方法に従うことで、他の 2 つの条件をカバーできるはずです。このhaveSameOriginalTree(r1, r2)メソッドは、私が理解できなかった最初の条件を満たすように実装されている可能性があります。r1およびr2は、等価性をチェックする必要がある 2 つのサブツリーのルートです。

bool areEquivalent(Node r1, Node r2)
{
    if(r1.children == null && r2.children == null)
    {
        return (haveSameOriginalTree(r1, r2) && (r1.ref == r2.ref));
    }
    if((r1.children == null && r2.children != null) || (r1.children != null && r2.children == null))
    {
        return false;
    }
    // if here then both must be non-leaf nodes
    if(r1.type != r2.type)
    {
        return false;
    }
    if(r1.children.getCount() != r2.children.getCount()) // not sure of correct syntax for Java Sets
    {
        return false;
    }
    for(int i=0; i<r1.children.getCount(); i++)
    {
        if(!areEquivalent(r1.children[i], r2.children[i])) // again please correct the syntax for Sets
        {
            return false;
        }
    }

    return true;
}

どう考えているか教えてください。

アップデート

これは、上記のソリューションの反復バージョンです。関数のコールスタックにプッシュされるのではなく、ヒープに割り当てられるスタックデータ構造を使用するため、再帰と大きく変わらないが、それでも優れています。また、(オブジェクト全体をコピーするのではなく) s への参照のみを保持するため、元のツリーを既にメモリにロードしている場合、追加のメモリ オーバーヘッドNodeはそれほど大きくないはずです。

bool areEquivalent(Node r1, Node r2)
{
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    Node n1, n2;

    s1.Push(r1);
    s2.Push(r2);
    while(true) // Need a better check
    {
        if(s1.getCount() != s2.getCount())
        {
            return false;
        }
        if(s1.getCount() == 0) // if both stacks are empty then we've traversed both trees without failure.
        {
            return true;
        }
        n1 = s1.Pop();
        n2 = s2.Pop();
        if(!areEquivalentNodes(n1, n2))
        {
            return false;
        }
        foreach(Node child in n1.children)
        {
            s1.Push(child);
        }
        foreach(Node child in n2.children)
        {
            s2.Push(child);
        }
    }
}

// only checks the two nodes are equivalent. their childrens' equivalence will be handled by other calls to this method.
bool areEquivalentNodes(Node n1, Node n2)
{
    if(n1.children.getCount() != n2.children.getCount())
    {
        return false;
    }
    if(n1.children.getCount() == 0) // if both are leaf nodes...
    {
        if(n1.ref != n2.ref)
        {
            return false;
        }
    }
    else // both are non-leaf
    {
        if(n1.type != n2.type)
        {
            return false;
        }
        // the condition that children of non-leaf nodes be equivalent will be covered by subsequent calls this method...
    }

    return true;
}

childrenどちらのソリューションも、同じ順序で 2 つの同等のノードを想定していることに注意してください。順序付けされていない場合childrenは、上記のコードを呼び出す前に並べ替える必要があります。

これが良いかどうか教えてください。

于 2014-06-05T14:58:10.967 に答える