Arbres
Introductions aux dictionnaires
Un des problèmes les plus fréquents qui arrivent en informatique est celui des dictionnaires. Son principe est simple : on possède un ensemble d'objets, et à chaque objet est associé une clef. La question est : si on nous donne une clef, comment retrouver le plus rapidement possible l'objet qui y correspond ?
Aujourd'hui, ce problème est à peu près résolu, soit par l'utilisation d'arbres, soit par l'emploi de tables de hashages. Cette seconde méthode sera vue dans le prochain chapitre.
Avant toutes choses, prenons un exemple pratique (sinon on ne va plus s'y retrouver). Il s'agit de programmer un petit annuaire. On donne le nom de la personne, et on désire avoir son adresse ou des informations du même tonneau. On supposera, pour simplifier, que deux personnes ont toujours deux noms différents.
Arbres binaires
Une solution habituelle, c'est d'utiliser le classement alphabétique. Finalement, en moyenne, si vous avez N personnes dans votre annuaire, vous devrez parcourir N/26 noms avant de tomber sur le bon. On voit bien ici que l'utilisation d'un index par ordre alphabétique est une bonne chose, mais moi, je vais vous proposer mieux.
Connaissez-vous le principe de la recherche dichotomique ? Le terme est barbare, mais il signifie « la recherche par plus grand ou plus petit ». Le petit jeu à la con qui consiste à faire deviner un nombre à quelqu'un, en lui disant à chaque proposition si la proposition qu'il vous fait est plus grande ou plus petite que la bonne réponse, c'est une recherche dichotomique. Le terme dichotomique signifie en gros « diviser par deux », et c'est bien de cela qu'il s'agit : si on ne joue pas comme un pied à ce jeu, on peut toujours se débrouiller pour éliminer la moitié des choix possibles à chaque test.
Alors nous aussi on va jouer à un petit jeu. Imaginons que vous cherchiez l'adresse de Dupont (comme c'est original !). Vous entrez dans un drôle de labyrinthe, ou chaque pièce à une entrée et deux sorties. De plus, dans chaque pièce est noté un nom et une adresse. Il est également noté : « si le nom que vous cherchez est plus petit par ordre alphabétique que ce nom-ci, continuez votre chemin par la porte de gauche. Si il est plus grand, continuez à droite. Et si c'est celui-ci, ben vous avez trouvé votre réponse, idiot ! »
Par combien de portes, en moyenne, allez-vous passer avant de trouver la bonne réponse ? En fait, si le truc est a peu près bien organisé, à chaque étape (chaque test), vous éliminez la moitié des possibilités. Si vous partez avec un carnet de 256 noms, après la première pièce il ne vous reste plus que 128 noms possibles. Puis 64, puis 32, etc... Bref, le nombre de tests que vous devez faire, c'est Log(N).
Bon, alors faisons un petit dessin de la situation pour comprendre ce qui s'est passé pendant notre petite balade :
L'avantage du truc est assez énorme : même si il y a quelques millions de noms dans l'annuaire, on peut calculer qu'il nous faudra parcourir moins d'une trentaine d'éléments. La seule grosse difficulté, c'est de savoir comment programmer un tel bidule, qu'on appelle un arbre.
Alors faisons un tout petit peu de vocabulaire : on dit d'un élément d'un arbre qu'il est un noeud. Le tout premier élément, Roger dans notre exemple, est appelé la racine de l'arbre. Il y a vraiment beaucoup de choses à dire sur les arbres, si je devais tout voir dans le détail ça me prendrait une centaine de pages facilement, alors vu qu'ici je ne m'intéresse qu'aux dictionaires, je me contenterai de voir les caractéristiques de dictionnaire qu'un arbre peut avoir.
Bref, dans un dictionnaire, on peut avoir envie de faire trois choses : consulter, rajouter un élément, supprimer un élément.
Pour construire l'arbre, on va utiliser un peu le même principe que la liste simplement chaînée, sauf qu'au lieu d'avoir un next par élément, ici il y en aura deux : le next de gauche, et le next de droite (appelés fils de gauche et fils de droite). La structure à utiliser ressemble dès lors à ceci :
| C | Pascal |
|---|---|
struct item { char* name; char* street; (...) } struct node { item* data; node* left; node* right; }
|
Type TItem=Record Name:String; Street:String; (...) End; PNode=^TNode; TNode=Record Item:^TItem; Left:PNode; Right:PNode; End;
|
Encore un petit dessin[3] :
Et on peut continuer ça très longtemps, c'est juste que j'arrive à court de place sur la page...
Alors la consultation est assez simple, voici en gros ce que donne l'algorithme (en général de manière récursive) :
- Regarder le data de la racine, et comparer le nom cherché avec le nom de l'item de cette racine
- Si le nom correspond, c'est gagné, on a notre réponse
- Si le nom est plus petit (par ordre alphabétique), on recommence à l'étape 1 avec le noeud de gauche à la place de la racine.
- Si le nom est plus grand, on recommence à l'étape 1 avec le noeud de droite à la place de la racine.
Si, à un moment, on tombe sur un noeud qui n'a pas de fils à gauche si on veut aller à gauche, ou de fils à droite si on veut aller à droite, bref si on se retrouve bloqué comme un con sans avoir par où aller, ça ne veut dire qu'une seule chose : la personne recherchée ne se trouve nulle part dans l'arbre. Par exemple, si je recherche Timonier dans le premier exemple, voilà le chemin que ça va donner :
Ach ! Grosse malheur ! Nous voila bien ennuyés, nous ne savons pas continuer la petite balade : en effet, Timonier ne se trouve nulle part dans l'arbre. Ceci dit, l'endroit où nous sommes bloqués serait un bon endroit pour rajouter Timonier, non ? Poum, nous avons tout de suite notre méthode pour rajouter un élément : trouver l'endroit où l'on bloque quand on recherche ce nouvel élément, et le rajouter à cet endroit :
Cette façon de procéder est assez simple, mais elle possède un gros désavantage : rien ne nous garanti que l'arbre restera bien équilibré, comme il l'était sur mon exemple. Par exemple, si on désire rajouter tous les éléments dans l'arbre par ordre alphabétique, ben la structure de l'arbre ressemblera à ceci :
Ce qui revient à faire une simple liste chaînée ! Il existe donc des méthodes dites de « rééquilibrage » de l'arbre, mais ça devient un rien compliqué et je vous laisserai donc vous documenter par vous-même. Gardez juste à l'esprit que si vous utiliser un simple arbre binaire avec la méthode que je vous ai donnée, le caractère logarithmique peut parfois laisser place à un comportement linéaire.
Pour supprimer un noeud, la méthode devient plus subtile, je vous laisse également y réfléchir, mais j'ai dans l'idée que j'écrirai bientôt un tutoriel sur les algorithmes récursifs par délégation, sujet totalement passionnant où les arbres vivent une vie pleine de joies et de délicatesses.
Arbres quelconques
On peut très facilement passer de la notion de l'arbre binaire (chaque noeud a au plus deux fils) à un arbre quelconque. Au lieu d'avoir deux variables, left et right, il suffit que chaque noeud possède une liste chaînée de fils, tout bêtement... Vu qu'à présent vous devez être devenus des kingz de l'utilisation des listes chaînées, cela ne devrait plus vous poser le moindre problème. Si il faut absolument vous faire un dessin, ça va donner :
| C | Pascal |
|---|---|
struct node; struct linkedItem { node* child; linkedItem* next; }; struct node { item* data; linkedItem* firstChild; };
|
Type PLinkedItem=^TLinkedItem; TNode=Record Data:PItem; FirstChild:PLinkedItem; End; TLinkedItem=Record Child:TNode; Next:PLinkedItem; End;
|
Voilà la manière classique de stocker une arborescence de fichier en mémoire. J'ai mis en rouge la liste chaînée, et en vert les données des répertoires en elles-mêmes. En noir, ce sont les noeuds de l'arbre.