Suppression dans les arbres, tas binaires, files de priorité et mémoïsation.
« If you can solve it, it's an exercise, otherwise it's a research problem » (Richard Bellman, inventeur de la programmation dynamique). Cette suite approfondit les structures arborescentes et introduit la mémoïsation, porte d'entrée vers la programmation fonctionnelle.
| Arbre | structure de données abstraite composée de nœuds atteignables par un seul chemin. |
| Arbre binaire | arbre enraciné dont les nœuds n'admettent au plus que deux branches. |
| Racine | l'unique point d'entrée d'un arbre. |
| Nœud / branche / feuille | un nœud est une valeur reliée à d'autres ; une branche est la relation entre nœuds ; une feuille est un nœud sans descendance. |
| Hiérarchique | structuré en échelons, formant un chemin unique pour atteindre un nœud. |
| Arbre binaire de recherche | arbre binaire avec relation d'ordre fils gauche < parent < fils droit. |
| Tas binaire (heap) | arbre binaire hiérarchique avec une relation d'ordre parent > fils, sans ordre entre les fils. |
| File de priorité | une collection qui rend la valeur la plus prioritaire. |
| Topologie | classification établie déductivement (à partir de propriétés). |
| Taxonomie | classification établie empiriquement (à partir de cas observés). |
| Transparence référentielle | aptitude d'une expression à être remplacée par sa valeur sans changer le comportement du logiciel. (Quine, 1960.) |
| Fonction pure | fonction déterministe sans effet de bord. La pureté implique la transparence référentielle. |
| Cache | un dictionnaire utilisé pour mémoïser. En retirer les données périmées (stale data) = invalider le cache. |
Pour traiter la suppression rigoureusement, on construit une topologie des cas (déductive), et non une simple taxonomie (empirique). On croise deux paramètres : la valeur à supprimer et la forme de l'arbre.
Cas sur la valeur : dégénérée · absente · présente — et si présente : à la racine, à une feuille, ou au milieu.
Cas sur la forme de l'arbre, du plus simple au plus général : arbre vide → racine seule → racine + une feuille (supérieure / inférieure) → racine + deux feuilles → racine + sous-arbre supérieur de hauteur 1 (avec / sans feuille inférieure) → idem côté inférieur → puis sous-arbre de hauteur arbitraire. On filtre ensuite les cas qui se ramènent concrètement à un seul.
Le tas garde donc le plus prioritaire à la racine, accessible immédiatement. Insertion et retrait se font en O(log n) — c'est optimal pour récupérer les « K plus grands ». Revers : la structure est peu compatible avec le cache (cache-unfriendly) car les nœuds reliés sont éloignés en mémoire.
Une file de priorité rend toujours la valeur la plus prioritaire (et non la première ou la dernière insérée — l'ordre d'insertion est une variable non descriptive). Elle s'implémente naturellement avec un tas binaire.
prendre_suivant(file) → le plus prioritaire (retiré). File vide : bloquant (attendre) ou non bloquant (signaler le vide).ajouter(file, (valeur, priorité)). Collisions de valeurs : traitées comme distinctes. Collisions de priorités : soit un invariant ajouté au contrat (ex. FIFO), soit une imprédictibilité assumée (choix du SDK Java).Cas typique : un service de facturation appelle souvent une API externe pour obtenir le prix d'un médicament. Chaque requête a un coût financier (facturée) et temporel (latence réseau : encodage + réseau + traitement + réseau + décodage). Or le « cap » de l'ingénieur, c'est d'obtenir O(1) sans coût.
L'appel getPrix("ibuprofène") → 2,57 € est une relation (clé, valeur) : on peut donc remplacer l'appel par un dictionnaire, c'est-à-dire remplacer dynamiquement la procédure par sa valeur de retour. C'est la transparence référentielle.
L'équivalence n'est valable que pendant la durée de stabilité de la valeur :
| Type de donnée | Comportement | Stratégie |
|---|---|---|
| Invariante | ne change jamais | mise en cache permanente |
| Stable mais périssable | change à fréquence connue | expiration automatique (TTL) |
| Volatile | fréquence indéterminée | invalidation explicite |
Pour être mémoïsable, l'appel doit être une fonction (avoir une valeur de retour), sans effet de bord et sans dépendre d'un état mutable externe (sinon, il faut capturer cet état comme paramètre). Une telle fonction est pure : aucune invalidation n'est alors nécessaire (ex. calculs scientifiques).
Exemple concret côté web : un serveur HTTP autorise le client à mettre en cache ses réponses via les codes 304 / 200 et l'en-tête ETag (identifiant de la ressource + de sa version).
| Nom | Pourquoi il est cité |
|---|---|
| Richard Bellman | inventeur de la programmation dynamique — dont la mémoïsation est la porte d'entrée. |
| W. V. O. Quine (1960) | formalise la transparence référentielle et la fonction pure — fondements de la programmation fonctionnelle. |
| Bertrand Russell (1910) | les travaux logiques (Principia Mathematica) sur lesquels Quine s'appuie. |
| Niklaus Wirth | « Algorithms + Data Structures = Programs » : on choisit la structure selon le contrat visé. |
À retenir : le tas garde le maximum à la racine (O(log n)) et sert de socle à la file de priorité ; la mémoïsation échange un appel coûteux contre un accès O(1) dans un cache — valable tant que la fonction est pure (ou que l'on gère le cycle de vie de la donnée).
D'après le cours d'algorithmie avancée (A. Roger, ENSICAEN). Fiche de révision personnelle.