NSIChapitre 1

Structures de données

L'essentiel en 30 secondes

En terminale, tu manipules les structures de données fondamentales : la liste chaînée (maillons reliés par des pointeurs, insertion en tête en $O(1)$), la pile (LIFO — dernier entré, premier sorti), la file (FIFO — premier entré, premier sorti), l'arbre binaire (structure hiérarchique récursive avec au plus 2 fils par nœud, 3 parcours en profondeur + 1 en largeur), l'ABR (gauche < racine < droit), et le dictionnaire (clé → valeur, accès moyen en $O(1)$). Chaque structure a son interface (opérations) et peut avoir plusieurs implémentations.

Les notions à connaître

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)$ $. Insertion/suppression$ en tête en $O(1)$ .
Pile (stack): Structure LIFO (Last In, First Out) : on empile (push) et on dépile (pop) uniquement par le sommet. Ex : pile d'appels de fonctions, Ctrl+Z, évaluation d'expressions postfixées.
File (queue): Structure FIFO (First In, First Out) : on enfile à l'arrière et on défile à l'avant. Ex : file d'attente d'impression, tampon réseau, parcours en largeur (BFS).
Arbre binaire: Structure hiérarchique récursive : une racine, chaque nœud a au plus un fils gauche et un fils droit. Un arbre vide est noté None. La hauteur d'un arbre de n nœuds est au minimum $\lfloor \log_2(n) \rfloor$ .
Dictionnaire (table de hachage): Collection de paires clé:valeur. Implémenté par table de hachage en Python. Accès, insertion et suppression en $O(1)$ en moyenne, $O(n)$ dans le pire cas (collisions).
Arbre binaire de recherche (ABR): Arbre binaire où pour tout nœud N, toutes les valeurs du sous-arbre gauche < N < toutes les valeurs du sous-arbre droit. Recherche en $O(h)$ où h est la hauteur.
Hauteur d'un arbre: Nombre d'arêtes du plus long chemin de la racine à une feuille. Un arbre vide a une hauteur de -1 (convention) ou 0 selon la convention. Une feuille a une hauteur de 0.
Parcours d'arbre: 3 parcours en profondeur (DFS) : préfixe (Racine-G-D), infixe (G-Racine-D), suffixe (G-D-Racine). 1 parcours en largeur (BFS) : niveau par niveau.

Les erreurs à éviter en nsi

Confondre pile et file
Pile = LIFO (pile d'assiettes). File = FIFO (queue au cinéma). Retiens l'image concrète.
Oublier le cas de base None dans les fonctions récursives sur les arbres
Toujours commencer par if arbre is None: return ... avant de traiter le cas récursif.
Utiliser une liste mutable comme clé de dictionnaire
Les clés doivent être hashables : utilise un tuple au lieu d'une liste.
Utiliser list.pop(0) pour une file
pop(0) est en $O(n)$ car il décale tous les éléments. Utilise collections.deque et popleft() en $O(1)$ .
Confondre parcours préfixe, infixe et suffixe
Préfixe = Racine-G-D, Infixe = G-Racine-D, Suffixe = G-D-Racine. Le nom indique quand on traite la Racine.

Sais-tu répondre à ces questions ?

Les corrigés détaillés sont dans le quiz du chapitre.

Dans une pile (stack), quelle opération permet de retirer le dernier élément ajouté ?
Quelle structure de données fonctionne selon le principe FIFO (First In, First Out) ?
Dans un dictionnaire Python, quelle est la complexité moyenne d'un accès par clé ?
On considère la classe suivante : class Maillon: def $__init__(self$ , valeur, $suivant=None)$ : self.valeur $=$ valeur self.suivant $=$ suivant liste $= Maillon(3, Maillon(7, Maillon(12)))$ Que vaut liste.suivant.valeur ?
On exécute les opérations suivantes sur une pile initialement vide : pile = [] pile.append(5) pile.append(8) pile.append(2) pile.pop() pile.append(9) Quel est le sommet de la pile ?

Accède à la fiche complète

Crée ton compte gratuit pour lire la fiche en entier et accéder à 7 000+ contenus de révision.

Créer un compte gratuit Se connecter