Algorithme O(1) pour déterminer si le nœud est descendant d'un autre nœud dans un multiway arbre?

StackOverflow https://stackoverflow.com/questions/6020369

Question

Imaginez l'arbre suivant:

    A
   / \
  B   C
 / \   \
D   E   F

Je suis à la recherche d'un moyen d'interroger, par exemple, si F est un descendant d'Un (remarque:F n'a pas besoin d'être un direct descendant d'Une), qui, dans ce cas particulier pourrait être vrai.Seule une quantité limitée de potentiel nœuds parents ont besoin d'être testé contre un plus grand potentiel de descendants du nœud de la piscine.

Lors de l'essai de savoir si un nœud est un descendant d'un nœud dans le potentiel parent de la piscine, il doit être testé à l'encontre de TOUS les potentiels de nœuds parents.

C'est ce que l'un est venu avec:

  • Convertir multiway arbre à un trie, c'est à direattribuer les préfixes suivants pour chaque noeud sur le dessus de l'arbre:

     A = 1
 B = 11
 C = 12
 D = 111
 E = 112
 F = 121

  • Ensuite, réserve un tableau de bits pour chaque préfixe de taille et d'ajouter des nœuds parents à être testé contre, c'est à diresi C est ajouté le potentiel du noeud parent de la piscine, faire:

      1    2    3  <- Prefix length

*[1]  [1]  ...
 [2] *[2]  ...
 [3]  [3]  ...
 [4]  [4]  ...
 ...  ...

  • Lorsque le test si un nœud est un descendant d'un potentiel nœud parent, prendre ses trie préfixe, recherche le premier caractère de la première "préfixe de table" (voir ci-dessus) et si elle est présente, la recherche de la deuxième caractère de préfixe dans le second "préfixe de table" et ainsi de suite, c'est à diretest de F conduit à:

     F = 1    2    1

   *[1]  [1]  ...
    [2] *[2]  ...
    [3]  [3]  ...
    [4]  [4]  ...
    ...  ...

    donc oui, F, est un descendant de C.

Ce test semble être le pire des cas O(n), où n = le maximum de la longueur de préfixe = maximum de la profondeur de l'arbre, de sorte que son pire des cas est exactement égale à la manière évidente d'aller juste en haut de l'arborescence et de comparer les nœuds.Cependant, elle effectue beaucoup mieux si l'testé nœud est près du bas de l'arbre et le potentiel du noeud parent est quelque part en haut.En combinant les deux algorithmes d'atténuer à la fois les pires scénarios.Cependant, la surcharge de la mémoire est un sujet de préoccupation.

Est-il une autre façon de faire cela?Tous les pointeurs grandement apprécié!

Était-ce utile?

La solution

Vos arbres d'entrée sont-ils toujours statiques? Si c'est le cas, vous pouvez utiliser un algorithme d'ancêtre commun le plus bas pour répondre à la question des descendants en O (1) avec une construction de temps / espace O (n). Une requête LCA reçoit deux nœuds et a 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 isDesCective avec une seule requête LCA, si LCA (A, B) == A ou LCA (A, B) == B, alors l'un est le descendant de l'autre.

Cette Topcoder Algorithme Tuoriel Donne une discussion approfondie du problème et de quelques solutions à différents niveaux de complexité / efficacité du code.

Autres conseils

Je ne sais pas si cela conviendrait à votre problème, mais une façon de stocker les hiérarchies dans les bases de données, avec des fonctionnalités rapides "donnez-moi tout de ce nœud et vers le bas" est de stocker un "chemin".

Par exemple, pour un arbre qui ressemble à ceci:

    +-- b
    |
a --+       +-- d
    |       |
    +-- c --+
            |
            +-- e

Vous stockeriez les lignes comme suit, en supposant que la lettre dans l'arbre ci-dessus est "ID" de chaque ligne:

id    path
a     a
b     a*b
c     a*c
d     a*c*d
e     a*c*e

Pour trouver tous les descendants d'un nœud particulier, vous feriez une requête "startWith" sur la colonne de chemin, c'est-à-dire. Tous les nœuds avec un chemin qui commence par a*c*

Pour savoir si un nœud particulier est un descendant d'un autre nœud, vous verrez si le chemin le plus long a commencé avec le chemin le plus court.

Ainsi, par exemple:

  • e est un descendant de a depuis a*c*e commence avec a
  • D est un descendant de C depuis a*c*d commence avec a*c

Cela serait-il utile dans votre instance?

Traverser n'importe quel arbre nécessitera des étapes de "profondeur d'arbre". Par conséquent, si vous maintenez une structure d'arbres équilibrée, il est prouvé que vous aurez besoin O (log n) opérations pour votre chercher opération. D'après ce que je comprends, votre arbre a l'air spécial et vous ne pouvez pas le maintenir de manière équilibrée, non? Alors Sur) sera possible. Mais c'est mauvais lors de la création de l'arbre de toute façon, donc vous mourrez probablement avant d'utiliser le chercher De toute façon...

En fonction de la fréquence à laquelle vous en aurez besoin chercher opération par rapport à insérer, vous pourriez décider de payer pendant insérer pour maintenir une structure de données supplémentaire. Je suggère un hachage si tu besoin amorti O (1). Sur chaque opération d'insertion que vous mettez tout parents d'un nœud dans un hachage. Par votre description, cela pourrait être Sur) Articles sur une donnée insérer. Si tu fais n inserts Cela semble mauvais (vers O (n ^ 2)), mais en fait, votre arbre ne peut pas se dégrader ce Mauvais, donc vous obtenez probablement une taille hastable globale de O (n log n). (En fait, le journal n La partie dépend du degration-degré de votre arbre. Si vous vous attendez à ce qu'il soit maximal de dégraed, ne le faites pas.)

Alors, tu paierais O (log n) Sur tout insérer, et obtenez une efficacité de hachage O (1) pour un chercher.

Pour un M-chemin de l'arbre, au lieu de votre tableau de bits, pourquoi ne pas tout simplement mettre le binaire "trie id" (à l'aide de M bits par niveau) à chaque nœud?Pour ton exemple (en supposant que M==2) : A=0b01, B=0b0101, C=0b1001, ...

Ensuite, vous pouvez faire le test en O(1):

bool IsParent(node* child, node* parent)
{ 
   return ((child->id & parent->id) == parent->id)
}

Vous pourriez comprimer le stockage d'ceil(lg2(M)) bits par niveau si vous avez un rapide FindMSB() fonction qui renvoie la position de le bit le plus significatif:

mask = (1<<( FindMSB(parent->id)+1) ) -1;
retunr (child->id&mask == parent->id);

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

Si vous pouvez prétraiter, tout ce que vous avez à faire est de numéroter chaque nœud et de calculer l'intervalle descendant.

Si vous ne pouvez pas prétraiter, alors un arbre lien / coupe Offre des performances O (log n) pour les mises à jour et les requêtes.

Vous pouvez répondre à la requête du formulaire "Le nœud est-il un descendant du nœud b?" En temps constant, en utilisant simplement deux tableaux auxiliaires.

Prétraitez l'arbre, en visitant en profondeur la première commande, et pour chaque nœud un magasin, son temps de départ et de fin dans la visite dans les deux tableaux commencent [] et finissent [].

Alors, disons que la fin [u] et le démarrage [u] sont respectivement la fin et l'heure de début de la visite du nœud u.

Alors le nœud u est un descendant du nœud v si et seulement si:

Démarrer [v] <= démarrer [u] et end [u] <= end [v].

Et vous avez terminé, la vérification de cette condition ne nécessite que deux recherches dans les tableaux de démarrage et de fin

Jeter un coup d'œil à Modèle d'ensemble imbriqué Il est très efficace de sélectionner mais trop lent à mettre à jour

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top