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