Łatwy sposób na znalezienie Subtree w drzewie

Question

Piszę kod, który używa drzewa (zwykłe drzewo, które może mieć nieograniczoną liczbę węzłów, ale nie ma zwrotnicy, tj. Dwa węzły nadrzędne nie będą wskazywać tego samego węzła podrzędnego). W każdym razie dwie rzeczy:

1) Czy są jakieś dobrze znane algorytmy do znalezienia sub-drzewa w drzewie.

2) Czy istnieją jakieś biblioteki Java (lub jakiekolwiek inne biblioteki), które już implementują ten algorytm? Nawet jeśli ich nie ma, czy ktoś może polecić jakąkolwiek dobrą ogólną bibliotekę Java?

Chcę używać tych drzew do przechowywania danych w formacie drzewa, a nie do ich możliwości wyszukiwania.

Aby rozwinąć nieco: Używam drzewa jako części gry, aby zachować historię wydarzeń, które mają miejsce, gdy zdarzają się określone wydarzenia. Na przykład puszkę hit B, która może uderzyć dwie, które może trafić inny dwie użytkownika itp

To będzie wyglądać następująco:

A 
    | 
    B 
/
    A 
/\ 
A A 
/\ 
    A A 

Oczywiście istnieje więcej niż tylko A i B. Co Chcę zrobić to (dla systemu osiągnięć) jest w stanie powiedzieć, kiedy, powiedzmy a ma trafić dwie to:

A 
/\ 
A A 

Chcę, aby móc łatwo wiedzieć, jeśli pierwsze drzewo zawiera że poddrzewie. I nie chcę pisać całego kodu, aby to zrobić, jeśli nie muszę :)

Answer 1

Wygląda na algorytmie prosta: Znajdź korzeń drzewa wyszukiwania w drzewie gry i sprawdzić, czy dzieci drzewa wyszukiwania są podzbiorem dzieci w drzewie gry.

ze swojego wyjaśnienia, nie jestem pewien, czy drzewo wyszukiwania

A 
/\ 
A A 

powinien pasować do tego drzewa:

A 
/|\ 
A C A 

(tzn. Jeśli niedopasowanych dzieci mają być ignorowane)

W każdym razie, oto kod, z którym właśnie bawiłem. Jest to w pełni działający przykład i jest dostarczany z główną metodą i prostą klasą Node.Czuć się swobodnie bawić się z nim:

import java.util.Vector; 

public class PartialTreeMatch { 
    public static void main(String[] args) { 
     Node testTree = createTestTree(); 
     Node searchTree = createSearchTree(); 

     System.out.println(testTree); 
     System.out.println(searchTree); 

     partialMatch(testTree, searchTree); 
    } 

    private static boolean partialMatch(Node tree, Node searchTree) { 
     Node subTree = findSubTreeInTree(tree, searchTree); 
     if (subTree != null) { 
      System.out.println("Found: " + subTree); 
      return true; 
     } 
     return false; 
    } 

    private static Node findSubTreeInTree(Node tree, Node node) { 
     if (tree.value == node.value) { 
      if (matchChildren(tree, node)) { 
       return tree; 
      } 
     } 

     Node result = null; 
     for (Node child : tree.children) { 
      result = findSubTreeInTree(child, node); 

      if (result != null) { 
       if (matchChildren(tree, result)) { 
        return result; 
       } 
      } 
     } 

     return result; 
    } 

    private static boolean matchChildren(Node tree, Node searchTree) { 
     if (tree.value != searchTree.value) { 
      return false; 
     } 

     if (tree.children.size() < searchTree.children.size()) { 
      return false; 
     } 

     boolean result = true; 
     int treeChildrenIndex = 0; 

     for (int searchChildrenIndex = 0; 
       searchChildrenIndex < searchTree.children.size(); 
       searchChildrenIndex++) { 

      // Skip non-matching children in the tree. 
      while (treeChildrenIndex < tree.children.size() 
        && !(result = matchChildren(tree.children.get(treeChildrenIndex), 
               searchTree.children.get(searchChildrenIndex)))) { 
       treeChildrenIndex++; 
      } 

      if (!result) { 
       return result; 
      } 
     } 

     return result; 
    } 

    private static Node createTestTree() { 
     Node subTree1 = new Node('A'); 
     subTree1.children.add(new Node('A')); 
     subTree1.children.add(new Node('A')); 

     Node subTree2 = new Node('A'); 
     subTree2.children.add(new Node('A')); 
     subTree2.children.add(new Node('C')); 
     subTree2.children.add(subTree1); 

     Node subTree3 = new Node('B'); 
     subTree3.children.add(subTree2); 

     Node root = new Node('A'); 
     root.children.add(subTree3); 

     return root; 
    } 

    private static Node createSearchTree() { 
     Node root = new Node('A'); 
     root.children.add(new Node('A')); 
     root.children.add(new Node('A')); 

     return root; 
    } 
} 

class Node { 
    char value; 
    Vector<Node> children; 

    public Node(char val) { 
     value = val; 
     children = new Vector<Node>(); 
    } 

    public String toString() { 
     StringBuilder sb = new StringBuilder(); 

     sb.append('('); 
     sb.append(value); 

     for (Node child : children) { 
      sb.append(' '); 
      sb.append(child.toString()); 
     } 

     sb.append(')'); 

     return sb.toString(); 
    } 
} 

Answer 2

Szukasz jakichś szczególnych ograniczeń w poddrzewie? Jeśli nie, to powinno wystarczyć simple traversa l do identyfikacji poddrzew (w zasadzie traktuj każdy węzeł jako źródło poddrzewa).

Wierzę, że okaże się, że interfejs API, który chcesz dla drzewa, jest bardzo różny w zależności od aplikacji - tak bardzo, że ogólne implementacje nie są zbyt użyteczne. Być może, gdybyś mógł nam powiedzieć, jakiego rodzaju aplikacji drzewo będzie używane, możemy podać szczegółowe informacje.

Ponadto, jeśli jesteś po prostu używając drzewa do przechowywania danych, możesz zapytać siebie, dlaczego potrzebujesz drzewa. Ta odpowiedź powinna również odpowiedzieć na pytanie w poprzednim punkcie.

Answer 3

Zastanawiam się, czy jest rozszerzeniem algorytmu Knuth, który byłby bardziej efektywny niż naiwnej przechodzenie ...

Answer 4

Jeśli jest jedna duża, statyczne, drzewo i będzie szukało wielu poddrzew w tym samym wielkim drzewie, może chcesz opisywanie każdego węzła z zestawu skrótów z wszystkie poddrzewa do określonej głębokości w zależności od tego, ile miejsca chcesz wydać na tę funkcję. Następnie utwórz mapę z wartości mieszania do zestawu węzłów, które są korzeniami poddrzewa o tej wartości mieszania. Następnie sprawdź każdy z nich, prawdopodobnie znacznie tańszy niż przejście, dla skrótu z korzenia drzewa zapytań do tej samej głębokości.