Module L03 · Partie F · Coder comme un professionnel

Structures de données : les construire pour les comprendre.

Une liste Python, un dictionnaire, un heapq : vous les utilisez depuis le collège. Ce module les réimplémente — liste chaînée, pile, file, arbre binaire de recherche, tas, table de hachage — pour que chaque coût (O(1), O(log n), O(n)) devienne une évidence et non une formule apprise. C’est le cœur du programme MP2I/MPI et de tout entretien d’embauche en informatique.

Durée : 3 séances · Prérequis : L02, récursivité, complexité (séances 11-12). Objectifs : implémenter et analyser 7 structures, choisir la bonne pour un problème donné, connaître les invariants qui les font tenir.

Ce que vous saurez faire à la fin

Écrire une liste chaînée, une pile, une file circulaire, un ABR, un tas binaire, une table de hachage, un arbre préfixe.
Donner la complexité de chaque opération et la justifier.
Choisir la structure adaptée : « je dois retrouver le plus petit en O(log n) » → tas.

Références : Introduction to Algorithms (CLRS, chapitres 10-13), programme MP2I « structures de données », cours CS61B (Berkeley).

Fiche de cours · Définitions

Les structures de données et leurs contrats

Définition (type abstrait de données). Un ensemble de valeurs et d’opérations spécifiées par leurs propriétés, indépendamment de l’implémentation. Pile (LIFO : empiler, dépiler), file (FIFO : enfiler, défiler), file de priorité (insérer, extraire-min), dictionnaire (associer, chercher, supprimer), ensemble.

Définition (tableau, liste chaînée). Tableau : cases contiguës, accès à l’indice i en O(1), insertion au milieu en O(n). Liste chaînée : cellules (valeur, suivant) ; insertion/suppression en O(1) à une position connue, accès à l’indice i en O(i).

Définition (tas binaire). Arbre binaire complet (tous les niveaux pleins sauf le dernier, rempli à gauche) stocké dans un tableau (enfants de i : 2i+1 et 2i+2 ; parent : ⌊(i−1)/2⌋) vérifiant la propriété de tas : chaque nœud est ≤ ses enfants (tas-min). Le minimum est à la racine.

Définition (table de hachage). Tableau de m cases ; une clé k est rangée en h(k) mod m, où h est une fonction de hachage. Deux clés dans la même case forment une collision, gérée par chaînage (liste par case) ou adressage ouvert (sonder la case suivante). Le facteur de charge est α = n/m.

Définition (arbre binaire de recherche). Arbre binaire où, pour tout nœud, les clés du sous-arbre gauche sont < la clé du nœud < celles du sous-arbre droit. Sa hauteur h gouverne le coût des opérations : O(h). Un ABR est équilibré si h = O(log n) (AVL, rouge-noir).

Définition (complexité amortie). Coût moyen d’une opération sur une suite d’opérations, dans le pire cas de la suite : une opération peut coûter O(n) une fois si les autres coûtent O(1) et que la moyenne est O(1).

Fiche de cours · Formules

Tableau des coûts à connaître

Structure	Accès	Recherche	Insertion	Suppression	Remarque
Tableau / list	O(1)	O(n)	O(1) amorti en fin, O(n) ailleurs	O(n)	cache-friendly
Tableau trié	O(1)	O(log n)	O(n)	O(n)	dichotomie
Liste chaînée	O(n)	O(n)	O(1) à une position connue	O(1)	deque = double chaînage par blocs
Tas binaire	min : O(1)	O(n)	O(log n)	extraire-min O(log n)	construction en O(n)
Table de hachage	—	O(1) moyen, O(n) pire	O(1) moyen	O(1) moyen	si α borné
ABR équilibré	—	O(log n)	O(log n)	O(log n)	parcours trié en O(n)

Hauteur d’un arbre binaire à n nœuds : ⌈log₂(n+1)⌉ − 1 ≤ h ≤ n − 1 un arbre de hauteur h a au plus 2^h+1 − 1 nœuds — d’où la borne inférieure

Chaînage : longueur moyenne d’une chaîne = α = n/m ; recherche infructueuse en Θ(1 + α) Python redimensionne quand α ≈ 2/3 pour garder α = O(1)

Fiche de cours · Théorèmes et démonstrations

Démonstrations à savoir refaire

Théorème 1 (insertion dans un tas en O(log n)). Ajouter x en fin de tableau puis le faire « remonter » tant qu’il est < son parent rétablit la propriété de tas en au plus ⌊log₂ n⌋ échanges.

Invariant : le tableau est un tas sauf peut-être entre x et son parent. Initialisation : avant l’ajout, tout est un tas ; après l’ajout en dernière position, seule la relation (parent(x), x) peut être violée. Conservation : si x < parent, échanger ; les enfants de l’ancienne position de x (anciens frères et anciens enfants) étaient ≥ parent ≥ … donc ≥ x ; la seule violation possible est maintenant entre x et son nouveau parent. Terminaison : la profondeur de x décroît de 1 par échange (variant) ; l’arbre étant complet, la profondeur initiale est ⌊log₂ n⌋. À l’arrêt, x ≥ parent ou x est racine : le tableau est un tas.

Théorème 2 (construire un tas coûte O(n), pas O(n log n)). Appliquer « faire descendre » à chaque nœud interne, du dernier vers la racine, construit un tas en O(n) échanges.

Un nœud de hauteur k (distance à la feuille la plus basse) descend d’au plus k niveaux. Dans un arbre complet à n nœuds il y a au plus ⌈n/2^k+1⌉ nœuds de hauteur k. Coût total ≤ Σ_k≥0 k·n/2^k+1 = (n/2)·Σ k/2^k = (n/2)·2 = n. (Rappel : Σ_k≥1 k·x^k = x/(1−x)² ; en x = 1/2 : 2.) Donc O(n).

Théorème 3 (recherche en O(1) moyen dans une table de hachage). Sous l’hypothèse de hachage uniforme (chaque clé tombe dans une case au hasard, indépendamment), une recherche dans une table par chaînage coûte en moyenne Θ(1 + α).

Soit une recherche de la clé k, infructueuse. On parcourt la chaîne de la case h(k), de longueur L. Par linéarité de l’espérance, E[L] = Σ_{clés k'} P(h(k') = h(k)) = n·(1/m) = α. Coût : calcul de h (O(1)) plus parcours : Θ(1 + α). Pour une recherche fructueuse, on ne parcourt que les clés insérées après k dans sa chaîne, en moyenne α/2 : encore Θ(1 + α). Comme Python maintient α ≤ 2/3 par redimensionnement (coût O(n) mais O(1) amorti, même argument que le tableau dynamique), on obtient O(1) moyen.

Théorème 4 (parcours infixe d’un ABR). Le parcours infixe (gauche, nœud, droite) d’un ABR énumère les clés dans l’ordre croissant.

Récurrence structurelle sur l’arbre. Arbre vide : suite vide, triée. Sinon, par hypothèse de récurrence les parcours des sous-arbres gauche G et droit D sont triés ; par définition de l’ABR, toute clé de G est < racine < toute clé de D ; la concaténation (parcours de G, racine, parcours de D) est donc triée.

Fiche de cours · Méthodes

Choisir une structure : la méthode

Méthode — partir des opérations. Lister les opérations dominantes (celles dans les boucles). « Tester l’appartenance » → set. « Compter » → dict/Counter. « Prendre toujours le plus petit » → tas (heapq). « Ajouter des deux côtés » → deque. « Parcourir dans l’ordre et insérer souvent » → ABR équilibré (ou bisect sur liste triée si les insertions sont rares). « Accès par indice » → list.

Méthode — analyser une suite d’opérations (amorti). Méthode du potentiel : choisir Φ(état) ≥ 0, Φ(initial) = 0 ; le coût amorti d’une opération est coût réel + ΔΦ. Si tous les coûts amortis sont O(1), la suite de n opérations coûte O(n). Tableau dynamique : Φ = 2·(taille − capacité/2) ; un ajout sans copie coûte 1 + 2 = 3, un ajout avec copie coûte n + (2 − n) = 2.

Méthode — implémenter un ABR. Nœud = (clé, gauche, droite). Insertion et recherche récursives ; suppression : 0 enfant → retirer ; 1 enfant → remplacer par lui ; 2 enfants → remplacer la clé par le minimum du sous-arbre droit (successeur) puis supprimer ce minimum. Toujours écrire une fonction est_abr(arbre, lo, hi) pour tester l’invariant après chaque opération.

Pièges : list.pop(0) est O(n) (utiliser deque.popleft) ; heapq est un tas-min (pour un max, empiler −x) ; un ABR construit à partir de données triées dégénère en liste (h = n) ; hacher des objets mutables.

Fiche de cours · Exercices corrigés

Exercices corrigés

Exercice 1. Donner un algorithme en O(n log k) qui renvoie les k plus grands éléments d’un flux de n nombres (on ne peut pas tout stocker si n est énorme). Prouver la complexité.

Correction. Maintenir un tas-min de taille ≤ k. Pour chaque x du flux : si le tas a moins de k éléments, insérer x ; sinon si x > min du tas, remplacer le min par x (heapq.heapreplace). Invariant : le tas contient les k plus grands éléments vus jusqu’ici. Chaque étape coûte O(log k) (taille du tas ≤ k), n étapes : O(n log k), mémoire O(k). À la fin, trier le tas : O(k log k).

Exercice 2. Montrer que dans un tas-min stocké en tableau, le plus grand élément est nécessairement une feuille, c’est-à-dire d’indice ≥ ⌊n/2⌋.

Correction. Un nœud interne i a un enfant 2i+1 < n avec T[2i+1] ≥ T[i] par la propriété de tas ; si T[i] était le maximum strict, T[2i+1] > T[i] contredit la maximalité (et s’il y a égalité, un enfant est aussi maximum). Donc un maximum se trouve parmi les nœuds sans enfant, ceux dont 2i+1 ≥ n, soit i ≥ ⌊n/2⌋. Trouver le max coûte donc O(n) (parcours des feuilles) — un tas-min n’aide pas à trouver le max.

Exercice 3. On insère dans un ABR initialement vide les clés 5, 3, 8, 1, 4, 7, 9 puis 1, 2, 3, 4, 5, 6, 7. Dessiner (ou décrire) les deux arbres, donner leurs hauteurs, et le coût d’une recherche dans chacun.

Correction. Premier arbre : 5 à la racine, 3 et 8 comme enfants, puis 1, 4 sous 3 et 7, 9 sous 8 : arbre parfait de hauteur 2, recherche en ≤ 3 comparaisons = O(log n). Second : chaque clé est plus grande que toutes les précédentes, donc va toujours à droite : chaîne 1→2→…→7 de hauteur 6, recherche en O(n). Moralité : l’ordre d’insertion décide de la hauteur ; d’où les arbres auto-équilibrés (AVL : après chaque insertion, rotation si les hauteurs des sous-arbres diffèrent de plus de 1, ce qui garantit h ≤ 1,44·log₂ n).

01 / Séquences

Liste chaînée : des maillons qui se pointent

class Maillon:
    __slots__ = ("valeur", "suivant")
    def __init__(self, valeur, suivant=None):
        self.valeur, self.suivant = valeur, suivant

class ListeChainee:
    def __init__(self): self.tete = None; self.taille = 0
    def inserer_tete(self, v):               # O(1)
        self.tete = Maillon(v, self.tete); self.taille += 1
    def inserer_fin(self, v):                # O(n) : il faut aller au bout
        m = Maillon(v)
        if self.tete is None: self.tete = m
        else:
            c = self.tete
            while c.suivant: c = c.suivant
            c.suivant = m
        self.taille += 1
    def supprimer(self, v):                  # O(n) : trouver, puis recoudre en O(1)
        prec, c = None, self.tete
        while c and c.valeur != v: prec, c = c, c.suivant
        if c is None: return False
        if prec is None: self.tete = c.suivant
        else: prec.suivant = c.suivant
        self.taille -= 1; return True
    def __iter__(self):
        c = self.tete
        while c: yield c.valeur; c = c.suivant
    def __len__(self): return self.taille
    def __repr__(self): return " → ".join(map(str, self)) + " → ∅"
    def inverser(self):                      # O(n), sans mémoire supplémentaire
        prec, c = None, self.tete
        while c: c.suivant, prec, c = prec, c, c.suivant
        self.tete = prec

L = ListeChainee()
for v in (3, 2, 1): L.inserer_tete(v)
L.inserer_fin(4); print(L, len(L))
L.supprimer(2); print(L)
L.inverser(); print(L)

Liste chaînée vs tableau (la list de Python)

Opération	Tableau	Liste chaînée
Accès au i-ème	O(1)	O(n)
Insertion en tête	O(n) (tout décaler)	O(1)
Insertion en fin	O(1) amorti	O(n), ou O(1) avec un pointeur de queue
Suppression au milieu (position connue)	O(n)	O(1)
Mémoire	compacte, cache-friendly	un pointeur par élément, dispersée

La list Python est un tableau dynamique : quand il est plein, on alloue un tableau ~1,125 fois plus grand et on recopie. Le coût de la recopie, réparti sur toutes les insertions, donne O(1) amorti. En pratique, sur les machines modernes, le tableau gagne presque toujours grâce au cache du processeur ; la liste chaînée reste la brique de base des files, des tables de hachage par chaînage et de l’allocation mémoire en C.

01 / Séquences

Pile et file : deux disciplines d’accès

class Pile:                                   # LIFO : dernier entré, premier sorti
    def __init__(self): self._t = []
    def empiler(self, x): self._t.append(x)  # O(1)
    def depiler(self):                        # O(1)
        if not self._t: raise IndexError("pile vide")
        return self._t.pop()
    def sommet(self): return self._t[-1]
    def __len__(self): return len(self._t)

class FileCirculaire:                         # FIFO avec un tableau fixe : O(1) partout
    def __init__(self, capacite):
        self._t = [None] * capacite; self._debut = 0; self._n = 0
    def enfiler(self, x):
        if self._n == len(self._t): raise OverflowError("file pleine")
        self._t[(self._debut + self._n) % len(self._t)] = x; self._n += 1
    def defiler(self):
        if self._n == 0: raise IndexError("file vide")
        x = self._t[self._debut]
        self._debut = (self._debut + 1) % len(self._t); self._n -= 1
        return x
    def __len__(self): return self._n

# Pile : vérifier le parenthésage d'une expression
def bien_parenthese(s):
    p, paires = Pile(), {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in "([{": p.empiler(c)
        elif c in ")]}":
            if len(p) == 0 or p.depiler() != paires[c]: return False
    return len(p) == 0
print(bien_parenthese("f(a[1], {b: (c)})"), bien_parenthese("(]"), bien_parenthese("(("))

# File circulaire : tampon d'un port série (module L18)
f = FileCirculaire(4)
for octet in b"ABCD": f.enfiler(octet)
print(chr(f.defiler()), chr(f.defiler())); f.enfiler(ord("E")); f.enfiler(ord("F"))
print([chr(f.defiler()) for _ in range(len(f))])

Piège classique : liste.pop(0) pour défiler coûte O(n) (tout décaler). Utilisez collections.deque (O(1) aux deux bouts) ou une file circulaire. Sur un microcontrôleur, la file circulaire de taille fixe est LA structure des tampons de réception : pas d’allocation, temps constant garanti.

02 / Arbres

Arbre binaire de recherche : l’invariant qui rend la recherche logarithmique

class Noeud:
    __slots__ = ("cle", "gauche", "droit")
    def __init__(self, cle): self.cle, self.gauche, self.droit = cle, None, None

class ABR:
    """Invariant : pour tout nœud, gauche < clé < droit."""
    def __init__(self): self.racine = None
    def inserer(self, cle):
        def ins(n):
            if n is None: return Noeud(cle)
            if cle < n.cle: n.gauche = ins(n.gauche)
            elif cle > n.cle: n.droit = ins(n.droit)
            return n
        self.racine = ins(self.racine)
    def contient(self, cle):
        n = self.racine
        while n:
            if cle == n.cle: return True
            n = n.gauche if cle < n.cle else n.droit
        return False
    def parcours_infixe(self):                 # renvoie les clés TRIÉES
        def rec(n):
            if n: yield from rec(n.gauche); yield n.cle; yield from rec(n.droit)
        return list(rec(self.racine))
    def hauteur(self):
        def h(n): return 0 if n is None else 1 + max(h(n.gauche), h(n.droit))
        return h(self.racine)
    def minimum(self):
        n = self.racine
        while n.gauche: n = n.gauche
        return n.cle

import random
random.seed(4)
a = ABR()
for v in random.sample(range(100), 15): a.inserer(v)
print(a.parcours_infixe())
print("contient 42 ?", a.contient(42), "| min :", a.minimum(), "| hauteur :", a.hauteur())

# Le pire cas : insérer dans l'ordre → une liste chaînée déguisée
b = ABR()
for v in range(15): b.inserer(v)
print("hauteur si inséré trié :", b.hauteur(), "(log2(15) ≈ 3.9 idéalement)")

Pourquoi les arbres équilibrés existent

Recherche, insertion, suppression coûtent O(hauteur). Sur des clés aléatoires, la hauteur est ≈ 2·ln n (≈ 1,39 log₂ n) : excellent. Sur des clés triées, la hauteur est n : catastrophe. Les arbres AVL et rouge-noir ajoutent des rotations à l’insertion pour garantir hauteur ≤ 2 log₂ n dans tous les cas ; c’est ce qu’utilisent std::map en C++ et Map en OCaml. Le programme MPI demande de connaître l’idée des rotations ; l’implémentation complète est un excellent défi ★★★. Python n’a pas d’arbre équilibré en bibliothèque standard : il a le dictionnaire (hachage), plus rapide quand on n’a pas besoin de l’ordre.

02 / Arbres

Suppression dans un ABR et parcours en largeur

from collections import deque

def supprimer(n, cle):
    """Renvoie la nouvelle racine du sous-arbre n privé de cle."""
    if n is None: return None
    if cle < n.cle: n.gauche = supprimer(n.gauche, cle)
    elif cle > n.cle: n.droit = supprimer(n.droit, cle)
    else:
        if n.gauche is None: return n.droit          # 0 ou 1 enfant
        if n.droit is None: return n.gauche
        s = n.droit                                  # 2 enfants : successeur = min du sous-arbre droit
        while s.gauche: s = s.gauche
        n.cle = s.cle
        n.droit = supprimer(n.droit, s.cle)
    return n

def largeur(racine):
    """Parcours niveau par niveau (BFS) avec une file."""
    niveaux, file = [], deque([(racine, 0)])
    while file:
        n, d = file.popleft()
        if n is None: continue
        if d == len(niveaux): niveaux.append([])
        niveaux[d].append(n.cle)
        file.append((n.gauche, d + 1)); file.append((n.droit, d + 1))
    return niveaux

t = ABR()
for v in (50, 30, 70, 20, 40, 60, 80, 35, 45): t.inserer(v)
print(largeur(t.racine))
t.racine = supprimer(t.racine, 30)      # nœud à deux enfants
print(largeur(t.racine), t.parcours_infixe())

Trois parcours en profondeur (préfixe, infixe, postfixe) et un en largeur : le préfixe sert à copier un arbre, l’infixe à trier, le postfixe à évaluer une expression ou libérer la mémoire, la largeur à trouver le plus court chemin (module L05).

02 / Arbres

Tas binaire : le minimum en O(1), l’insertion en O(log n)

class TasMin:
    """Tableau où le parent de i est (i-1)//2 ; invariant : parent <= enfants."""
    def __init__(self): self.t = []
    def __len__(self): return len(self.t)
    def inserer(self, x):
        self.t.append(x); i = len(self.t) - 1
        while i > 0 and self.t[(i - 1) // 2] > self.t[i]:       # remonter
            self.t[i], self.t[(i - 1) // 2] = self.t[(i - 1) // 2], self.t[i]
            i = (i - 1) // 2
    def minimum(self): return self.t[0]
    def extraire_min(self):
        m, dernier = self.t[0], self.t.pop()
        if self.t:
            self.t[0] = dernier; i, n = 0, len(self.t)
            while True:                                            # redescendre
                g, d, p = 2 * i + 1, 2 * i + 2, i
                if g < n and self.t[g] < self.t[p]: p = g
                if d < n and self.t[d] < self.t[p]: p = d
                if p == i: break
                self.t[i], self.t[p] = self.t[p], self.t[i]; i = p
        return m

import random, heapq
random.seed(7)
donnees = [random.randint(0, 999) for _ in range(20)]
h = TasMin()
for x in donnees: h.inserer(x)
tri = [h.extraire_min() for _ in range(len(donnees))]
print(tri == sorted(donnees), tri[:6])

# Le module standard fait pareil, en C : heapq
hh = []
for x in donnees: heapq.heappush(hh, x)
print([heapq.heappop(hh) for _ in range(5)])

# File de priorité : (priorité, tâche)
taches = [(3, "lire capteur"), (1, "freinage d'urgence"), (2, "envoyer télémétrie")]
heapq.heapify(taches)
while taches: print(heapq.heappop(taches))

Le tas partout

Le tri par tas (heapsort) ci-dessus est en O(n log n) sans mémoire supplémentaire. Le tas est aussi la file de priorité de Dijkstra et A* (module L05), de l’ordonnanceur d’un système d’exploitation (la tâche la plus prioritaire d’abord), des simulateurs à événements discrets (l’événement le plus proche dans le temps d’abord) et de la compression de Huffman. Le tas binaire est un tableau : pas de pointeurs, excellent pour le cache. Sa faiblesse : chercher un élément quelconque coûte O(n).

03 / Hachage

Table de hachage : le dictionnaire, de l’intérieur

class TableHachage:
    """Chaînage : chaque case contient une liste de (clé, valeur)."""
    def __init__(self, capacite=8):
        self.cases = [[] for _ in range(capacite)]; self.n = 0
    def _indice(self, cle): return hash(cle) % len(self.cases)
    def __setitem__(self, cle, valeur):
        case = self.cases[self._indice(cle)]
        for i, (k, v) in enumerate(case):
            if k == cle: case[i] = (cle, valeur); return
        case.append((cle, valeur)); self.n += 1
        if self.n > 0.75 * len(self.cases): self._agrandir()     # facteur de charge
    def __getitem__(self, cle):
        for k, v in self.cases[self._indice(cle)]:
            if k == cle: return v
        raise KeyError(cle)
    def __contains__(self, cle):
        try: self[cle]; return True
        except KeyError: return False
    def _agrandir(self):
        anciennes = self.cases
        self.cases = [[] for _ in range(2 * len(anciennes))]; self.n = 0
        for case in anciennes:
            for k, v in case: self[k] = v
    def statistiques(self):
        tailles = [len(c) for c in self.cases]
        return f"{len(self.cases)} cases, {self.n} clés, chaîne max {max(tailles)}, vides {tailles.count(0)}"

t = TableHachage()
for i in range(50): t[f"capteur{i}"] = i * 1.5
print(t["capteur7"], "capteur99" in t, t.statistiques())

# Un hachage terrible : tout dans la même case → O(n)
class MauvaiseTable(TableHachage):
    def _indice(self, cle): return 0
m = MauvaiseTable()
for i in range(50): m[f"capteur{i}"] = i
print(m.statistiques())
print(hash("robot") % 8, hash("tobor") % 8, hash(42), hash(3.0) == hash(3))

Ce qu’il faut savoir

Une fonction de hachage transforme une clé en entier ; l’indice est cet entier modulo la capacité. Si elle disperse bien, chaque case contient ~1 élément : accès O(1) en moyenne.
Collisions : inévitables (pigeonnier). Deux stratégies : chaînage (ci-dessus) ou adressage ouvert (chercher la case suivante libre — c’est ce que fait CPython).
Facteur de charge n/capacité : au-delà de ~0,7, on double la taille et on réinsère tout (O(n), mais rare : O(1) amorti).
Une clé doit être immuable : si elle changeait après insertion, son hachage changerait et on ne la retrouverait plus. D’où : les listes ne sont pas hashables, les tuples le sont.
Pire cas O(n) si un attaquant choisit des clés qui collisionnent toutes : Python randomise le hachage des chaînes à chaque lancement pour cette raison (hash flooding).

03 / Hachage

Arbre préfixe (trie) : chercher des mots par leur début

Le coût d’une recherche est O(longueur du mot), indépendant du nombre de mots stockés : c’est la structure de l’autocomplétion, des tables de routage IP (préfixes binaires) et des dictionnaires de correcteurs orthographiques.

04 / Choisir

Quelle structure pour quel besoin ?

Besoin	Structure	Coût clé
Accès par indice, parcours	Tableau (`list`)	O(1) accès, O(1) amorti append
Ajouter/retirer aux deux bouts	`deque` / file circulaire	O(1)
Dernier entré premier sorti (annuler, appels, parcours DFS)	Pile	O(1)
Premier entré premier sorti (tampon, BFS)	File	O(1)
Retrouver par clé, sans ordre	Table de hachage (`dict`, `set`)	O(1) moyen
Retrouver par clé, en gardant l’ordre (min, max, intervalle)	ABR équilibré	O(log n)
Toujours le plus petit / prioritaire	Tas (`heapq`)	O(1) lire, O(log n) insérer/retirer
Mots par préfixe	Trie	O(longueur)
Ensembles disjoints, « sont-ils connectés ? »	Union-Find (module L05)	≈ O(1) amorti

La question n’est jamais « quelle est la meilleure structure » mais « quelles opérations vais-je faire souvent ». Écrivez la liste des opérations, leur fréquence, puis choisissez.

04 / Choisir

Mesurer pour le croire

import time, random, bisect, heapq
from collections import deque

def chrono(f):
    t0 = time.perf_counter(); f(); return f"{1000 * (time.perf_counter() - t0):7.1f} ms"

N = 100_000
donnees = list(range(N)); random.shuffle(donnees)

print("recherche de 2000 clés")
L = list(donnees); S = set(donnees); T = sorted(donnees)
cibles = random.sample(range(N), 2000)
print("  liste (O(n))      ", chrono(lambda: [x in L for x in cibles[:200]]), "(200 seulement !)")
print("  set (O(1))        ", chrono(lambda: [x in S for x in cibles]))
print("  bisect (O(log n)) ", chrono(lambda: [T[bisect.bisect_left(T, x)] == x for x in cibles]))

print("défiler 50 000 éléments")
l = list(range(50_000)); d = deque(range(50_000))
print("  list.pop(0)       ", chrono(lambda: [l.pop(0) for _ in range(len(l))]))
print("  deque.popleft()   ", chrono(lambda: [d.popleft() for _ in range(len(d))]))

print("extraire 20 000 fois le minimum")
a = list(donnees[:20_000]); h = list(a); heapq.heapify(h)
print("  min + remove (O(n))", chrono(lambda: [a.remove(min(a)) for _ in range(300)]), "(300 seulement !)")
print("  heapq (O(log n))   ", chrono(lambda: [heapq.heappop(h) for _ in range(20_000)]))

Cours

Cours 1 — Types abstraits et implémentations : séparer le « quoi » du « comment »

Définition. Un type abstrait de données (TAD) est un ensemble de valeurs et d’opérations spécifiées par leur comportement, indépendamment de toute implémentation. La pile est un TAD : empiler, depiler, est_vide, avec l’axiome « depiler(empiler(p, x)) rend x et p ». Un tableau ou une liste chaînée en sont deux implémentations ; le code client ne doit dépendre que du TAD.

TAD	Opérations	Implémentations usuelles	Complexités
Séquence	accès i, insérer, supprimer, parcourir	tableau dynamique ; liste chaînée	O(1)/O(n) selon l’opération (cours L03 §01)
Pile / File / Deque	push/pop ; enqueue/dequeue ; les deux bouts	tableau ; tableau circulaire ; liste chaînée	O(1) toutes
Dictionnaire (map)	insérer, chercher, supprimer par clé	table de hachage ; ABR équilibré ; trie	O(1) moyen ; O(log n) ; O(\|clé\|)
Ensemble	appartenance, union, intersection	hachage ; bitset ; arbre	O(1) ; O(n/64) ; O(log n)
File de priorité	insérer, extraire-min, diminuer-clé	tas binaire ; tas de Fibonacci	O(log n) ; O(1) amorti pour diminuer-clé
Ensembles disjoints	trouver, unir	forêt avec compression	O(α(n)) amorti

Pourquoi cette séparation compte. Elle permet de changer l’implémentation quand les mesures l’exigent, sans toucher au reste ; elle rend la complexité explicite dans l’interface (« contient est O(1) ») ; et c’est ainsi que sont écrites les bibliothèques standard de tous les langages (std::map, Map.Make en OCaml, dict).

Cours

Cours 2 — Analyse amortie : les trois méthodes

Une opération peut coûter cher parfois tout en étant bon marché en moyenne sur une suite d’opérations. Trois façons de le prouver :

Agrégat : borner le coût total de n opérations, diviser par n. Tableau dynamique : n insertions coûtent au plus n + (1 + 2 + 4 + … + n) < 3n copies ⇒ O(1) amorti.
Comptable (banquier) : chaque opération paie un coût fixe ; l’excédent est déposé sur des « jetons » attachés aux éléments et dépensé lors des opérations chères. Tableau dynamique : chaque insertion paie 3 (1 pour s’écrire, 2 jetons) ; au doublement, chaque élément de la moitié récente a 2 jetons pour se recopier lui et un ancien.
Potentiel : une fonction Φ(état) ≥ 0 ; coût amorti = coût réel + ΔΦ. Pour la file à deux piles : Φ = taille de la pile d’entrée ; enfiler coûte 1 + 1 ; défiler qui renverse k éléments coûte k + 1 − k = 1.

L’analyse amortie ne dit rien sur le pire cas d’une opération isolée : un tableau dynamique peut bloquer 10 ms sur une recopie. Pour un système temps réel (L18), on préfère les structures à pire cas borné (file circulaire de taille fixe).

Cours

Cours 3 — Bien choisir : un arbre de décision, et les structures qu’on n’a pas vues

Les clés ont un ordre à exploiter (min, max, plus proche, intervalle, parcours trié) → arbre équilibré (AVL, rouge-noir, B-arbre) ou skip list. Sinon → hachage.
Les clés sont des entiers petits → tableau direct ou bitset (un bit par valeur : 10⁸ entiers dans 12 Mo, opérations ensemblistes par ET/OU 64 bits à la fois).
Les clés sont des chaînes avec préfixes → trie ; besoin de sous-chaînes → arbre/tableau des suffixes.
Requêtes sur des intervalles (somme, min, max sur t[i..j] avec mises à jour) → arbre de Fenwick (O(log n), 20 lignes) ou arbre de segments.
Points dans le plan / l’espace (voisins, boîtes) → k-d tree, quadtree, grille de hachage spatial (robotique, L20).
Appartenance approximative avec très peu de mémoire (« ai-je déjà vu cette URL ? ») → filtre de Bloom (jamais de faux négatif, quelques faux positifs).
Données immuables partagées (historique, annuler/rétablir, OCaml) → structures persistantes (arbres partageant leurs sous-arbres).

TP guidé

TP — Une bibliothèque de structures, testée et mesurée (sur PC, 2 h)

Squelette. Projet tp-structures (venv, pytest, hypothesis). Un module par structure : pile.py, file.py, abr.py, tas.py, hachage.py. Chaque classe expose __len__, __contains__ quand c’est pertinent, et __iter__.

Tests par propriétés avec un modèle de référence. Pour chaque structure, un test Hypothesis qui applique une suite aléatoire d’opérations à la fois à votre structure et à une référence Python (list, collections.deque, sorted, heapq, dict) et compare les résultats à chaque étape :

from hypothesis import given, strategies as st
ops = st.lists(st.tuples(st.sampled_from(["push", "pop"]), st.integers()))
@given(ops)
def test_pile_comme_list(seq):
    p, ref = Pile(), []
    for op, x in seq:
        if op == "push": p.empiler(x); ref.append(x)
        elif ref: assert p.depiler() == ref.pop()
        assert len(p) == len(ref)

Invariants exécutables. Ajoutez à ABR une méthode _verifier() qui parcourt l’arbre et vérifie « gauche < clé < droit » partout, et à TasMin une _verifier() « parent ≤ enfants ». Appelez-les dans les tests après chaque opération (mode débogage).
Mesure. Script bench.py : pour n = 10³, 10⁴, 10⁵, chronométrez n insertions puis n recherches dans ABR, table de hachage, et dict ; tracez (matplotlib) en log-log. Lisez les pentes : ≈ 1 pour le hachage (O(1) par opération, donc O(n) total), légèrement plus pour l’ABR (n log n).
Dégradation. Insérez les clés triées dans l’ABR : mesurez, constatez l’explosion (O(n²) total), et expliquez dans RESULTATS.md. Puis remplacez l’ABR par l’AVL du défi ★★★ et refaites la mesure.
Livrable. Le dépôt avec tests verts, bench.png et RESULTATS.md (tableau des temps, pentes, conclusion en 5 lignes).

Exercices

Exercices auto-corrigés — piles, files, listes

Exercice 1 — Évaluer une expression postfixée

Avec une pile, évaluez une expression en notation polonaise inverse : "3 4 + 2 *" → 14. Opérateurs + - * / (division réelle). Levez ValueError si l’expression est mal formée (pile vide à un opérateur, ou plus d’un élément à la fin).

Correction

def rpn(expr):
    pile, ops = [], {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b, "/": lambda a, b: a / b}
    for tok in expr.split():
        if tok in ops:
            if len(pile) < 2: raise ValueError("opérande manquante")
            b, a = pile.pop(), pile.pop(); pile.append(ops[tok](a, b))
        else: pile.append(float(tok))
    if len(pile) != 1: raise ValueError("expression mal formée")
    return pile[0]

Exercice 2 — Liste chaînée : supprimer les doublons consécutifs et détecter un cycle

Sur la classe Maillon ci-dessous : compacter(tete) supprime les répétitions consécutives en place ; a_un_cycle(tete) renvoie True si la liste boucle (algorithme du lièvre et de la tortue, sans mémoire supplémentaire).

Correction

def compacter(tete):
    m = tete
    while m and m.s:
        if m.s.v == m.v: m.s = m.s.s
        else: m = m.s
    return tete
def a_un_cycle(tete):
    lent = rapide = tete
    while rapide and rapide.s:
        lent, rapide = lent.s, rapide.s.s
        if lent is rapide: return True
    return False

Exercices

Exercices auto-corrigés — arbres, tas, hachage

Exercice 3 — k plus grands éléments d’un flux

Avec heapq, écrivez k_plus_grands(flux, k) qui lit un itérable (potentiellement énorme) en gardant seulement k éléments en mémoire, et renvoie les k plus grands triés décroissants. Indice : un tas-min de taille k.

Correction

def k_plus_grands(flux, k):
    tas = []
    for x in flux:
        if len(tas) < k: heapq.heappush(tas, x)
        elif x > tas[0]: heapq.heapreplace(tas, x)
    return sorted(tas, reverse=True)

Exercice 4 — Deux sommes avec une table de hachage

deux_somme(t, cible) renvoie les indices (i, j), i < j, tels que t[i] + t[j] = cible, en un seul passage O(n) ; None sinon. Puis anagrammes(mots) regroupe les mots anagrammes entre eux (clé : lettres triées).

Correction

def deux_somme(t, cible):
    vus = {}
    for j, x in enumerate(t):
        if cible - x in vus: return (vus[cible - x], j)
        vus.setdefault(x, j)
    return None
def anagrammes(mots):
    groupes = {}
    for m in mots: groupes.setdefault("".join(sorted(m)), []).append(m)
    return list(groupes.values())

05 / Défis

Défi ★ — Une file avec deux piles

Consigne

Implémentez une file FIFO en n’utilisant que deux piles (listes avec append/pop uniquement, jamais pop(0) ni insert). Montrez que chaque élément est déplacé au plus deux fois, donc que defiler est O(1) amorti. Testez contre deque sur 10 000 opérations aléatoires.

Correction

class FileDeuxPiles:
    def __init__(self): self.entree, self.sortie = [], []
    def enfiler(self, x): self.entree.append(x)
    def defiler(self):
        if not self.sortie:
            while self.entree: self.sortie.append(self.entree.pop())   # renverser
        if not self.sortie: raise IndexError("file vide")
        return self.sortie.pop()
    def __len__(self): return len(self.entree) + len(self.sortie)

import random
from collections import deque
f, d = FileDeuxPiles(), deque()
for _ in range(10_000):
    if d and random.random() < 0.5:
        assert f.defiler() == d.popleft()
    else:
        x = random.random(); f.enfiler(x); d.append(x)
print("OK")

Chaque élément passe une fois dans entree (append), une fois dans sortie (pop + append), une fois dehors (pop) : 3 opérations O(1) par élément sur toute sa vie, donc O(1) amorti par opération, même si un defiler isolé peut coûter O(n). C’est exactement le raisonnement de l’analyse amortie (méthode du banquier).

05 / Défis

Défi ★★ — Cache LRU

Consigne

Un cache de capacité k qui garde les k derniers éléments utilisés (lecture ou écriture) et éjecte le moins récemment utilisé. get(cle) et put(cle, valeur) doivent être O(1). Indice : un dictionnaire pour retrouver, une liste doublement chaînée pour l’ordre d’usage (déplacer un maillon en tête est O(1) si on a le pointeur). Vérifiez contre une implémentation naïve O(n) sur des opérations aléatoires.

Correction

class _M:
    __slots__ = ("cle", "val", "prec", "suiv")
    def __init__(self, cle=None, val=None): self.cle, self.val, self.prec, self.suiv = cle, val, None, None

class LRU:
    def __init__(self, capacite):
        self.capacite, self.table = capacite, {}
        self.tete, self.queue = _M(), _M()          # sentinelles : jamais de cas particulier
        self.tete.suiv, self.queue.prec = self.queue, self.tete
    def _detacher(self, m): m.prec.suiv, m.suiv.prec = m.suiv, m.prec
    def _en_tete(self, m):
        m.prec, m.suiv = self.tete, self.tete.suiv
        self.tete.suiv.prec = m; self.tete.suiv = m
    def get(self, cle):
        m = self.table.get(cle)
        if m is None: return None
        self._detacher(m); self._en_tete(m); return m.val
    def put(self, cle, val):
        m = self.table.get(cle)
        if m: m.val = val; self._detacher(m); self._en_tete(m); return
        if len(self.table) == self.capacite:
            vieux = self.queue.prec; self._detacher(vieux); del self.table[vieux.cle]
        m = _M(cle, val); self.table[cle] = m; self._en_tete(m)

Les sentinelles (tête et queue fictives) suppriment tous les « si la liste est vide / si c’est le premier ». Python fournit functools.lru_cache (décorateur) et OrderedDict.move_to_end qui font exactement cela. Le LRU est la politique des caches de processeur, des navigateurs et des bases de données.

05 / Défis

Défi ★★★ — Esprit prépa : arbre AVL

Consigne

Ajoutez à l’ABR une hauteur stockée dans chaque nœud et les rotations gauche/droite pour maintenir |h(gauche) − h(droit)| ≤ 1 après chaque insertion (4 cas : GG, DD, GD, DG). Insérez 1, 2, …, 10 000 dans l’ordre et vérifiez que la hauteur reste ≤ 1,44 log₂(n + 2). Vérifiez l’invariant ABR et l’équilibre après chaque insertion sur 1000 clés aléatoires.

Correction

def rot_droite(y):
    x = y.g; y.g = x.d; x.d = y; maj(y); maj(x); return x
def rot_gauche(x):
    y = x.d; x.d = y.g; y.g = x; maj(x); maj(y); return y

def inserer(n, cle):
    if n is None: return N(cle)
    if cle < n.cle: n.g = inserer(n.g, cle)
    elif cle > n.cle: n.d = inserer(n.d, cle)
    else: return n
    maj(n); e = equilibre(n)
    if e > 1 and cle < n.g.cle: return rot_droite(n)                    # GG
    if e < -1 and cle > n.d.cle: return rot_gauche(n)                    # DD
    if e > 1: n.g = rot_gauche(n.g); return rot_droite(n)                # GD
    if e < -1: n.d = rot_droite(n.d); return rot_gauche(n)               # DG
    return n

import math, random
r = None
for k in range(1, 10_001): r = inserer(r, k)
print("hauteur :", r.h, "≤", round(1.44 * math.log2(10_002), 1))

def verifier(n, lo=-math.inf, hi=math.inf):
    if n is None: return True
    return lo < n.cle < hi and abs(equilibre(n)) <= 1 and n.h == 1 + max(h(n.g), h(n.d)) \
        and verifier(n.g, lo, n.cle) and verifier(n.d, n.cle, hi)
r = None
for k in random.sample(range(100_000), 1000):
    r = inserer(r, k); assert verifier(r)
print("invariants OK")

Une rotation est O(1) et préserve l’ordre infixe ; au plus 2 rotations par insertion suffisent. La preuve que la hauteur reste en O(log n) passe par la suite de Fibonacci (un AVL de hauteur h a au moins F(h+2) − 1 nœuds) : c’est un exercice d’oral classique. Les arbres rouge-noir relâchent l’équilibre pour faire moins de rotations ; les B-arbres généralisent à plusieurs clés par nœud pour les disques et les bases de données.

06 / Vérification

Un ordonnanceur doit sans cesse exécuter la tâche la plus urgente parmi des milliers. Structure ?

Deux questions supplémentaires

1. Pourquoi une liste ne peut-elle pas être clé de dictionnaire ? Elle est mutable : son hachage changerait après modification et la clé deviendrait introuvable.

2. Que signifie « O(1) amorti » ? Une suite de n opérations coûte O(n) au total, même si certaines opérations isolées coûtent O(n) (le redimensionnement d’un tableau, le renversement des deux piles).

Référence

Les mots à retenir

Mot	Définition
Invariant	Propriété vraie avant et après chaque opération (ABR : gauche < clé < droit ; tas : parent ≤ enfants).
Amorti	Coût moyen par opération sur une longue suite.
Liste chaînée	Maillons reliés par pointeurs ; insertion O(1) en tête.
File circulaire	File dans un tableau fixe avec indices modulo.
ABR	Arbre binaire de recherche ; O(hauteur).
AVL / rouge-noir	ABR auto-équilibrés par rotations ; O(log n) garanti.
Tas	Arbre binaire complet dans un tableau ; minimum à la racine.
Hachage	Clé → entier → indice ; O(1) moyen ; collisions gérées par chaînage ou adressage ouvert.
Facteur de charge	Nombre de clés / nombre de cases.
Trie	Arbre des préfixes ; recherche en O(longueur du mot).
Sentinelle	Nœud fictif qui élimine les cas particuliers.

Pour continuer

Vous savez ce que coûte chaque opération

Module suivant : les stratégies algorithmiques — diviser pour régner, programmation dynamique, gloutons, backtracking — et comment prouver qu’elles sont correctes.

À faire chez soi

Réécrire de mémoire le tas et la table de hachage, avec tests par propriétés.
Implémenter collections.Counter et OrderedDict vous-même.
Lire CLRS chapitre 11 (hachage) ou regarder la conférence « The Mighty Dictionary » (Brandon Rhodes).

← L02 Sommaire L04 : Stratégies algorithmiques →