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

Une structure de données est le couple d'une organisation en mémoire et des opérations qu'elle rend efficaces. Le programme MP2I distingue le type abstrait (ce que l'on peut faire, spécifié par une signature et des propriétés) de son implémentation (comment c'est fait). Pour chaque structure, il faut connaître l'invariant qui la définit et le coût de ses opérations.

Tableau dynamique

Un tableau de capacité $c$ qui contient $n\le c$ éléments. Quand il est plein, on alloue un tableau de capacité $2c$ et on recopie. L'ajout en fin coûte O(n) au pire mais O(1) amorti : pour atteindre $n$ éléments, les recopies coûtent $1+2+4+\cdots <2n$.

Liste chaînée

Maillons alloués séparément, chacun pointant vers le suivant. Insertion et suppression en tête en O(1), accès au i-ème élément en O(i), recherche en O(n). En OCaml, les listes sont des listes chaînées immuables : x :: l partage l sans la copier.

Pile (LIFO) et file (FIFO)

Usages : la pile sert au parenthésage, à l'évaluation postfixe, au parcours en profondeur et modélise la pile d'appels ; la file sert au parcours en largeur et aux tampons. Avec deux piles, on enfile sur la première et on défile depuis la seconde, que l'on remplit en renversant la première quand elle est vide : chaque élément est déplacé au plus une fois.

Un arbre binaire est vide ou formé d'une racine et de deux sous-arbres (gauche, droit). En OCaml : type 'a arbre = Vide | Noeud of 'a arbre 'a 'a arbre.

• Taille $n$ : nombre de nœuds. Hauteur $h$ : nombre de nœuds de la plus longue branche (arbre vide : 0). Certains ouvrages comptent les arêtes : préciser la convention.
• Encadrement : $h\le n\le 2^h-1$, donc $h\ge {\log }_2(n+1)$. Un arbre équilibré a une hauteur O(log n), un arbre filiforme une hauteur $n$.
• Nombre de feuilles = nombre de nœuds à deux fils + 1 (arbre non vide).

Parcours

Tous visitent chaque nœud une fois : O(n).

Arbre binaire de recherche (ABR)

Invariant : pour tout nœud de clé $k$, toutes les clés du sous-arbre gauche sont inférieures à $k$ et toutes celles du sous-arbre droit supérieures. Le parcours infixe produit les clés triées.

• Recherche et insertion : descendre à gauche ou à droite selon la comparaison, O(h).
• Suppression d'un nœud à deux fils : le remplacer par son successeur (minimum du sous-arbre droit) puis supprimer celui-ci, O(h).
• $h$ vaut O(log n) si l'arbre est équilibré, mais $n$ si les clés arrivent triées. Les arbres AVL ou rouge-noir maintiennent $h=O(\log n)$ (principe à connaître, pas les rotations).

Un tas max est un arbre binaire presque complet (niveaux pleins sauf le dernier, rempli de gauche à droite) où chaque nœud est supérieur ou égal à ses fils. Il se range dans un tableau sans pointeurs : racine en 0, fils de $i$ en $2i+1$ et $2i+2$, père en $\lfloor (i-1)/2\rfloor$.

• Insertion : placer en fin, faire remonter en échangeant avec le père tant que nécessaire : O(log n).
• Extraction du max : remplacer la racine par le dernier élément, le faire descendre vers le plus grand fils : O(log n).
• Accès au max : O(1).

Le tas implémente la file de priorité (Dijkstra, Huffman, ordonnancement). Le tri par tas construit un tas puis extrait $n$ fois le maximum : O(n log n) dans tous les cas, en place.

Un dictionnaire associe des clés uniques à des valeurs : ajouter, chercher, supprimer. Implémentations : liste d'association (O(n)), ABR équilibré (O(log n), clés ordonnées), table de hachage (O(1) en moyenne).

Une fonction de hachage $h$ envoie chaque clé sur un indice d'un tableau de $m$ alvéoles. Les collisions sont traitées par chaînage (liste par alvéole) ou adressage ouvert (sondage d'autres alvéoles). Avec une bonne répartition et un facteur de charge $n/m$ borné (on redimensionne au-delà), les opérations coûtent O(1) en moyenne ; le pire cas reste O(n). Une fonction de hachage doit être déterministe, rapide et cohérente avec l'égalité des clés.

En OCaml : Hashtbl.create, Hashtbl.add, Hashtbl.find (lève Not_found), Hashtbl.find_opt, Hashtbl.replace, Hashtbl.mem. En C, on écrit soi-même le tableau de listes chaînées.

Maintient une partition en classes disjointes avec find x (représentant) et union x y. Représentation par forêt : chaque élément pointe vers un père, la racine est le représentant. Avec union par rang et compression de chemin, le coût amorti est quasi constant. Application phare : Kruskal (arbre couvrant minimal) et la détection de cycles.

## Méthodes de concours

1. 1Énoncer l'invariant de la structure avant d'écrire une opération (ordre du tas, propriété d'ABR, remplissage du tableau circulaire) et vérifier qu'il est conservé.
2. 2Justifier chaque complexité par la hauteur (arbres, tas) ou par un argument amorti (tableau dynamique, deux piles).
3. 3Choisir la structure selon les opérations demandées : extraction du min répétée → tas ; recherche par clé → table de hachage ; parcours trié → ABR ; dernier arrivé → pile.
4. 4Savoir coder en OCaml les fonctions récursives sur les arbres et en C les listes chaînées avec malloc/free.
5. 5Connaître les cas dégénérés : ABR filiforme, table de hachage avec collisions systématiques, pile d'appels trop profonde.