Forma fácil de encontrar Subárbol en un árbol

Question

Escribo un código que usa un árbol (un árbol regular que puede tener un número ilimitado de nodos, pero no cruzado, es decir, dos nodos principales no apuntarán al mismo nodo hijo) De todos modos, dos cosas:

1) ¿Hay algún algoritmo conocido para encontrar un subárbol dentro de un árbol?

2) ¿Hay alguna biblioteca de Java (o cualquier biblioteca para el caso) que ya implemente este algoritmo? Incluso si no hay ninguno, ¿alguien puede recomendar una buena biblioteca de árbol de Java de propósito general?

Quiero utilizar estos árboles para almacenar datos en un formato de árbol, no para sus capacidades de búsqueda.

Para expandir un poco: estoy usando el árbol como parte del juego para mantener un historial de lo que sucede cuando ocurren ciertos eventos. Por ejemplo, una A puede golpear una B, que puede golpear dos A de que puede golpear a otro dos de un etc.

Eso sería algo como:

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

Por supuesto que hay algo más que A y B. ¿Qué lo que quiero hacer es (para un sistema de logros) es capaz de decir cuando, por ejemplo una a ha afectado a dos a de:

A 
/\ 
A A 

Quiero ser capaz de saber fácilmente si el primer árbol contiene ese subárbol. Y no quiero tener que escribir todo el código para hacerlo si no tengo que hacerlo :)

Answer 1

Parece que un algoritmo sencillo: Encontrar la raíz del árbol de búsqueda en el árbol de juego y comprobar si los hijos del árbol de búsqueda son un subconjunto de los niños en el árbol del juego.

Desde sus explicaciones, no estoy seguro de si el árbol de búsqueda

A 
/\ 
A A 

debe coincidir con este árbol:

A 
/|\ 
A C A 

(. Es decir, si se supone que los niños no congruentes para ser ignorado)

De todos modos, aquí está el código con el que jugué. Es un ejemplo completamente ejecutable y viene con un método principal y una clase simple Node.Siéntase libre para jugar con él:

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

¿Está buscando alguna restricción particular en un subárbol? De lo contrario, un simple traversa l debería bastar para identificar subárboles (básicamente, trate cada nodo como la raíz de un subárbol).

Creo que encontrará que la API que querrá para un árbol varía mucho según su aplicación en particular, tanto que las implementaciones genéricas no son muy útiles. Quizás si pudieras decirnos para qué tipo de aplicación se utilizará el árbol, podríamos proporcionar detalles.

Además, si usted es solo usando un árbol para el almacenamiento de datos, es posible que desee preguntarse por qué necesita un árbol. Esa respuesta también debería responder a la pregunta en mi párrafo anterior.

Answer 3

Me pregunto si hay una extensión del algoritmo de Knuth que sería más eficiente que un recorrido ingenua ...

Answer 4

Si hay una grande, estática, el árbol y usted será la búsqueda de muchos sub-estructuras en el mismo árbol grande, es posible que desee para anotar cada nodo con el conjunto de hashes de todos sus subárboles a una profundidad dada, dependiendo de la cantidad de almacenamiento que esté dispuesto a gastar en esa funcionalidad. Luego construya un mapa de valores hash al conjunto de nodos que son raíces de un subárbol con ese valor hash. Luego, compruebe cada uno de ellos, presumiblemente mucho más barato que un cruce, para el hash de la raíz del árbol de consultas a esa misma profundidad.