Aller au contenu principal
Valrose.tech

#Slides : Structures de données

Une diapo par structure: l'invariant, les opérations, le coût. À dérouler dans l'ordre du module.

  1. Le choix se décide par les opérations: compter accès, insertions, recherches; aucune structure ne gagne partout.
  2. Tableaux et listes: contiguïté contre chaînage; O(1) indexé mais décalages, O(1) local mais parcours; list, deque, ndarray.
  3. Piles et files: invariants LIFO et FIFO; O(1) aux extrémités; parenthèses, BFS, annuler; jamais pop(0) sur une list.
  4. Tables de hachage: clé → hash → alvéole; facteur de charge α = n/m; chaînage contre adressage ouvert; tombstone; Bloom sans faux négatifs.
  5. Arbres et tas: vocabulaire (hauteur, complétude); quatre parcours; tas min = Arbre complet + parent ≤ enfants; tableau et indices 2i+1/2i+2; insertion et extraction O(log n), construction O(n); heapq.
  6. BST: invariant sur les sous-arbres entiers; recherche/insertion le long d'un chemin O(h); suppression à deux enfants par successeur infixe; dégénérescence en peigne et équilibrage AVL / rouge-noir.
  7. Grille finale: quelle structure pour quel besoin (tableau, liste, pile/file, hachage, BST, tas), avec le pire cas de la table de hachage en réserve.