NSI · terminale speGratuit

Chapitre 1 — Structures de données

L'essentiel en 30 secondes

En terminale, tu manipules $5$ structures de données fondamentales : la liste chaînée (éléments reliés par des pointeurs), la pile (LIFO $—$ dernier entré, premier sorti), la file (FIFO $—$ premier entré, premier sorti), l'arbre binaire (structure hiérarchique avec au plus $2$ fils par nœud) et le dictionnaire (association clé $\to$ valeur avec accès en $O(1)$ en moyenne). Chaque structure $a$ ses opérations propres et ses cas d'usage.

Notions clés

Liste chaînée: Suite de maillons, chaque maillon contient une valeur et une référence vers le maillon suivant. L'accès au i-ème élément est en O(n).
Pile (stack): Structure LIFO : on empile (push) et on dépile (pop) uniquement par le sommet. Ex : pile d'appels de fonctions, Ctrl+Z.
File (queue): Structure FIFO : on enfile à l'arrière et on défile à l'avant. Ex : file d'attente d'impression, tampon réseau.
Arbre binaire: Structure hiérarchique : une racine, chaque nœud a au plus un fils gauche et un fils droit. Un arbre vide est noté None.
Dictionnaire: Collection de paires clé:valeur. Implémenté par table de hachage. Accès, insertion et suppression en O(1) en moyenne.
Arbre binaire de recherche (ABR): Arbre binaire où pour tout nœud, les valeurs du sous-arbre gauche sont inférieures et celles du sous-arbre droit supérieures.

Formules

Classe Maillon (liste chaînée)

`class Maillon:\n def __init__(self, valeur, suivant=None):\n self.valeur = valeur\n self.suivant = suivant`

Condition : Base de l'implémentation d'une liste chaînée

Opérations de pile

`pile.append(x) # empiler\npile.pop() # dépiler\npile[-1] # consulter le sommet`

Condition : En Python, on simule une pile avec une list

Classe Arbre binaire

`class Noeud:\n def __init__(self, valeur, gauche=None, droit=None):\n self.valeur = valeur\n self.gauche = gauche\n self.droit = droit`

Condition : Structure récursive : chaque fils est un Noeud ou None

Taille d'un arbre

`def taille(arbre):\n if arbre is None:\n return 0\n return 1 + taille(arbre.gauche) + taille(arbre.droit)`

Condition : Complexité O(n) — parcours complet de l'arbre

A retenir

Pile = LIFO, File = FIFO : ne jamais confondre l'ordre d'accès.
Un arbre binaire se manipule toujours récursivement : cas de base = arbre vide (None).
Un dictionnaire Python {} est une table de hachage : les clés doivent être non mutables (str, int, tuple).

Erreurs classiques

Erreur : Confondre pile et file

Correction : Pile = LIFO (pile d'assiettes). File = FIFO (queue au cinéma). Retiens l'image concrète.

Erreur : Oublier le cas de base None dans les fonctions récursives sur les arbres

Correction : Toujours commencer par `if arbre is None: return ...` avant de traiter le cas récursif.

Erreur : Utiliser une liste mutable comme clé de dictionnaire

Correction : Les clés doivent être hashables : utilise un tuple au lieu d'une liste.

Astuce méthode

Au bac, quand tu implémentes une fonction sur un arbre, écris d'abord le cas de base (None), puis le cas récursif. Dessine l'arbre sur ton brouillon avec 3-4 nœuds pour vérifier ton code à la main.