Chaîner les données
Ce que ce chapitre apporte
- Représenter une liste chaînée par deux tableaux parallèles, valeur et suivant.
- Insérer en tête et supprimer au milieu sans déplacer aucune valeur.
- Comparer au compteur de pas ce qu'une liste rend immédiat et ce qu'elle rend coûteux.
- Construire un arbre binaire de recherche en trois tableaux, puis y chercher une valeur.
- Expliquer ce que devient un arbre binaire de recherche nourri de valeurs déjà triées.
Un tableau range ses valeurs côte à côte, et cette contiguïté décide de tout : lire la n-ième case est immédiat, insérer au début oblige à tout décaler. Chaîner consiste à renoncer au côte à côte et à faire désigner par chaque valeur celle qui la suit. Les deux coûts s'inversent alors exactement, et le compteur de pas le montre sans qu'il faille l'affirmer.
Ce pseudo-code ne connaît pas d'enregistrement : impossible de fabriquer une case qui contiendrait à la fois une valeur et un lien. La contrainte oblige à écrire les structures chaînées en tableaux parallèles, un tableau par champ, la même position désignant partout le même élément. Loin d'être un pis-aller, c'est la description exacte de ce que fait une machine : la mémoire est un long tableau de cases numérotées, et le module d'architecture le montre côté matériel. Ce que le pseudo-code appelle ici une position, la machine l'appelle une adresse.
Deux tableaux au lieu d'un
Une liste chaînée est une suite d'éléments dont chacun porte, en plus de sa valeur, la position de son successeur. Une position convenue, ici 0, marque la fin de la chaîne. Une variable retient la position du premier élément : c'est la tête, et sans elle la liste est perdue.
Le tableau valeur contient les données, le tableau suivant contient les liens. Rien n'impose que l'ordre des cases soit l'ordre de la chaîne : c'est même tout l'intérêt.
| Position | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
valeur | 10 | 20 | 30 | 40 |
suivant | 2 | 3 | 4 | 0 |
Parcourir ne consiste plus à compter de 1 à n, mais à suivre les liens jusqu'au 0 final.
programme principal
17 pas. La variable c n'est pas un compteur : c'est une position courante, et elle ne progresse que parce que la case où elle se trouve lui dit où aller. C'est la différence de fond avec le parcours d'un tableau, où l'indice avance tout seul.
Écrire TantQue suivant[c] <> 0 au lieu de TantQue c <> 0. La boucle s'arrête alors avant d'avoir traité le dernier élément, qui est justement celui dont le lien vaut 0. Le test porte sur la position où l'on se trouve, jamais sur celle où l'on va.
Insérer en tête : le décalage contre trois affectations
Voici la comparaison qui justifie la structure. Huit valeurs, une neuvième à placer en première position.
Sur un tableau, toutes les valeurs doivent reculer d'une case, en partant de la fin pour ne rien écraser :
programme principal
22 pas, dont 17 passés dans la seule boucle de décalage. Doubler le nombre de valeurs doublerait ce coût.
Sur une liste, rien ne bouge. La nouvelle valeur se pose dans une case libre, son lien désigne l'ancienne tête, et la tête change de valeur :
programme principal
8 pas, dont trois pour l'insertion proprement dite. Le nombre d'éléments déjà présents n'y change rien : ce serait trois affectations sur huit valeurs comme sur huit mille.
La suppression obéit à la même logique. Retirer le troisième élément d'une chaîne ne demande pas de reboucher un trou, mais de faire pointer son prédécesseur par-dessus lui :
programme principal
15 pas, et la sortie donne 10, 20, 40. La valeur 30 est toujours dans le tableau valeur, intacte ; elle a simplement cessé d'appartenir à la chaîne. Une case qui n'est sur le chemin de personne n'existe plus, du point de vue de la liste.
Lire la n-ième valeur : l'inverse exact
L'avantage se paie, et il se paie sur l'accès direct. Dans un tableau, la sixième valeur est à l'indice 6, sans discussion :
programme principal
2 pas. Dans une liste, la sixième valeur n'est nulle part en particulier : il faut partir de la tête et suivre cinq liens.
programme principal
16 pas pour le même résultat, et ce coût grandit avec le rang demandé, tandis que celui du tableau ne bouge jamais.
| Opération sur huit valeurs | Tableau | Liste chaînée |
|---|---|---|
| Insérer en tête | 22 pas | 8 pas |
| Lire la sixième valeur | 2 pas | 16 pas |
Aucune des deux structures n'est meilleure. Elles échangent leurs coûts terme à terme : ce que la contiguïté offre à la lecture, elle le reprend à l'insertion, et le chaînage fait l'inverse. Le choix se décide sur l'opération la plus fréquente dans l'usage visé, et non sur une préférence.
L'arbre binaire de recherche
Chaîner ne se limite pas à une file d'attente d'éléments. Avec deux liens par élément au lieu d'un, la chaîne devient un arbre.
Un arbre binaire de recherche est un arbre où chaque nœud porte une valeur, un lien vers un sous-arbre gauche et un lien vers un sous-arbre droit, avec cette règle : tout ce qui est à gauche d'un nœud lui est inférieur, tout ce qui est à droite lui est supérieur ou égal. La règle vaut pour chaque nœud, pas seulement pour la racine.
Trois tableaux parallèles suffisent : valeur, gauche et droite, avec toujours 0 pour l'absence de lien. L'insertion descend depuis la racine en comparant, et accroche le nouveau nœud au premier lien vide rencontré.
programme principal
113 pas, et trois tableaux en sortie :
| Position | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
valeur | 8 | 3 | 10 | 1 | 6 | 14 |
gauche | 2 | 4 | 0 | 0 | 0 | 0 |
droite | 3 | 5 | 6 | 0 | 0 | 0 |
La racine est en position 1, elle porte 8, son fils gauche est en position 2 (la valeur 3) et son fils droit en position 3 (la valeur 10). Chaque nœud est rangé là où il y avait de la place, et la forme de l'arbre n'est inscrite nulle part ailleurs que dans les liens.
Chercher revient alors à descendre : à chaque nœud, une seule comparaison élimine tout un côté.
programme principal
19 pas et deux descentes seulement pour atteindre 14, au fond de l'arbre. Remplacer cible par une valeur absente fait sortir la boucle sur un lien nul, et l'algorithme le dit.
Parcourir un arbre dans l'ordre
La règle de placement a une conséquence remarquable : visiter d'abord tout le sous-arbre gauche, puis le nœud, puis tout le sous-arbre droit rend les valeurs triées. C'est le parcours infixe, et il s'écrit naturellement par récursion, chaque sous-arbre se traitant comme un arbre.
programme principal
35 pas, et la sortie est 1, 3, 6, 8, 10, 14. La pile des appels affichée par la figure mérite d'être suivie : elle monte jusqu'à cinq cadres, et le nœud n'est écrit qu'au retour du premier appel, jamais avant. Le cas de base est ici un lien nul, qui ne fait rien du tout : c'est la forme la plus économique de cas de base, celle qui n'a pas besoin d'être traitée à part.
Ce qui arrive aux valeurs déjà triées
L'arbre précédent a coûté 113 pas à construire, et deux descentes pour trouver 14. Voici le même algorithme, mot pour mot, nourri des mêmes six valeurs dans l'ordre croissant.
programme principal
155 pas au lieu de 113, et surtout un tableau gauche entièrement nul : [0, 0, 0, 0, 0, 0]. Chaque valeur, plus grande que toutes les précédentes, s'est accrochée à droite de la dernière. L'arbre n'a plus aucune branche gauche : c'est un peigne, et un peigne n'est rien d'autre qu'une liste chaînée déguisée en arbre.
programme principal
34 pas et cinq descentes, contre 19 pas et deux descentes sur l'arbre équilibré, pour chercher la même valeur dans les mêmes six données. Aucune comparaison n'élimine plus rien : la recherche parcourt tout, exactement comme dans une liste.
L'arbre binaire de recherche n'est donc rapide que tant qu'il reste équilibré, et l'ordre d'arrivée des données suffit à le ruiner. Le cas fatal, insérer des valeurs déjà triées, est aussi le plus probable en pratique : les données arrivent souvent d'un fichier ou d'une base qui les a déjà rangées. Des arbres qui se rééquilibrent seuls à chaque insertion existent pour cette raison ; leur mécanique dépasse ce parcours, mais le problème qu'ils résolvent est exactement celui qui vient d'être mesuré.
Vérification
1.Dans une liste chaînée en deux tableaux, à quoi sert la valeur 0 dans suivant ?
2.Insérer une valeur en tête coûte 22 pas sur un tableau de huit valeurs et 8 pas sur une liste. Pourquoi ?
3.Lire la sixième valeur coûte 2 pas sur un tableau et 16 sur une liste chaînée. Qu'est-ce que cela illustre ?
4.Que produit le parcours infixe d'un arbre binaire de recherche ?
5.Un arbre binaire de recherche reçoit des valeurs déjà triées. Que devient-il ?
La méthode
- Ouvrir un tableau par champ et tenir la règle : la même position désigne partout le même élément, et 0 signifie l'absence.
- Retenir la tête à part. Une liste chaînée dont la tête est perdue est intégralement perdue, quelles que soient les valeurs encore présentes dans les tableaux.
- Avancer par position courante, jamais par compteur : le parcours s'arrête quand la position vaut 0, pas quand un indice atteint une borne.
- Choisir la structure sur l'opération la plus fréquente, insertion ou accès direct, et vérifier le choix au compteur de pas plutôt qu'au ressenti.
- Accrocher un nouveau nœud d'arbre au premier lien nul rencontré, après être descendu depuis la racine en comparant à chaque étage.
- Se méfier des données déjà triées avant toute insertion dans un arbre binaire de recherche, et mélanger l'ordre d'arrivée si rien ne rééquilibre l'arbre.
Synthèse
- Une liste chaînée s'écrit en deux tableaux parallèles,
valeuretsuivant, avec 0 pour marquer la fin et une variable pour retenir la tête. - L'insertion en tête et la suppression au milieu ne déplacent aucune valeur : elles ne touchent qu'aux liens, en trois affectations ou en une seule.
- Le prix de ce chaînage est l'accès direct : 2 pas sur un tableau contre 16 sur une liste pour la même sixième valeur.
- Un arbre binaire de recherche tient en trois tableaux,
valeur,gaucheetdroite; son parcours infixe rend les valeurs triées. - Nourri de valeurs déjà triées, cet arbre dégénère en peigne et perd tout son avantage, ce que le compteur de pas chiffre à 34 contre 19.
Le chapitre suivant change de nature : plutôt que de mesurer ce qu'un algorithme coûte, il s'agira de démontrer qu'il est juste, ce qu'aucun jeu d'essai ne fera jamais. C'est l'objet de prouver un algorithme.