Structures de données en terminale NSI : comprendre au lieu d'apprendre par cœur

La plupart des élèves apprennent ce chapitre comme du vocabulaire : pile égale LIFO, file égale FIFO, arbre égale hiérarchie. Ils récitent correctement et se retrouvent bloqués dès qu'un exercice demande de choisir la bonne structure, parce que la définition ne dit rien sur le moment où il faut l'utiliser.

L'ordre utile est inverse. On part du problème, on regarde quelles opérations il exige, et la structure s'impose d'elle-même. Une fois ce réflexe installé, les définitions deviennent inutiles à mémoriser : elles se retrouvent.

Une pile sert à retenir un chemin pour le défaire. C'est la structure du bouton annuler, du bouton retour d'un navigateur, et de la vérification de parenthèses. C'est aussi ce que la machine utilise elle-même pour gérer les appels de fonctions, ce qui explique pourquoi la récursivité et les piles sont enseignées ensemble.

def bien_parenthesee(expr):
    pile = []
    for c in expr:
        if c == "(":
            pile.append(c)
        elif c == ")":
            if not pile:        # une fermante sans ouvrante
                return False
            pile.pop()
    return len(pile) == 0       # rien ne doit rester ouvert

print(bien_parenthesee("(a+(b*c))"))   # True
print(bien_parenthesee("(a+b))"))      # False

En Python, une liste fait très bien l'affaire : append pour empiler, pop pour dépiler. Il n'est pas nécessaire d'écrire une classe, sauf si l'énoncé le demande explicitement.

Une file sert quand le premier arrivé doit être le premier traité : une file d'attente, une file d'impression, les messages à envoyer. Elle apparaît aussi dans le parcours en largeur d'un arbre ou d'un graphe, qui est l'un des algorithmes les plus demandés en terminale.

file = []
file.append("a")
premier = file.pop(0)   # retire en tête : coûteux

from collections import deque

file = deque()
file.append("a")
premier = file.popleft()   # retire en tête : immédiat

Un arbre représente ce qui se ramifie : un système de fichiers, un arbre généalogique, les coups possibles dans un jeu. En terminale, l'arbre binaire de recherche est le cas central, parce qu'il permet de chercher rapidement dans un ensemble ordonné.

L'intuition à retenir : chercher dans un arbre binaire de recherche équilibré revient à couper le problème en deux à chaque étape, comme quand on cherche un mot dans un dictionnaire papier.

Multiplier la taille des données par mille ne coûte que dix comparaisons de plus. C'est toute la raison d'être des arbres, et c'est la réponse attendue à la question « pourquoi ne pas se contenter d'une liste ». Elle fait aussi une très bonne question de Grand oral.

# Un noeud : (valeur, sous-arbre gauche, sous-arbre droit)
# None represente un arbre vide.
arbre = (8, (3, None, None), (12, None, None))

def infixe(a):
    if a is None:
        return []
    valeur, gauche, droit = a
    return infixe(gauche) + [valeur] + infixe(droit)

print(infixe(arbre))   # [3, 8, 12] : trié

Un graphe généralise l'arbre : les liens n'ont plus de hiérarchie et les cycles sont autorisés. Réseau social, plan de métro, réseau informatique. Deux représentations sont au programme, et le choix entre elles est une question d'examen fréquente.

from collections import deque

graphe = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

def parcours_largeur(g, depart):
    vus = {depart}
    file = deque([depart])
    ordre = []
    while file:
        s = file.popleft()
        ordre.append(s)
        for voisin in g[s]:
            if voisin not in vus:
                vus.add(voisin)
                file.append(voisin)
    return ordre

print(parcours_largeur(graphe, "A"))   # ['A', 'B', 'C', 'D']