Les listes chaînées

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 parcours d'architecture le montre côté matériel. Ce que le pseudo-code appelle ici une position, la machine l'appelle une adresse, à un détail près : la machine numérote ses cases à partir de 0, le pseudo-code du cours à partir de 1.

Deux tableaux au lieu d'un

Le tableau valeur contient les données, le tableau suivant contient les liens, et rien n'impose que l'ordre des cases soit l'ordre de la chaîne : c'est même tout l'intérêt. Une tournée de maintenance visite quatre capteurs. Leurs fiches sont rangées dans l'ordre d'installation, C1 en case 1 jusqu'à C4 en case 4, mais la tournée les visite dans un autre ordre : C2, C4, C1, puis C3. Le tableau suivant enregistre cet ordre sans déplacer une seule fiche. La tête vaut 2 ; la case 2 renvoie à la case 4, la case 4 à la case 1, la case 1 à la case 3, et la case 3, dernière de la tournée, porte 0.

Parcourir ne consiste plus à compter de 1 à n, mais à suivre les liens depuis la tête jusqu'au 0 final.

17 pas, et c prend les valeurs 2, 4, 1, 3 puis 0 : elle saute d'une case à l'autre au lieu d'avancer d'un cran. La variable c n'est donc 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. Changer l'ordre de la tournée reviendrait à réécrire quelques liens, sans déplacer aucune fiche.

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 :

22 pas, dont 17 passés dans la seule boucle de décalage. Doubler le nombre de valeurs doublerait ce coût. La neuvième case est réservée d'avance, et son 0 n'est qu'un remplissage : un tableau créé avec ses valeurs garde son nombre de cases, et il faut donc prévoir celle que le décalage va occuper.

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 :

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 case 9 est la case libre, préparée d'avance comme celle du tableau ; tant qu'aucun lien n'y mène, ce qu'elle contient n'appartient pas à la chaîne. La tête joue ici le rôle du sommet de la pile du chapitre précédent : la dernière valeur insérée est la première que rencontre le parcours, et insérer en tête revient à empiler, sans rien décaler.

La liste vide n'est pas un cas particulier : tete vaut 0, le parcours ne fait aucun tour, et l'insertion en tête y fonctionne telle quelle, puisque le nouveau maillon reçoit 0 comme lien, c'est-à-dire la marque de fin.

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 :

17 pas, et la sortie donne 10, 20, 40. La ligne décisive se lit de droite à gauche : le prédécesseur reçoit le successeur de la case retirée, et la chaîne passe par-dessus elle. 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, et la case 3 ainsi libérée pourra accueillir la prochaine insertion.

Cette affectation unique suppose cependant que p soit connu, et le trouver demande de parcourir la chaîne depuis la tête, comme pour lire la n-ième valeur, que la section suivante mesure : supprimer au milieu ne déplace aucune valeur, mais ne coûte une seule affectation qu'une fois arrivé au bon endroit. Retirer la tête, qui n'a pas de prédécesseur, est le seul cas à part, et tete ← suivant[tete] y suffit.

Lire la n-ième valeur : les rôles s'inversent

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 :

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.

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.

Les deux structures échangent leurs forces. Aucune des deux structures n'est meilleure. Elles échangent leurs forces : 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 à mettre des éléments à la suite. Avec deux liens par élément au lieu d'un, la chaîne devient un arbre.

Un arbre se décrit avec quelques mots. Chaque élément est un nœud, et le nœud d'où tout part est la racine. Les deux nœuds qu'un nœud désigne par ses liens sont ses fils, gauche et droit ; tout ce qui descend d'un fils forme un sous-arbre, et un nœud sans fils est une feuille. La hauteur compte les étages, de la racine à la feuille la plus basse, et un arbre est équilibré quand ses branches ont à peu près la même hauteur, ce qui garde courte la descente depuis la racine.

Un entrepôt enregistre les références de ses articles au fil des arrivées : 8, 3, 10, 1, 6, puis 14. Rangées dans un arbre binaire de recherche, elles forment l'arbre suivant.

La racine porte 8. Ses fils sont 3 et 10, et 1, 6 et 14 sont des feuilles. Le sous-arbre gauche de la racine contient 3, 1 et 6, toutes inférieures à 8 ; son sous-arbre droit contient 10 et 14, qui ne le sont pas. L'arbre compte trois étages, et il est équilibré : aucune branche n'y est beaucoup plus longue qu'une autre.

Trois tableaux parallèles suffisent à l'écrire : valeur, gauche et droite, avec toujours 0 pour l'absence de lien. Chaque référence occupe la case de son rang d'arrivée.

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.

Ces tableaux se construisent au fil des arrivées. L'insertion descend depuis la racine en comparant, et accroche le nouveau nœud au premier lien vide rencontré. Voici l'insertion de 6, cinquième valeur arrivée, rangée en case 5. La descente part de la racine, en case 1, qui porte 8. Comme 6 est plus petit, elle regarde à gauche : gauche[1] vaut 2, ce lien n'est pas vide, et la descente passe en case 2, qui porte 3. Comme 6 n'est pas plus petit que 3, elle regarde à droite : droite[2] vaut 0, la place est libre, et droite[2] reçoit 5.

L'algorithme suivant répète cette descente pour chacune des six valeurs. La variable c est la case où se trouve la descente, et place passe à Vrai quand le nouveau nœud est accroché, ce qui arrête le TantQue. La toute première valeur n'a rien à chercher, puisqu'elle devient la racine : c'est le rôle du test Si n > 1.

104 pas, et les trois tableaux en sortie sont exactement ceux du tableau précédent.

Chercher revient alors à descendre : à chaque nœud, une seule comparaison élimine tout un sous-arbre. Pour savoir si la référence 14 est enregistrée, la descente suit le chemin coloré de la figure de l'arbre.

19 pas et deux descentes seulement pour atteindre 14, au fond de l'arbre. Le champ de saisie de la figure accepte une autre cible : avec 7, absente de l'arbre, la descente passe par 8, 3 et 6, tombe sur un lien nul, et l'algorithme le dit en 22 pas. Ce cas n'est possible que parce que la condition teste c <> 0 avant valeur[c] : ET n'examine sa partie droite que si sa partie gauche est vraie, et la règle posée au chapitre sur les tris s'applique telle quelle. Dans l'autre ordre, la figure réclamerait valeur[0], qui n'existe pas.

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.

48 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é 104 pas à construire, et deux descentes pour trouver 14. Voici le même algorithme, mot pour mot, nourri des mêmes six références arrivées cette fois dans l'ordre croissant, comme les livrerait un fichier déjà trié.

150 pas au lieu de 104, 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. Sa hauteur est de six étages, contre trois pour l'arbre équilibré des mêmes valeurs.

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.

Mettre en pratique

Un lien suivi, une valeur décalée, un étage descendu : chacun de ces coûts se compte à partir des données, sans dérouler aucune figure.

Les deux dernières questions portent sur les mêmes références : seul leur ordre d'arrivée sépare les deux réponses.

Exercice 1, La longueur d'une tournée

Une tournée d'inspection de vannes est rangée en deux tableaux parallèles, et sa tête vaut 5. Les cases 2 et 3 portent deux vannes retirées de la tournée : elles forment encore entre elles une petite chaîne, de la case 3 à la case 2, mais aucun lien parti de la tête n'y mène. Écrire un algorithme qui compte les vannes réellement visitées.