Structures de données : piles, files, arbres et tas

Structures de données : piles, files, arbres et tas

1. Piles (LIFO) et files (FIFO)

Une pile (stack) est une structure « dernier entré, premier sorti » (LIFO) : les deux opérations de base sont empiler (push, ajouter au sommet) et dépiler (pop, retirer le sommet), chacune en $O(1)$.

empiler(P, x) : ajouter x au sommet de P

dépiler(P) : retirer et renvoyer l'élément au sommet de P

Une file (queue) est « premier entré, premier sorti » (FIFO) : enfiler (enqueue, ajouter à l'arrière) et défiler (dequeue, retirer à l'avant), chacune en $O(1)$ avec une implémentation adaptée (liste doublement chaînée ou tableau circulaire).

Applications classiques : une pile sert à l'évaluation d'expressions arithmétiques (notation polonaise inversée), à la gestion des appels de fonctions récursives, au parcours en profondeur (DFS) d'un graphe. Une file sert au parcours en largeur (BFS), à l'ordonnancement de tâches (FIFO).

2. Arbres binaires

Un arbre binaire est une structure récursive : chaque nœud a au plus deux enfants (gauche, droit). La hauteur $h$ d'un arbre à $n$ nœuds vérifie $h\geq\lceil\log_2(n+1)\rceil-1$ (borne atteinte par un arbre parfaitement équilibré) et $h\leq n-1$ (cas dégénéré, arbre filiforme).

Arbre binaire de recherche (ABR) : pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures, toutes celles du sous-arbre droit sont supérieures. Recherche, insertion, suppression sont en $O(h)$ — donc $O(\log n)$ si l'arbre est équilibré, mais $O(n)$ dans le pire cas (arbre filiforme, par exemple après insertions dans un ordre déjà trié).

3. Arbres équilibrés

Les arbres AVL et arbres rouge-noir garantissent $h=O(\log n)$ en maintenant un équilibre lors des insertions/suppressions (rotations locales en $O(1)$ par niveau). Cela garantit que les opérations de base restent en $O(\log n)$ dans le pire cas, contrairement à l'ABR naïf.

4. Tas (heap) et file de priorité

Un tas-min (min-heap) est un arbre binaire (souvent représenté par un simple tableau) vérifiant la propriété de tas : la valeur de chaque nœud est inférieure ou égale à celles de ses enfants. Conséquence : la racine contient toujours le minimum de l'ensemble.

Opérations : insérer un élément : on l'ajoute en fin de tableau puis on le fait « remonter » (percolation vers le haut) tant qu'il est plus petit que son parent — coût $O(\log n)$. Extraire le minimum : on retire la racine, on la remplace par le dernier élément, puis on fait « descendre » cet élément (percolation vers le bas) — coût $O(\log n)$ également.

Représentation par tableau : pour un nœud à l'indice $i$ (indexation à partir de $0$), son enfant gauche est à l'indice $2i+1$, son enfant droit à $2i+2$, son parent à $\lfloor(i-1)/2\rfloor$ — pas besoin de pointeurs explicites.

Application — file de priorité : un tas implémente efficacement une file de priorité (extraire systématiquement l'élément de plus haute/basse priorité), utilisée notamment dans l'algorithme de Dijkstra (leçon suivante) et le tri par tas (heapsort, $O(n\log n)$ dans tous les cas, y compris le pire).

5. Table de hachage

Une table de hachage associe à chaque clé un indice dans un tableau via une fonction de hachage $h$, permettant insertion, recherche et suppression en $O(1)$ en moyenne (sous hypothèse de bonne répartition des clés). En cas de collision (deux clés ayant le même indice), on utilise le chaînage (liste des éléments en collision à chaque case) ou l'adressage ouvert (recherche de la case libre suivante selon une règle déterministe).

Pire cas : $O(n)$ si toutes les clés se retrouvent dans la même case (table de hachage mal conçue ou attaque délibérée), mais ce cas est rare en pratique avec une bonne fonction de hachage.

6. Récapitulatif

|---|---|---|---|