Voici un problème que j’ai rencontré il y à de cela quelque jours dans le carde du développement d’un algorithme génétique. En effet mon algo devais trouver une formule mathématique.
J’ai donc implanté une solution en C/C++, grâce à un arbre binaire, dont les nœuds sont des fonction (à savoir sin,+,-,/,*) et les feuilles des constantes.
J’ai également deux fonctions, qui me permettent de faire une mutation sur l’arbre, et un cross over pour la création d’un nouvel individus. Le problème est que, pour ces deux fonction, je doit accéder à un nœud précis, tiré aléatoirement (entre 1 et n, où n est le nombre de nœuds total de l’arbre). Du fait que l’arbre n’est pas équilibré, il se pose donc un problème, à savoir, comment le trouver rapidement?

Une solution naïve, mais non optimal, est de faire un parcourt total de l’arbre pour connaître N, tirer X (random(1,n)), puis refaire un parcourt pour enfin avoir le nœud voulu. Ça marche … mais voilà, on peut mieux faire que du O(2N).

Avant de continuer, une implémentation possible du problème:

La première chose que l’on remarque, est le parcourt complet de l’arbre pour connaître N, qui ralentie énormément. On peut donc le stoker, et le mettre à jour en temps voulu. On obtient alors :

De cet façon, chaque nœud connais le nombre de nœud de son sous arbre. Si c’est une feuille, la valeur est de 1 (pour des raison pratique pour la suite). C’est bien beau, mais on est toujours en O(n) en terme de complexité. Il y a tout de même une solution. J’ai mis un petit moment à la trouver, mais voici celle à laquelle j’ai pensé:

• À Chaque nœud sera associé un numéro (fictif)
• Chaque nœud dois avoir un numéro plus grand que chacun de ses fils (direct ou non).
• Le numéro le plus grand doit être égale au nombre de nœud total de l’arbre (n).

Une des conséquence est que le numéro de la racine est le nombre totale de nœud, soit nb_sub_nodes: On peut donc appliquer ce raisonnement à chaque sous nœud, et on obtient alors une suite, en O(log2(n)).

Voici donc une implémentation:

De cette façon, on a un accès beaucoup plus rapide à un nœud aléatoirement choisie, entre O(Cst) < O(log2(n) < x (avec n = nombre de neud total, x l’index cherché) En effet dans le cas d’un arbre linéaire (un seul fils à chaque fois), on me gagne rien. En moyenne, on tombe à du log2(n).

En espérant que cela soit utile à quelqu’un d’autre que moi.