Comment incrémenter une valeur contenue dans tous les pères d'un nœud d'un arbre en temps constant ?

Bonjour à tous.

Je suis en train de développer en C++ un algorithme qui crée un arbre en temps linéaire (du nombre de feuilles).

Chaque nœud de cet arbre contient actuellement un compteur qui doit être incrémenté à chaque fois qu'une opération sur l'un des fils dudit nœud est réalisée. Pour faire cette mise à jour, j'ai actuellement besoin de remonter tous les pères du nœud manipulé jusqu'à la racine pour incrémenter leurs compteurs. Le problème est que cette opération casse la complexité de mon algorithme et la transforme en O(n²) au lieu de O(n).

Je cherche donc une solution raisonnable qui me permette, à chaque fois que je manipule un nœud, de changer en mémoire une seule valeur sur laquelle "pointent" tous les pères (et seulement eux, pas les fils) du nœud manipulé, de manière à ce que le fait de modifier cette valeur soit équivalent à incrémenter tous leurs compteurs d'un coup.

D'après vous existe-il une telle solution svp ?

Merci d'avance :)

Salut,

un pointeur du/des compteur(s) du/des père(s) chez les enfants ?

le problème, c'est que chaque père peut avoir plusieurs fils (puisque c'est un arbre)
avoir un lien vers le pere peut servir, mais pas sur les compteurs de chaque pere.

D'ailleurs, il devrait probablement y avoir une fonction qui augmente le lien du noeud courant, et s'appelle récursivement sur le père.

Code:

---

1 2 3 4

void inc() { ++compteur; pere->inc(); }

---

De toute facon, tu veux modifier tous les compteurs, il n'y a pas le choix, c'est N²
Par contre, tu peux aussi ne pas modifier les pères, et au choix ne mettre à jour qu'après ou additionner les compteurs personnels.

Normalement si c'est bien fait, ce sera plutôt du N⋅log(N) que du N²...

Je ne sais pas exactement... En fait, le compteur compte pour chaque père le nombre de toutes les feuilles qui en sont issues (sachant qu'une fois une feuille créée on n'y touche plus), du coup pour l'instant je suis allé au plus simple et à chaque fois que je crée une feuille je parcours tous ses pères jusqu'à la racine et incrémente leurs compteurs un par un.

Au début j'avais essayé de gérer les compteurs en additionnant les compteurs personnels comme préconise leternel, ça marche très bien dans mon algo naïf mais là j'implémente une adaptation de l'algorithme d'Ukkonen et ça marche beaucoup moins bien car l'algorithme "saute" d'une branche à l'autre quand il ajoute un nouveau nœud et peut ajouter ce nœud à n'importe quel niveau de la branche.

Merci pour vos réponses.

Est-ce que ton programme procède en deux temps: création des feuilles, puis utilisation du nombre de feuilles?

Du coup c'est pour ça que ça aurait été super bien d'avoir dans chaque fils quelque chose qui "pointe" sur tous ses pères à la fois, je l'aurais incrémenté à chaque création de feuille et ça aurait magiquement incrémenté d'un seul coup la bonne valeur pour tous ses pères :calim2:

Oui en effet les compteurs ne sont utiles qu'après, pas lors de la création de l'arbre, donc s'il existe une manière optimale de les mettre à jour après la création de l'arbre (qui elle se fait en O(n)) c'est bien aussi.

en N, oui, mais en N = nombre de noeud, pas N = nombre de feuille.
Tu pars de la racine, et pour chaque noeud, son nombre de feuilles est la somme du nombre de feuilles de chacun de ses fils + le nombre de fils qui sont des feuilles.

Du coup je l'ai fait de cette manière après avoir adapté Ukkonen (chaque noeud qui n'est pas une feuille a son compteur à zéro) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

unsigned int Noeud::calculerCompteurs() // calcule tous les compteurs à partir de la racine (à utiliser une seule fois et seulement à la racine dans l'algo opti) { unsigned int tailleFils = fils.size();   for(unsigned int i = 0; i < tailleFils; i++) { compteur += fils[i].calculerCompteurs(); }   return compteur; }

---

Je ne sais pas si c'est la meilleure méthode possible en complexité, mais ça marche.

C'est optimal, a un facteur constant près, car tu dois parcourir tes données.

Salut,

Et si tu te dépeches de remplacer la variable locale compteur par une donnée membre de ta classe, associée à un booléen évalué à true ou à false (selon qu'il faille effectivement compter les noeuds, ou que cela ait déjà été fait depuis le dernier ajout d'éléments), tant que le nombre d'enfants (et de descendants des enfants) n'a pas changé, tu ne devras même pas passer ton temps à parcourir à chaque fois tout ton arbre pour avoir la réponse ;)

(on appelle cela la "mise en cache" d'une information ;) )

Si tu n'as, effectivement, plus de modification au niveau des enfants (et des descendants) une fois que tu as fini de créer ton arbre, le "temps de calcul" (comprend : le fait d’exécuter cette boucle de manière récursive) sera rapidement amorti au travers de toutes les fois où... tu n'auras plus à le refaire ;) (au dépends, il est vrai, de l'augmentation de "quelques bytes" de la taille requise pour représenter chaque noeud)

Citation:

---

Et si tu te dépeches de remplacer la variable locale compteur par une donnée membre de ta classe, associée à un booléen évalué à true ou à false (selon qu'il faille effectivement compter les noeuds, ou que cela ait déjà été fait depuis le dernier ajout d'éléments), tant que le nombre d'enfants (et de descendants des enfants) n'a pas changé, tu ne devras même pas passer ton temps à parcourir à chaque fois tout ton arbre pour avoir la réponse

---

En effet, et quand je vois ça:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

unsigned int Noeud::calculerCompteurs() // calcule tous les compteurs à partir de la racine (à utiliser une seule fois et seulement à la racine dans l'algo opti) { unsigned int tailleFils = fils.size(); for(unsigned int i = 0; i < tailleFils; i++) { compteur += fils[i].calculerCompteurs(); } return compteur; }

---

Je me dis que tu mets en cache le nombre de fils/sous-fils lorsque tu ajoute ou supprimer un fils en remontant aux parents. Tu parcourras donc une fois à l'ajout/suppression de fils en remontant les parents et tu accéderas au nombre d'enfants en O1 car mise en cache.