Moyen facile de trouver des sous-arbre dans un Arbre

Je suis en train d'écrire un code qui utilise un Arbre (un régulier arbre qui peut avoir un nombre illimité de nœuds, mais pas de crossover, c'est à dire deux nœuds parents ne pointera pas le même nœud enfant). En tout cas, deux choses:

1) existe-il des algorithmes les plus connus pour la recherche d'un sous-arbre dans un arbre.

2) existe-il des bibliothèques Java (ou bibliothèques) qui mettent déjà en œuvre de cet algorithme? Même si on n'y fait, quelqu'un peut-il recommander des bons à des fins générales Java arbre de la bibliothèque?

Je veux utiliser ces arbres pour maintenir les données dans un format arbre, pas pour leurs capacités de recherche.

Pour développer un peu: je suis à l'aide de l'arbre en tant que partie du jeu afin de conserver un historique de ce qui se passe lorsque certains événements se produisent. Par exemple, l'Un peut frapper un B qui peut frapper deux Un qui peut frapper un autre deux Un etc de.

Qui ressemblerait à quelque chose comme:

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

Bien sûr, il ya plus que A et B. Ce que je veux faire, c'est (pour un système de réalisation), c'est être capable de dire quand, disons un Un a frappé deux A:

  A
 / \
A   A

Je veux être en mesure de facilement savoir si le premier arbre ne contient que des sous-arborescence. Et je ne veux pas avoir à écrire tout le code pour le faire si je n'ai pas 🙂

OriginalL'auteur cdmckay | 2009-02-25

Ressemble à un simple algorithme: Trouver la racine de l'arbre de recherche dans l'arborescence du jeu et de vérifier si les enfants de l'arbre de recherche sont un sous-ensemble des enfants dans le jeu de l'arbre.

De vos explications, je ne suis pas sûr de savoir si un arbre de recherche

  A
 / \
A   A

doit correspondre à cet arbre:

  A
 /|\
A C A

(c'est à dire en cas de non-correspondance des enfants sont censés être ignoré.)

De toute façon, voici le code que j'ai juste joué avec. Il est entièrement exemple, et est livré avec une méthode main et un simple Node classe. N'hésitez pas à jouer avec elle:

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

Mieux de le modifier avant de le "Vecteur" de la police d'obtenir de vous! 😉
Laissez-les venir! 🙂

OriginalL'auteur gclj5

2

Vous êtes à la recherche pour n'importe quel particulier des contraintes sur une sous-arborescence? Si non, un simple traversal devrait suffire pour identifier les sous-arbres (essentiellement traiter chaque nœud de la racine d'un sous-arbre).

Je crois que vous trouverez que l'API, vous aurez envie pour un arbre varie beaucoup par votre application particulière, si bien que les implémentations ne sont pas très utiles. Peut-être si vous pouviez nous dire quel type d'application que l'arbre sera utilisé pour, nous pourrions fournir des précisions.

Aussi, si vous êtes juste à l'aide d'un arbre pour le stockage de données, vous pourriez vous demander pourquoi vous avez besoin d'un arbre. Cette réponse doit aussi répondre à la question dans mon précédent paragraphe.

J'ai mis à jour ma question à élaborer.

OriginalL'auteur Martin
0

Je me demande si il y a une extension de l'algorithme de Knuth, qui serait plus efficace qu'un naïf traversée...

Assez sûr que c'est pas possible, puisque tous les "arbres algorithmes sont basés sur le fait, pour chaque nœud contient quelques informations sur ses enfants (comme les leurs valeurs maximum et minimum), et ce n'est pas le cas ici.
Je ne vois pas comment qui suit. Un char dans un str ne contient pas d'info sur l'avenir de la station. Dans ce cas, la racine correspond à la racine de la cible, mais son enfant B ne correspond pas, et maintenant, je devrais être capable d'ignorer la vérification de B par rapport à la racine-Un de la mire.
citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.3770 utilise une représentation de chaîne de l'arbre à donner des sous-linéaire correspondant.

OriginalL'auteur Ken
0

Si il y a un gros, statique, de l'arbre et vous serez à la recherche pour de nombreux sous-arborescences dans le même grand arbre, vous pouvez annoter chaque nœud avec le jeu de hachages de l'ensemble de ses sous-arbres à une profondeur donnée en fonction de la quantité de stockage que vous êtes prêt à consacrer à cette fonctionnalité. Puis construire une carte à partir de valeurs de hachage pour l'ensemble de nœuds qui sont les racines d'un sous-arbre avec cette valeur de hachage. Ensuite il suffit de vérifier chacune de celles-ci, sans doute beaucoup moins cher qu'une traversée, pour le hachage de la racine de l'arborescence de la requête à la même profondeur.

OriginalL'auteur Dick King

Vous devez vous connecter pour publier un commentaire.