Imaginez l'arbre suivant:
F = 1 2 1
*[1] [1] ...
[2] *[2] ...
[3] [3] ...
[4] [4] ...
... ...
8 Réponses :
Je ne sais pas si cela conviendrait à votre problème, mais une façon de stocker des hiérarchies dans des bases de données, avec des fonctionnalités rapides "Donnez-moi de tout ce nœud et de ce nœud" consiste à stocker un "chemin".
Par exemple , pour un arbre qui ressemble à ceci: p> Vous stockiez les lignes comme suit, en supposant que la lettre de l'arbre ci-dessus est l'ID "de chaque ligne: P> id path
a a
b a*b
c a*c
d a*c*d
e a*c*e
C'est exactement ce que je propose, uniquement pour les bases de données, autant que je puisse dire :) Dans une implémentation native, StartSwith serait la partie lente - pour m nœuds parents potentiels avec une longueur maximale de préfixe de N, ce serait o (NM) Je pense que, alors que les matrices de bits font ceci O (n), au détriment de la croissance de la mémoire exponentielle :(
La longueur du chemin peut être o (journal (n)) alors commence par prend les tâches O (journal (n))
Une table de cartographie statique fonctionnerait-elle? c'est à dire. Vous explosez toutes les combinaisons, vous pourrez donc stocker à chaque noeud une liste de descendants, où cette liste est peuplée avec tous les descendants, quelle que soit sa profondeur? Il aurait une juste quantité de coûts de démarrage pour construire les tables de recherche, mais après cela serait capable de répondre "quels nœuds sont des descendants de x" en temps constant (amorti), au moins si vous avez utilisé une hache / dictionnaire.
Pour une arborescence M, au lieu de votre tableau de bit, pourquoi ne pas enregistrer simplement l'ID binaire "TRIE ID" (en utilisant des bits par niveau) em> avec chaque nœud? Pour votre exemple (supposer m == 2) em>: alors vous pouvez faire le test dans O (1): p> a = 0b01, b = 0b0101, c = 0b1001, ... code> mask = (1<<( FindMSB(parent->id)+1) ) -1;
retunr (child->id&mask == parent->id);
Pouvez-vous élaborer comment calculer que Trie ID? Gardez à l'esprit que c'est un arbre multi-voitures avec potentiellement de nombreux nœuds par niveau.
Je suppose que A) Vous pouvez déjà calculer l'identifiant dans le formulaire que vous avez décrit ci-dessus, et b) m est corrigé. Pour la première fonction, juste faire foreach chiffil: id = (id << m) | (1 << (chiffre-1)) . Pour la 2e méthode, c'est: id = (id << b) | chiffre , où b est le nombre de bits nécessaires pour maintenir m (i.e: FindMSB (m) +1).
Et si M dépasse 32/64 bits, utilisez simplement un tableau long, puis boucle sur toutes les pièces d'identité lors de l'anding? J'aime ça :)
-Or- Si vous avez des stockages et que vous ne voulez pas y aller avec des champs de bit, stockez les identifiants comme des chaînes d'octets dans exactement la forme que vous avez montrée: par exemple A est "\ x01", f est "\ x01 \ x02 \ x01 ". Cela peut gérer jusqu'à 255 enfants par nœud et vous pouvez effectuer le test avec strtstr (enfant, parent) == Parent
@Ashelly ne devrait pas c = 0b1001 être c = 0b0110 dans votre exemple avec m == 2 ?
Non, la représentation est correcte, c'est l'algorithme de construction dans mon premier commentaire qui a tort. Nous voulons que l'ID de niveau 0 soit dans les bits les moins importants, de sorte que nous n'avons pas à vous déplacer à gauche car nous ajoutons plus de niveaux. Pour attribuer des ID de Trie aux enfants d'un nœud numéroté à partir de 1..m , la construction doit être trie_id = (1 << (ChildNum-1)) | parent_id
@ASHELLY OK, je l'ai eu maintenant, merci pour votre commentaire! Juste pour être sûr si j'avais tout de suite, dans votre exemple A = 0B01, B = 0B0101, C = 0B1001, ... Vous réservez 2 bits par Profondeur d'arborescence + 1 , donc par exemple Si un arbre a une profondeur de 11 comme suit: 1 (root, profondeur 0) -> 2 (enfant de 1, profondeur 1) -> 3 (enfant de 2, profondeur 2) -> ... - > 12 (enfant de 11, profondeur 11) ; Vous utiliserez 2 bits * (11 profondeur + 1) = 24 bits bits pour l'identifiant Trie des nœuds qui ont une profondeur 11, non?
Traverser tout arbre nécessitera des étapes "profondeur d'arborescence". Par conséquent, si vous conservez une structure d'arborescence équilibrée, il est prouvé que vous aurez besoin o (log n) les opérations pour votre Opération . De ce que je comprends que votre arbre a l'air spécial et que vous ne pouvez pas le maintenir de manière équilibrée, non? Donc o (n) sera possible. Mais c'est mauvais lors de la création de l'arbre de toute façon, vous allez probablement mourir avant d'utiliser la recherche Selon la fréquence à laquelle vous aurez besoin de cette opération Alors, vous paieriez sur o (log n) sur chaque insert insert et obtenez l'efficacité de la haquetable o (1) pour un < Strong> Recherche .
Je viens de voir que je n'ai pas assez clarifié ma question, désolé pour ça :( Le problème est qu'il existe une piscine potentielle de nœud parents, disons, A, B, C - alors j'aimerais voir si F est un descendant de tout nœud dans la piscine mère. Avec votre idée de hashmap, cela serait toujours O (n), mais la mémoire de mémoire devrait être beaucoup moins :)
En fait, je ne suivrais pas mes propres conseils. Je n'aime pas beaucoup les haschmaps, j'aime Garanties mieux. Deuxièmement, je pense que j'ai négligé quelque chose dans ma description ... mais sinon: tout ce que signifie "piscine de nœud", je pense que l'entrée de hachage devrait y travailler aussi. Parlant en C ++ - Parlance, il est en fait un définir <> ce que je pense. Les entrées seraient paire insert (make_pair (parent, enfant)) . Ensuite, si vous souhaitez vérifier n'importe quel enfant.SthataParent (potentiparent) est juste un retour set.find (noeud, potentiel, potentiparent)! = Fin) . Vérifiez que fait une paire donnée dans O (1) .
Dans une traversée de pré-commande, chaque ensemble de descendants est contigu. Pour votre exemple,
A B D E C F
+---------+ A
+---+ B
+ D
+ E
+-+ C
+ F
Remarque: Le journal N Performance est PAS CONTENANT SUR UNE TOPICOLOGIE D'ARBRE POINTS.
Vos arbres d'entrée sont-ils toujours statiques? Si tel est le cas, vous pouvez utiliser un algorithme d'ancêtres communs le plus bas pour répondre à la question descendante dans O (1) temps avec une construction de temps / espace O (n). Une requête de la LCA reçoit deux nœuds et demandé quel est le nœud le plus bas de l'arbre dont le sous-arbre contient les deux nœuds. Ensuite, vous pouvez répondre à la requête iscidendant avec une seule requête de la LCA, si la LCA (A, B) == A ou LCA (A, B) == B, puis une descendante de l'autre.
Ce Topcoder Algorithme Tuorial donne une discussion approfondie du problème et Quelques solutions à différents niveaux de complexité / efficacité du code.
Excellent tutoriel, merci! J'ai appris quelques choses :) Malheureusement, mon arbre n'est pas statique, mais je pense que l'idée de la LCA de pièces SQRT peut être facilement adoptée pour une utilisation dynamique lorsque la profondeur de l'arbre est toujours à peu près la même, comme dans mon cas.
Vous pouvez répondre à la requête du formulaire "est un nœud un descendant du nœud B?" En temps constant, en utilisant simplement deux matrices auxiliaires.
Préprocéder à l'arborescence, en visitant dans une première commande en profondeur, et pour chaque noeud, un magasin, son temps de départ et de fin dans la visite dans les deux tableaux commencent [] et fin [].
Alors, disons que la fin [u] et commencer [u] sont respectivement la fin de la fin et du début de la visite du nœud U.
Le noeud u est un descendant du nœud V si et seulement si:
Démarrer [V] <= Démarrer [u] et end [u] <= fin [v].
Et vous avez terminé, la vérification de cette condition ne nécessite que deux recherches dans les tableaux de départ et de fin
Malheureusement, l'arbre n'est pas statique, je ne peux donc pas vraiment le prétraiter.
Jetez un coup d'œil à Modèle de jeu imbriqué Il est très efficace de sélectionner mais trop lent pour mettre à jour
Pour ce que cela vaut, ce que vous demandez ici est équivalent à tester si une classe est un sous-type d'une autre classe dans une hiérarchie de classe et dans des implémentations telles que CPPHON, cela vient de faire le bon vieux démodé "itérer les parents à la recherche du parent "Way.
Est-ce toujours un arbre binaire?