Par Godrik (godrik-article@mandragor.org) Cet article sera assez court. Il présente les avantages et les inconvénients des deux façons les plus connues d'implémenter un arbre (disons binaire). Les exemples seront en C (ou pseudo C)
De la bonne implémentation des arbres.Par Godrik (godrik-article@mandragor.org) Cet article sera assez court. Il présente les avantages et les inconvénients des deux façons les plus connues d'implémenter un arbre (disons binaire). Les exemples seront en C (ou pseudo C)
L'arbre des famillesAlors les arbres dans leur forme la plus standard ressemblent à:
struct arbre
{
struct arbre* filsGauche;//NULL si pas de fils
struct arbre* filsDroit;//NULL si pas de fils
void* valeur;
};
Donc ça c'est pas trop mal. C'est assez standard, on voit facilement comment on l'utilise. On sent les mallocs arriver à la pelle et les delete (heu, free du C j'ai dis) aussi. En gros, on va avoir des :
struct arbre* creeArbre (void* valeur)
{
struct arbre* toto = (struct arbre*) malloc (sizeof(struct arbre));
toto->filsGauche = NULL;
toto->filsDroit = NULL;
toto->valeur = valeur;
return toto;
}
Bref, on voit bien la tête que ça va avoir. Mais à force de faire des opérations sur les arbres on risque de faire plein de malloc/free et consommer plein de ressources.
CimetièreAlors on peut optimiser ça un peu, on faisant un cimetière. C'est quoi donc un cimetière? Quand on détruit un struct arbre, au lieu de le free-er, on va le mettre dans une pile quelque part Et la prochaine fois qu'on a besoin de creer un struct arbre, on commence par le chercher dans la pile. Ca permet de faire moins d'appel a malloc/free.
Mais dans l'ensemble ça fait gagner du temps. Bien sur, il ne faut pas que la mémoire de la machine soit trop petite et qu'on ait pas de pic de consommation...
Ca a l'air bien comme ça comme formulation des arbres, mais on peut peut-être faire mieux. Alors oui on peut faire mieux(enfin, pas pareil), et c'est ce que l'on va voir tout de suite.
Avec des tableauxQu'est ce qui pourrait rendre les algorithmes sur les arbres lents. La récursivité, on n'y peut pas grand chose, et un autre article explique déjà comment optimiser les recursions.
Le problème vient de la gestion de la mémoire comme on a dit. Alors on pourrait essayer d'utiliser la structure de donnée la plus simple pour stocker notre arbre : A savoir, un tableau. Je vous vois arriver, vous aller dire: "le godrik, il nous a pété une durite, les arbres et les tableau c'est assez éloigné!". Bah oui, c'est assez éloigné, mais essayons quand même et regardons ce que ça donne.
On va dire que chaque case de notre tableau, c'est un noeud. Et que tout le tableau c'est l'arbre. Alors que devient notre structure:
struct noeud
{
int filsGauche;//-1 si pas de fils
int filsDroit;//-1 si pas de fils
void* valeur;
};
Ça ressemble assez a l'ancienne formulation et d'un seul coup on voit beaucoup mieux comment ça va faire.
Mais il reste plusieurs questions. Notre tableau va avoir une taille fixe. Et notre arbre, il peut être dynamique. C'est la que ça se complique, mais pas tant que ça. Parce que dans 90% des cas, on a une estimation de la taille maximale de notre tableau. Donc on fait un tableau de la taille max et on est tranquille. Au pire, vector est votre ami et on en parle plus. Et la se pose la deuxième question, il va y avoir des cases sans noeud, et comment retrouve t'on la racine ? Bah, pour la racine, soit on fixe que 0 c'est toujours la racine; soit on stocke un entier en plus pour identifier la racine. Et pour les cases vides? En effet ça arrive assez souvent (tout le temps même) mais la, on a plusieurs façon de voir. Soit on considère que seul les premières cases du tableau sont utilisées et que le reste (la partie droite) est non-utilisé. Soit on rajoute un booleen dans la structure (heu, j'ai dit C pas C++, mais vous avez compris) qui indique si la case est utilisée ou non. Ce qui permet de faire la distinction.
Eventuellement, d'ailleurs si on fait beaucoup de création/destruction dans l'arbre, on peut rajouter une pile a notre structure qui stocke la position des case non utilise. Enfin, c'est assez simple à faire en somme.
Efficacité comparéOn en vient a se demander la quel des deux méthode est la plus efficace. La, je vais vous faire une réponse de normand: "bah, ça dépend!" Si on a une bonne borne supérieure de la taille de l'arbre, alors la deuxième va vraiment être génial. Si on en a pas, ça va devenir vraiment plus compliqueré. On peut toujours considérer qu'on a plein de ram et que ça ira bien. Mais non en fait, parce qu'on a plein de mémoire, mais pas forcement plein de cache processeur...
Bon et la première, bah, elle fait plein d'allocation/désallocation donc en général ce n'est pas très rapide (même si on optimise avec un cimetière). Et en plus, comme c'est fait dynamiquement, il y a des chances que deux noeuds ne soit pas adjacents en mémoire. Donc ça veut dire plein de défaut de cache, et donc plein de temps d'attente.
ConclusionsEn somme: Deux structures d'arbres sont disponibles. Une sous forme de tableau qui est efficace lorsque l'on peut borner précisément la taille de l'arbre. Une plus classique rendu efficace par sa "forme objet" et par la possibilité de pouvoir avoir des arbres de taille infini.
Ce ne sont bien sur pas les seules solutions envisageables pour faire des arbres, et bien d'autres doivent être efficace.
Comme d'habitude, pour toute remarque vous avez mon adresse ou l'espace de libre discutions ci dessous! :)
