Discussion :

[Tokapi]

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

[Bousk]

Salut,

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

[ternel]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Médinoc]

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

[Tokapi]

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.

[ternel]

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

[Tokapi]

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