Les structures de données expliquées

Tout programme range ses données quelque part, et la manière dont il les range décide de ce qui est rapide et de ce qui est lent. Une liste d'un million de noms peut être parcourue nom par nom, ou organisée pour que vingt comparaisons trouvent n'importe quel nom. Les structures de données sont ces organisations : une poignée d'idées, pour la plupart plus anciennes que l'ordinateur personnel, présentes dans chaque base de données, système d'exploitation, navigateur et jeu.

Un arbre binaire de recherche coloré en rouge et noir, une pile de boîtes, une rangée d'alvéoles de hachage avec une chaîne de clés en collision et des flèches qui relient les nœuds d'une liste
Un arbre binaire de recherche coloré en rouge et noir, une pile de boîtes, une rangée d'alvéoles de hachage avec une chaîne de clés en collision et des flèches qui relient les nœuds d'une liste

À quoi sert une structure de données

On choisit une structure de données selon les questions auxquelles elle doit répondre. Le journal d'appels d'un téléphone veut le dernier appel en premier, les travaux d'une imprimante le plus ancien en premier, un dictionnaire le sens d'un mot parmi cent mille, un calculateur d'itinéraire le carrefour non visité le plus proche. Chaque structure rend certaines opérations rapides en renonçant à d'autres, et la notation grand O décrit ce compromis : O(1) signifie que le temps ne croît pas avec le nombre n d'éléments, O(log n) que doubler n ajoute une étape, et O(n) que le temps croît proportionnellement à n.

Piles, files et deques

Une pile ajoute et retire au même bout : dernier entré, premier sorti. Les historiques d'annulation, le bouton Retour et les appels d'un programme en cours sont des piles. Une file ajoute à l'arrière et retire à l'avant : premier entré, premier sorti, comme les frappes au clavier ou une file d'impression. Une deque permet les deux aux deux bouts. Toutes trois prennent un temps constant par opération. Une file est souvent rangée dans un tampon circulaire, un tableau fixe dans lequel l'avant et l'arrière font le tour après la fin ; quand il est plein, les éléments sont copiés dans un tableau deux fois plus grand. La copie coûte O(n), mais elle arrive si rarement que chaque opération coûte quand même O(1) en moyenne, ce qu'on appelle une borne amortie.

Listes chaînées

Une liste chaînée range chaque valeur dans un nœud doté d'un pointeur vers le nœud suivant. Insérer ou supprimer ne fait que rebrancher un pointeur ou deux, sans rien décaler, mais impossible de sauter au dixième nœud : il faut suivre les liens depuis la tête. Une liste qui ne garde que sa tête atteint la queue en O(n) étapes ; les vraies listes gardent souvent aussi un pointeur de queue, et les listes doublement chaînées un pointeur arrière, c'est ainsi qu'on construit un historique de navigation ou un cache LRU.

Arbres binaires de recherche

Un arbre binaire de recherche range, en chaque nœud, les valeurs plus petites dans le sous-arbre gauche et les plus grandes dans le droit. Une recherche compare puis va à gauche ou à droite, et un parcours infixe lit les valeurs dans l'ordre. Supprimer une feuille revient à la retirer, un nœud à un seul enfant est remplacé par cet enfant, et un nœud à deux enfants par son successeur infixe, la plus petite valeur de son sous-arbre droit. Tout cela prend un temps proportionnel à la hauteur de l'arbre : environ log n quand l'arbre est touffu, mais n quand les valeurs arrivent triées et que l'arbre dégénère en liste.

Arbres AVL et rouge-noir

Les arbres auto-équilibrés réparent leur forme après chaque modification. Un arbre AVL, inventé par Adelson-Velsky et Landis en 1962, garde les hauteurs des deux sous-arbres de chaque nœud à au plus un d'écart ; quand le facteur d'équilibre d'un nœud atteint ±2, une rotation (cas LL et RR) ou deux (LR et RL) rétablissent l'équilibre. Un arbre rouge-noir colore ses nœuds de sorte que la racine soit noire, qu'aucun nœud rouge n'ait d'enfant rouge et que chaque chemin vers le bas passe par le même nombre de nœuds noirs, ce qui limite le plus long chemin au double du plus court. Il se répare par recoloration et au plus quelques rotations, et c'est l'arbre des TreeMap de Java, de std::map en C++ et de l'ordonnanceur de Linux.

Tas et files de priorité

Un tas binaire est un arbre binaire complet rangé dans un tableau sans aucun pointeur : les enfants de la position i se trouvent en 2i + 1 et 2i + 2. Dans un tas min, chaque parent est au plus aussi grand que ses enfants, donc la plus petite valeur est toujours à la racine. Une nouvelle valeur va à la fin et remonte au-delà des parents plus grands ; extraire la racine place la dernière valeur au sommet et la fait descendre. Les deux coûtent O(log n), et un tableau entier peut devenir un tas en O(n). Les tas font tourner les files de priorité de l'algorithme de Dijkstra, des simulations d'événements et des ordonnanceurs de systèmes d'exploitation, et ils donnent le tri par tas.

Tables de hachage

Une table de hachage transforme une clé en indice de tableau grâce à une fonction de hachage et s'y rend directement. Des clés différentes peuvent tomber sur le même indice : c'est une collision. Le chaînage garde une petite liste dans chaque alvéole ; l'adressage ouvert, comme le sondage linéaire, essaie les cases suivantes jusqu'à en trouver une libre et doit laisser une pierre tombale quand une clé est supprimée, pour que les recherches suivantes continuent à sonder. Avec une bonne fonction de hachage et un taux de remplissage (clés par alvéole) maintenu bas en agrandissant la table, insertion, recherche et suppression prennent O(1) en moyenne. Une fonction médiocre, comme additionner les codes des caractères d'un mot, envoie les anagrammes dans la même alvéole. Les tables de hachage sont derrière les dict de Python, les objets JavaScript et les index des bases de données.

Tries et union-find

Un trie, ou arbre préfixe, range les chaînes à raison d'un caractère par niveau : les mots qui commencent pareil partagent un chemin et un nœud marque l'endroit où un mot se termine. Trouver un mot de longueur L prend L étapes quel que soit le nombre de mots rangés, et tous les mots d'un préfixe donné se trouvent dans un même sous-arbre : c'est ainsi que fonctionnent la saisie semi-automatique et les correcteurs orthographiques. Union-find range les éléments en ensembles disjoints, chacun un arbre dont la racine nomme l'ensemble. Find suit les liens parents jusqu'à la racine ; union accroche une racine sous une autre. Avec l'union par rang et la compression de chemin, une longue suite d'opérations coûte un temps presque constant par opération, la fonction d'Ackermann inverse α(n), qui ne dépasse pas 4 pour tout n réaliste. L'algorithme de Kruskal pour l'arbre couvrant minimal s'appuie dessus.

Questions fréquemment posées

Quelle est la différence entre un tableau et une liste chaînée ?

Un tableau range ses éléments côte à côte en mémoire, donc toute position est accessible immédiatement, mais insérer au milieu oblige à décaler tout ce qui suit. Une liste chaînée peut insérer n'importe où en changeant des pointeurs, mais atteindre une position oblige à partir de la tête. Les tableaux exploitent aussi bien mieux le cache du processeur, c'est pourquoi ils sont en pratique généralement plus rapides.

Que signifie un temps amorti ?

Le coût moyen par opération sur une longue suite, même si une opération isolée coûte parfois cher. Un tampon circulaire qui double quand il est plein copie de temps en temps ses n éléments, mais comme les copies se raréfient à mesure que le tampon grandit, n ajouts coûtent O(n) au total, soit O(1) chacun en moyenne.

Un tas est-il la même chose qu'un arbre binaire de recherche ?

Non. Un arbre binaire de recherche place chaque sous-arbre gauche avant son nœud et chaque sous-arbre droit après, il peut donc lister toutes les valeurs dans l'ordre et trouver rapidement n'importe quelle valeur. Un tas promet seulement que chaque parent passe avant ses enfants, ce qui suffit pour trouver aussitôt le minimum ou le maximum, mais pas pour chercher une valeur quelconque.

Comment union-find sait-il si deux éléments sont reliés ?

Il suit les liens parents de chaque élément jusqu'à la racine de son arbre. Si les deux aboutissent à la même racine, ils sont dans le même ensemble. La compression de chemin fait ensuite pointer chaque nœud du chemin directement sur la racine, si bien que la prochaine question à leur sujet ne prend qu'une étape.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir le visualiseur de structures de données