00 — Choisir une structure, c'est choisir un profil de coûts

Ce que tu vas apprendre

• Pourquoi cette série prolonge l'article 03 de la série Complexité
• L'idée que chaque structure est un compromis assumé
• Les structures qu'on va construire et leurs usages
• Le plan de la série

Prérequis

• Le coût des structures de données de la série Complexité

Dans la série Complexité, l'article sur le coût des structures de données donnait un tableau : tableau, hashmap, Set, arbre, et leurs complexités pour l'accès, la recherche, l'insertion, la suppression. C'était la photo. Cette série est le film : on construit ces structures, on comprend pourquoi elles ont ces coûts, et on en ajoute de nouvelles qui répondent à des besoins précis que ni le tableau ni la hashmap ne couvrent.

L'idée directrice reste la même. Une structure de données n'est jamais bonne ou mauvaise dans l'absolu. Elle est un compromis : rapide pour certaines opérations, lente pour d'autres, économe ou gourmande en mémoire. Choisir une structure, c'est décider quelles opérations tu veux rendre rapides, en acceptant que d'autres soient lentes. Le métier consiste à connaître assez de structures pour qu'il y en ait toujours une dont le profil colle à ton problème.

Pourquoi aller au-delà du tableau et de la hashmap

Le tableau et la hashmap couvrent l'essentiel du code applicatif. Mais certains besoins leur échappent.

• « Donne-moi toujours l'élément de plus haute priorité » : ni le tableau ni la hashmap ne font ça efficacement. C'est le rôle de la file de priorité (article 02).
• « Trouve tous les mots qui commencent par algo » : la hashmap répond à « ce mot exact existe-t-il ? », pas aux préfixes. C'est le rôle du trie (article 06).
• « Ces deux éléments sont-ils dans le même groupe connecté ? » avec des fusions de groupes : c'est le rôle d'union-find (article 07).
• « Garde mes éléments triés tout en cherchant vite » : c'est le rôle des arbres équilibrés (article 05).

Chacune de ces structures existe parce qu'un problème réel rendait le tableau ou la hashmap maladroits. Les comprendre, c'est élargir la palette de profils de coûts disponibles.

Le vocabulaire commun

Quelques termes qui reviendront dans toute la série :

• Opération amortie : un coût moyen lissé sur de nombreuses opérations, même si une opération isolée peut coûter plus cher (vu pour l'ajout en fin de tableau).
• Nœud : l'unité de base des structures chaînées et arborescentes ; il contient une valeur et des liens vers d'autres nœuds.
• Invariant : une propriété que la structure maintient en permanence (par exemple, « un tas a toujours son maximum à la racine »). C'est l'invariant qui garantit les complexités.
• Hauteur : pour un arbre, le nombre de niveaux. Beaucoup de coûts d'arbres sont en O(hauteur), d'où l'importance de garder les arbres équilibrés.

Le plan de la série

On part des structures linéaires simples, puis on monte vers les arbres et les structures spécialisées.

À la fin, tu connaîtras non seulement les coûts de chaque structure, mais aussi comment elle fonctionne à l'intérieur, ce qui te permettra de choisir en connaissance de cause et de comprendre les structures que les bibliothèques et les bases de données utilisent sous le capot.

L'article suivant commence par les deux structures linéaires les plus simples et les plus utiles : la pile et la file.

Sources

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), Partie III "Data Structures". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Chapitre 1.3 "Bags, Queues, and Stacks". Addison-Wesley.
• Wengrow, J. (2020). A Common-Sense Guide to Data Structures and Algorithms (2nd ed.). Pragmatic Bookshelf.