Structures de données · L2 · Section 7/7
Ressources
Progression
Points d’expérience : —XPSérie de jours consécutifs : —· —Progression du module : — / —compris
#Ressources : Structures de données
Pour aller plus loin après les chapitres, et pour choisir vite et bien au moment de coder.
#La grille de décision en une table
Le résumé à connaître par cœur (coûts moyens; le pire cas de la table de hachage est en O(n)):
| Structure | Accès par clé | Insertion | Ordre / min | Point fort |
|---|---|---|---|---|
| Tableau dynamique | index O(1), clé O(n) | fin O(1) amorti | tri O(n log n) à la demande | localité cache |
| Liste chaînée / deque | O(n) | O(1) à position connue | non | recâblage local |
| Pile / file | extrémités seules | O(1) | LIFO / FIFO | discipline stricte |
| Table de hachage | O(1) moyen | O(1) amorti moyen | non | dictionnaire pur |
| BST équilibré | O(log n) garanti | O(log n) | trié, intervalles, successeur | ordre dynamique |
| Tas binaire | min O(1) | O(log n) | min immédiat | file de priorité |
Trois réflexes de choix:
- Compter les opérations dominantes avant de choisir (voir le chapitre d'introduction du module).
- Un ordre ou des intervalles sont nécessaires: arbre équilibré. Juste clé → valeur: hachage. Juste « le plus petit tout de suite »: tas.
- Vérifier l'invariant de la structure candidate dans votre contexte (clés immuables pour le hachage, comparabilité totale pour les arbres).
#Références
- Introduction to Algorithms (CLRS), chapitres 10 à 13 puis 18: structures élémentaires, tables de hachage, arbres de recherche, B-arbres.
- Algorithms de Sedgewick et Wayne, partie 3: la référence illustrée pour tables de symboles et arbres équilibrés.
- OpenDSA (opendsa-server.cs.vt.edu, libre): visualisations interactives pile/file/hachage/BST/tas, avec exercices autocorrigés.
- VisuAlgo (visualgo.net): animations de toutes les structures de ce module, en français partiellement.
#Visualisations intégrées au site
- Piles et files:
StackAnimationetQueueVisualizer(chapitre Piles et files). - Tables de hachage:
HashTableVisualizer(adressage ouvert) etBloomFilter(chapitre Tables de hachage). - Arbres:
TreeVisualizer(tas, ce module) etBSTVisualizer(insertion/recherche/suppression pas à pas). - Parcours de graphes:
GraphTraversalVisualizer(module Algorithmique 1).
#S'entraîner
Implémentez de zéro, sans regarder les chapitres, puis testez contre les corrections:
- Une pile et une file sur tableau circulaire (attention au wrap-around des indices).
- Une table de hachage par chaînement avec redimensionnement au doublement de α.
- Un tas min avec
construireen O(n), puis tri par tas. - Un BST complet avec la suppression à deux enfants, puis
est_bstpar intervalles.
Exercices type entretien pour aller plus loin: LRU cache (table de hachage + liste doublement chaînée), top-K par tas, itérateur d'un BST en O(h) mémoire, médiane d'un flux (deux tas).
#Pièges à revoir avant un examen
list.pop(0)en boucle: O(n) par retrait, file à remplacer pardeque.- Clé mutable insérée dans une table de hachage: paire perdue.
- Effacement physique en adressage ouvert: chaîne de sondage coupée, il faut un tombstone.
- Valider un BST en ne comparant que parent et enfants: faux positif, il faut les bornes héritées.
- Tamiser vers l'enfant gauche sans comparer au droit: invariant cassé dès l'échange.