Déterminer si un arbre est un sous-arbre d'un autre
https://stackoverflow.com/questions/1017821
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Il existe deux arbres binaires T1 et T2 qui stockent des données de caractères. Les doublons sont autorisés.
Comment puis-je savoir si T2 est un sous-arbre de T1? .
T1 contient des millions de nœuds et T2 des centaines de nœuds.
La solution
Traverse T1. Si le nœud actuel est égal au nœud racine de T2, parcourez les deux arbres (T2 et le sous-arbre actuel de T1) en même temps. Comparez le nœud actuel. S'ils sont toujours égaux, T2 est un sous-arbre de T1.
Autres conseils
Je suggère un algorithme utilisant le prétraitement:
1) Pré-traiter l'arborescence T1 en conservant la liste de toutes les racines de sous-arborescence possibles (la liste de caches comportera des millions d'entrées);
2) Triez la liste des racines en cache selon l’ordre décroissant des données, conservé dans le répertoire racine. Vous pouvez choisir une fonction de tri plus élégante, par exemple, analyser une arborescence de caractères dans une chaîne.
3) Utilisez la recherche binaire pour localiser le sous-arbre nécessaire. Vous pouvez rapidement rejeter les sous-arbres dont le nombre de nœuds n'est pas égal au nombre de nœuds T2 (ou de profondeur différente).
Notez que les étapes 1) et 2) ne doivent être effectuées qu'une seule fois. Vous pouvez ensuite tester plusieurs candidats de sous-arborescence en utilisant le même résultat prétraité.
Si vos arbres ne sont pas triés de quelque manière que ce soit, je ne vois pas d'autre moyen que de faire une recherche brute-force : parcourez l'arbre T1 et vérifiez pour voir si vous atteignez un noeud qui correspond au premier noeud de l’arbre T2 . Sinon, continuez à parcourir T1 . Si tel est le cas, vérifiez si les nœuds suivants correspondent, jusqu'à la fin de T2 , auquel cas vous avez un hit: votre arborescence T2 est bien un sous-arbre de T1 .
Si vous connaissez la profondeur de chaque nœud de T1 (de feuille à nœud), vous pouvez ignorer tous les nœuds qui ne sont pas aussi profonds que le sous-arbre que vous recherchez. Cela pourrait vous aider à éliminer beaucoup de comparaisons inutiles. Disons que T1 et T2 sont bien équilibrés, l’arbre T1 aura une profondeur totale de 20 ( 2 ** 20 > 1 000 000 ) et l’arbre T2 aura une profondeur de 7 ( 2 ** 7 > 100 ). Vous aurez juste à parcourir les 13 premières couches de T1 (8192 nœuds - ou est-ce que 14 couches et 16384 nœuds?) Et pourrez sauter environ 90 % de T1 ...
Cependant, si par sous-arbre vous voulez dire que les nœuds terminaux de T2 sont également des nœuds terminaux de T1 , vous pouvez effectuer un premier parcours T1 et calculez la profondeur de chaque noeud (distance de feuille à noeud), puis vérifiez uniquement les sous-arbres ayant la même profondeur que T2 .
Si vous êtes lié à la mémoire / au stockage (vous ne pouvez pas pré-manipuler et stocker les arbres sous d'autres formes), vous ne pourrez probablement pas faire mieux que la recherche en force brute suggérée par d'autres réponses (traverse P1 recherche la racine correspondante de P2, parcourez les deux pour déterminer si le nœud est réellement la racine d'un sous-arbre correspondant, continuez avec la traversée d'origine si ce n'est pas une correspondance). Cette recherche fonctionne dans O (n * m) où n est la taille de P1 et m est la taille de P2. Avec des vérifications de profondeur et d’autres optimisations potentielles en fonction des données de l’arbre dont vous disposez, cet homme peut être optimisé un peu, mais c’est toujours généralement O (n * m). En fonction de votre situation particulière, cela peut être la seule approche raisonnable.
Si vous n'êtes pas lié à la mémoire / au stockage et que la complexité ne vous dérange pas, je pense que cela pourrait être amélioré en O (n + m) en le réduisant à problème de la plus longue sous-chaîne commune avec l'aide d'un arbre de suffixe généralisé . Vous pouvez trouver des informations à ce sujet pour un problème similaire ici . Peut-être que quand j'aurai plus de temps, je reviendrai et éditerai plus de détails sur une implémentation.
Si l’on donne la racine des deux arbres et que les noeuds sont du même type, pourquoi s’assurer alors que la racine de T2 n’est pas suffisante?
Je suppose que "étant donné un arbre T" signifie donné un pointeur sur la racine de T et le type de données du noeud.
Cordialement.
Je ne suis pas sûr si mon idée est correcte. Néanmoins, pour votre persual.
- Procédez à une promenade post-commande dans l’arbre 1 & amp; Arbre 2, appelez-le P1 et P2.
- Comparez P1 & amp; P2. S'ils sont différents L'arbre n'est pas un sous-arbre. Quitter.
- S'ils sont identiques ou si P1 est contenu dans P2. Vous pouvez décider lequel est le sous-arbre.
Je pense que nous devons recourir à la force brutale, mais pourquoi faut-il faire correspondre les arbres après avoir trouvé votre racine de T2 dans T1? Ce n’est pas la même chose que lorsque nous ne sommes pas supposés trouver si l’arbre est identique (nous avons seulement besoin de comparer l’arbre entier).
On vous donne des arbres T1 et T2, des pointeurs, pas les valeurs.
Si le noeud T2 (qui est un pointeur) est présent dans l’arbre T1.
Ensuite, l'arbre T2 est un sous-arbre de T1.
Modifier:
Seulement s'il est dit que T2 est en réalité un arbre différent par objet, et nous devons savoir que s'il existe un sous-arbre dans T1, il est identique à T2.
Ensuite, cela ne fonctionnera pas.
Et nous n’avons pas d’autre option que de choisir les solutions déjà évoquées ici.
Disons que nous avons T1 comme arbre parent et T2 comme un arbre qui pourrait être un sous-arbre de T1. Faites ce qui suit. Les suppositions faites sont T1 et T2 sont des arbres binaires sans facteur d’équilibrage.
1) Recherchez la racine de T2 dans T1. Si non trouvé, T2 n'est pas un sous-arbre. La recherche de l'élément dans BT prendra O (n) temps.
2) Si l'élément est trouvé, on trouve une traversée pré-ordonnée de T1 à partir de l'élément racine de noeud de T2. Cela prendra du temps. Effectuez également une traversée de T2 en précommande. Prendra O (n) temps. Le résultat de la traversée de pré-commande peut être stocké dans une pile. L’insertion dans la pile ne prendra que O (1).
3) Si la taille de deux piles n’est pas identique, T2 n’est pas un sous-arbre.
4) Retirez un élément de chaque pile et vérifiez l’égalité. En cas d'incompatibilité, T2 n'est pas un sous-arbre.
5) Si tous les éléments correspondants, T2 est un sous-arbre.
Je suppose que votre arbre est un arbre immuable , de sorte que vous ne changez jamais d'arborescence (vous ne faites pas set-car! en langage schématique), mais vous le faites construire de nouveaux arbres à partir de feuilles ou d’arbres existants.
Dans ce cas, je vous conseillerais de conserver dans chaque nœud (ou sous-arbre) un code de hachage de ce nœud. En langage C, déclarez que l’arbre-s est
struct tree_st {
const unsigned hash;
const bool isleaf;
union {
const char*leafstring; // when isleaf is true
struct { // when isleaf is false
const struct tree_st* left;
const struct tree_st* right;
};
};
};
puis calculez le hachage au moment de la construction et lorsque vous comparez des noeuds pour l'égalité, comparez d'abord leur hachage pour l'égalité; la plupart du temps, le code de hachage serait différent (et vous ne vous soucierez pas de comparer le contenu).
Voici une fonction de construction de feuille possible:
struct tree_st* make_leaf (const char*string) {
assert (string != NULL);
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
t->hash = hash_of_string(string);
t->isleaf = true;
t->leafstring = string;
return t;
}
La fonction permettant de calculer un code de hachage est
unsigned tree_hash(const struct tree_st *t) {
return (t==NULL)?0:t->hash;
}
Fonction permettant de construire un nœud à partir de deux sous-arbres sleft & amp; sright est
struct tree_st*make_node (const struct tree_st* sleft,
const struct tree_st* sright) {
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
/// some hashing composition, e.g.
unsigned h = (tree_hash(sleft)*313) ^ (tree_hash(sright)*617);
t->hash = h;
t->left = sleft;
t->right = sright;
return t;
}
La fonction de comparaison (de deux arbres tx et ty ) tire parti du fait que si les codes de hachage sont différents, les comparands sont différents
bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
if (tx==ty) return true;
if (tree_hash(tx) != tree_hash(ty)) return false;
if (!tx || !ty) return false;
if (tx->isleaf != ty->isleaf) return false;
if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
else return equal_tree(tx->left, ty->left)
&& equal_tree(tx->right, ty->right);
}
La plupart du temps, le test tree_hash (tx)! = tree_hash (ty) est réussi et vous n'avez pas à recurse.
En savoir plus sur la consommation de hachage .
Une fois que vous disposez d'une fonction equal_tree basée sur le hachage, vous pouvez utiliser les techniques mentionnées dans d'autres réponses (ou dans des manuels).
L’une des méthodes les plus simples consiste à écrire la méthode is_equal () pour tree et à procéder comme suit,
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
Notez que is_equal () peut être optimisé en utilisant hashcode pour l’arbre. Cela peut être fait simplement en prenant la hauteur de l'arbre, le nombre d'enfants ou la plage des valeurs sous forme de hashcode.
bool is_equal(TNode*other) {
if(x != other->x) return false;
if(height != other->height) return false;
if(nchildren != other->nchildren) return false;
if(hashcode() != other->hashcode()) return false;
// do other checking for example check if the children are equal ..
}
Lorsque l’arborescence est similaire à une liste chaînée, le temps nécessaire est de O (n). Nous pouvons également utiliser des méthodes heuristiques lors du choix des enfants à comparer.
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
if(is_equal(other)) return true;
if(left == NULL || right == NULL) {
return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
if(left->nchildren < right->nchildren) { // find in smaller child tree first
return (left->contains_subtree(other)) || right->contains_subtree(other);
} else {
return (right->contains_subtree(other)) || left->contains_subtree(other);
}
}
Une autre méthode consiste à sérialiser les deux arbres sous forme de chaîne et à rechercher si la deuxième chaîne (sérialisée à partir de T2) est une sous-chaîne de la première chaîne (sérialisée à partir de T1).
Le code suivant est sérialisé en pré-commande.
void serialize(ostream&strm) {
strm << x << '(';
if(left)
left->serialize(strm);
strm << ',';
if(right)
right->serialize(strm);
strm << ')';
}
Et nous pouvons utiliser un algorithme optimisé, par exemple Knuth & # 8211; Morris & # 8211; Pratt algorithme pour rechercher (éventuellement en temps O (n)) l’existence de la sous-chaîne et éventuellement déterminer si un arbre est un sous-arbre d’autre.
Encore une fois, la chaîne peut être compressée efficacement avec Burrows & # 8211; Wheeler_transform. Et il est possible de bzgrep de rechercher une sous-chaîne dans les données compressées.
Une autre méthode consiste à trier les sous-arbres de l’arbre en fonction de leur taille et du nombre d’enfants.
bool compare(TNode*other) {
if(height != other->height)
return height < other->height;
return nchildren < other->nchildren;
}
Notez qu'il y aura O (n ^ 2) sous-arbres. Pour réduire le nombre, nous pouvons utiliser une plage basée sur la hauteur. Par exemple, nous ne pouvons nous intéresser qu'aux sous-arbres de hauteur 1000 à 1500.
Lorsque les données triées sont générées, il est possible d'effectuer une recherche binaire et de déterminer si elles sont sous-définies en temps O (lg n) (en considérant qu'il n'y a pas de doublons dans les données triées).
