Structures de données : questions d’entraînement avec explications

1Ce qu’est une structure de données

Une structure de données est une manière d’organiser les données en mémoire pour que certaines opérations soient rapides : trouver un élément, en ajouter un, en supprimer un.

Aucune structure n’est rapide pour tout. Choisir une structure, c’est choisir quelles opérations doivent être peu coûteuses. Leurs coûts s’écrivent en notation grand O, avec n le nombre d’éléments.

Les deux briques de base sont le tableau et la liste chaînée.

Un tableau range ses éléments dans un seul bloc de mémoire, les uns après les autres. L’ordinateur peut calculer où se trouve l’élément i, donc lire a[i] coûte O(1). Insérer au début oblige à décaler tous les éléments : O(n).

Une liste chaînée range chaque élément dans un nœud muni d’un pointeur vers le nœud suivant. Le dernier pointeur est nul. Insérer en tête (h) ne modifie qu’un seul pointeur : O(1). Mais pour atteindre l’élément i, il faut suivre i pointeurs : O(n).

Une liste doublement chaînée possède aussi un pointeur vers le nœud précédent, ce qui permet de la parcourir dans les deux sens.

2Piles et files

Une pile ressemble à une pile d’assiettes : on n’ajoute et on ne retire qu’au sommet. Le dernier élément entré est le premier sorti : LIFO.

• push (empiler) place un élément au sommet, pop (dépiler) retire l’élément du sommet, peek lit le sommet sans le retirer. Toutes ces opérations sont en O(1).
• Utilisations : la fonction d’annulation d’un éditeur, la pile d’appels d’un programme, la vérification de l’équilibre des parenthèses, le parcours en profondeur.

Une file ressemble à la queue devant une caisse : on se place à l’arrière et on part par l’avant. Le premier élément entré est le premier sorti : FIFO.

• enqueue (enfiler) ajoute à l’arrière, dequeue (défiler) retire à l’avant. Les deux sont en O(1).
• Utilisations : les travaux d’impression, les messages en attente de traitement, le parcours en largeur.

Une deque (file à double extrémité) permet d’ajouter et de retirer aux deux extrémités. Une file de priorité retire toujours en premier l’élément de plus haute priorité ; elle est généralement construite sous forme de tas.

3Arbres, tas, tables de hachage et graphes

Un arbre possède un nœud supérieur, la racine. Tous les autres nœuds ont exactement un parent. Les nœuds sans enfant sont des feuilles. Un arbre de n nœuds a n − 1 arêtes.

Dans un arbre binaire, chaque nœud a au plus deux enfants. Un arbre binaire de recherche (ABR) ajoute une règle : les clés du sous-arbre gauche sont plus petites que le nœud, celles du sous-arbre droit sont plus grandes.

La recherche dans un ABR suit un seul chemin vers le bas, donc elle coûte O(hauteur). Un arbre équilibré (AVL, rouge-noir) maintient la hauteur proche de log₂ n. Des clés insérées dans l’ordre croissant forment une chaîne de hauteur n.

Un tas est un arbre binaire dans lequel chaque parent est plus petit que ses enfants (tas min) ou plus grand (tas max). Le minimum ou le maximum se trouve à la racine, et l’insertion et la suppression coûtent O(log n).

Une table de hachage stocke des paires clé–valeur. Une fonction de hachage transforme la clé en indice, donc l’insertion et la recherche sont en O(1) en moyenne. Deux clés ayant le même indice forment une collision, résolue par chaînage (une liste par case) ou par adressage ouvert (essayer une autre case).

Un graphe possède des sommets reliés par des arêtes, qui peuvent avoir une direction ou un poids. Il est stocké sous forme de matrice d’adjacence, avec une mémoire en O(V²), ou de listes d’adjacence, en O(V + E).

4La méthode pas à pas

Les questions décrivent souvent une tâche et demandent quelle structure convient, ou demandent à quoi ressemble une structure après quelques opérations.

1. Repérez l’opération qui doit être rapide : accès par position, par clé, l’élément le plus récent, le plus ancien, le plus petit, ou une plage.
2. Associez-la à une structure : indice → tableau, clé → table de hachage, le plus récent → pile, le plus ancien → file, le plus petit ou le plus grand → tas, ordre trié ou plages → arbre de recherche équilibré.
3. Vérifiez le coût, en notation grand O, des autres opérations dont la tâche a besoin.
4. Pour une question de simulation, effectuez les opérations une par une et notez l’état après chacune.
5. Comparez l’état final avec la règle de la structure : LIFO, FIFO, l’ordre de l’ABR ou l’ordre du tas.

5Un exemple détaillé

Suivez chaque étape. Essayez de deviner la suivante avant de l’ouvrir.

6Erreurs fréquentes

• Confondre LIFO et FIFO. Une pile renvoie l’élément le plus récent, une file le plus ancien.
• Croire qu’une liste chaînée donne un accès rapide par indice. Elle doit parcourir depuis la tête.
• Supposer qu’un ABR est toujours en O(log n). Seul un arbre équilibré l’est ; des insertions triées donnent O(n).
• Oublier les collisions dans une table de hachage. O(1) est la moyenne, pas le pire cas.
• Confondre les parcours. Préfixe : le nœud d’abord. Infixe : le nœud au milieu. Postfixe : le nœud en dernier.
• Utiliser une matrice d’adjacence pour un grand graphe peu dense. Elle gaspille une mémoire en O(V²).

7À quoi ressemblent les questions d’examen

• Facile : termes clés et faits. LIFO et FIFO, ce qu’est un nœud, une racine ou une feuille, la règle de l’ABR, ce que fait une fonction de hachage.
• Moyen : application des notions. Quelle structure convient à une tâche, résultat de push et pop ou d’insertions dans un ABR, parcours d’arbres, table de hachage avec sondage linéaire, coûts en notation grand O.
• Difficile : cas et analyse. Arbres équilibrés, tas dans des tableaux, B-arbres, tries, union-find, filtres de Bloom et conceptions telles qu’un cache LRU.

Pour un tas stocké dans un tableau à partir de l’indice 0, les enfants de l’indice i se trouvent en 2i + 1 et 2i + 2, et son parent en ⌊(i − 1) / 2⌋.