Structures de données : piles, files, objets, arbres et graphes

Trois demandes fictives A, B, C arrivent dans cet ordre. Une file traite A d’abord : c’est FIFO, premier entré, premier sorti. Une pile rend C d’abord : c’est LIFO, dernier entré, premier sorti. La pile convient à un historique à remonter ; la file conserve l’ordre d’attente. Ni l’une ni l’autre ne choisit automatiquement la demande la plus urgente.

Un type abstrait décrit les valeurs manipulées et les opérations permises, avec leurs préconditions et leurs résultats. Son interface expose ces opérations au programme client. L’implantation décide comment les réaliser. Dire « empiler ajoute un élément au sommet » appartient au contrat ; dire « utiliser la dernière case d’une liste Python » appartient à une implantation.

Notre première pile est un tuple : creer_pile() rend (), empiler(p, x) rend une nouvelle pile, sommet(p) observe sans retirer, et depiler(p) rend le couple (valeur, nouvelle_pile). Sur le vide, les deux dernières opérations lèvent ValueError. La loi depiler(empiler(p, x)) == (x, p) exprime le comportement attendu sur les valeurs ordinaires utilisées ici.

Il faut réaffecter le résultat : appeler seulement empiler(p, 'A') laisse p inchangé. C’est un contrat fonctionnel, différent de la classe mutable de l’étape suivante. Le tuple ne change pas de cases, mais les objets qu’il référence peuvent être mutables. Ajouter à une liste stockée dedans reste possible : immuable ne signifie pas copie profonde.

Ce modèle privilégie une trace facile à lire. Concaténer ou découper un tuple de n éléments recopie des références : ces opérations coûtent O(n), même si leur écriture tient en une ligne. La conformité LIFO ne garantit donc pas l’efficacité. On pourra changer de stockage tout en préservant un contrat donné.

Une classe réunit une description d’état et des méthodes pour agir dessus. p = Pile() crée une instance ; __init__ initialise cette nouvelle instance. L’attribut p._contenu porte ses données. La méthode p.empiler('A') utilise self pour désigner p ; dans cet exemple, cet appel équivaut à Pile.empiler(p, 'A').

Contrairement au tuple de l’étape précédente, cette pile se modifie sur place. empiler ne rend pas une nouvelle pile : sans return, son résultat est None. Écrire p = p.empiler('A') ferait donc perdre la référence à l’objet. depiler retire puis rend la valeur ; sommet rend la valeur sans changer l’ordre ni la taille.

Placer _contenu = [] directement dans le corps de la classe créerait une liste partagée par les instances qui l’utilisent. La créer dans __init__ donne à p et q deux listes distinctes. Ne confonds pas ce défaut avec q = p : cette affectation donne volontairement deux noms au même objet, sans créer une deuxième pile.

L’interface maintient un invariant : les valeurs sont rangées de la plus ancienne à la plus récente, et seul le sommet est retiré. Sur le vide, observer ou retirer lève ValueError sans changer l’état. Le préfixe _ signale un détail interne par convention ; il n’empêche pas techniquement le client de modifier cet attribut.

observer() renvoie un tuple des valeurs, pour examiner l’ordre sans donner directement la liste de rangement. Ce tuple est une copie superficielle des références : si une valeur est elle-même une liste, elle reste partagée. L’indépendance des conteneurs et l’indépendance des objets contenus sont deux questions différentes.

Une liste abstraite représente une suite. Une implantation chaînée relie une cellule, qui contient une valeur, à la suivante. Dans ('A', ('B', None)), la tête vaut A, puis on suit un lien pour atteindre B. Ajouter en tête crée une cellule ; accéder à l’élément d’indice k oblige à suivre k liens. None représente ici la fin de chaîne.

Une list de CPython est un tableau dynamique de références, pas une liste chaînée. L’accès par indice est direct, tandis que retirer en tête avec pop(0) décale les références suivantes. Retirer à la fin évite ce décalage. Les coûts décrivent une implantation et un modèle d’opérations, pas la longueur du code ni un chronométrage universel.

Un dictionnaire associe une valeur à une clé. Avec catalogue = {'T2': 'dessiner', 'T7': 'tester'}, catalogue['T7'] vaut « tester » : T7 n’est pas un rang. in teste les clés, et réaffecter une clé remplace sa valeur. Dans une table de hachage, l’accès est en moyenne O(1) si le hachage répartit correctement les clés et si calculer leur hash et les comparer coûte O(1) ; ce n’est pas une garantie du pire cas.

Pour traiter des identifiants dans l’ordre d’arrivée, emploie une file et garde leurs descriptions dans un dictionnaire. Changer la description de T7 ne doit pas déplacer T7 dans l’attente. Une clé inconnue lève KeyError dans un accès direct : choisis et documente le comportement souhaité avant de le masquer par une valeur par défaut.

Notre File stocke les valeurs dans une liste avec un indice de tête. Défiler avance cet indice, libère la référence consommée puis compacte occasionnellement la liste. L’invariant est 0 <= _tete <= len(_donnees) ; les éléments actifs commencent à _tete. Une sortie peut coûter O(n) lors d’une copie, mais une longue suite d’opérations a un coût amorti O(1) par ajout ou retrait. observer() copie les n éléments actifs et reste O(n).

Un arbre enraciné organise des nœuds à partir d’une racine. Chaque autre nœud possède un unique parent ; il n’y a pas de cycle et tous les nœuds sont accessibles depuis la racine. Une feuille n’a aucun enfant. Le sous-arbre enraciné en un nœud comprend ce nœud et ses descendants. Un arbre non vide de n nœuds possède n − 1 arêtes.

Dans un arbre binaire, chaque nœud possède deux emplacements distingués : gauche et droit. Chacun peut contenir un sous-arbre ou être vide. Un enfant gauche seul et un enfant droit seul ne donnent donc pas la même structure. Un arbre binaire n’est pas automatiquement un arbre binaire de recherche : ce dernier ajoute des règles d’ordre sur les clés.

La profondeur d’un nœud est ici le nombre d’arêtes depuis la racine ; la racine est à profondeur 0. La hauteur de l’arbre est la profondeur maximale. Un singleton a donc hauteur 0 ; nous donnons à l’arbre vide la hauteur −1 pour garder la même formule récursive. D’autres exercices comptent les nœuds : pour un arbre non vide, leur hauteur vaut la nôtre plus 1. Vérifie toujours la convention.

Le modèle Python emploie None pour le vide et (valeur, gauche, droite) pour un nœud. La taille vérifie 1 + taille(gauche) + taille(droite) ; la hauteur vérifie 1 + max(hauteur(gauche), hauteur(droite)). Les fonctions supposent une structure finie bien formée. Elles ne valident pas un objet arbitraire et la profondeur d’appels reste limitée par l’exécution Python.

Pour un arbre binaire non vide de hauteur h et de taille n, h + 1 <= n <= 2**(h + 1) - 1. Le chemin le plus long fournit la borne basse ; les niveaux pleins de 1, 2, 4… nœuds donnent la borne haute. À taille fixée, une chaîne donne la hauteur maximale n − 1. Ces bornes évitent d’accepter un résultat impossible.

Dire qu’un arbre est complet exige une définition. Dans le transfert, tous les niveaux sauf peut-être le dernier sont pleins et le dernier se remplit de gauche à droite. Un arbre parfait a tous ses niveaux pleins. L’exemple dessiné est complet, mais pas parfait : au dernier niveau, 1 et 6 occupent les deux premières places, puis les deux places sous 10 restent vides.

Un graphe décrit des sommets et leurs relations. Une arête non orientée relie deux sommets sans ordre ; un arc orienté va d’un sommet de départ vers un sommet d’arrivée. Avec A → B, B est successeur de A et A est prédécesseur de B. L’arc inverse n’existe que si on l’ajoute. Les graphes suivants utilisent des lettres fictives, sans personnes ni réseau réel.

On représente ici les successeurs par un dictionnaire d’ensembles. Dans {'A': {'B'}, 'B': {'C'}, 'C': set(), 'D': set()}, C n’a aucune sortie mais reçoit l’arc venant de B. D est isolé : aucune entrée ni sortie. Un ensemble évite les doublons ; ce modèle ne représente pas plusieurs arcs parallèles. Le laboratoire autorise un arc d’un sommet vers lui-même, appelé boucle.

Pour écrire une matrice, fixe un ordre des sommets, par exemple A, B, C, D. La case M[i][j] vaut 1 si un arc va du sommet de la ligne i au sommet de la colonne j, et 0 sinon. La ligne B contient donc un 1 dans la colonne C. Changer l’ordre permute les lignes et les colonnes ensemble ; une matrice sans ses étiquettes perd cette correspondance.

Une représentation non orientée doit être symétrique : B apparaît chez A si et seulement si A apparaît chez B. Dans une matrice orientée, une ligne nulle ne suffit pas pour conclure « isolé » : vérifie aussi la colonne. Les sommes d’une ligne et d’une colonne donnent les degrés sortant et entrant de nos graphes sans arcs multiples ; une boucle compte une fois dans chacun.

La matrice prend O(n²) cases pour n sommets ; tester une case est direct, mais énumérer les voisins exige de lire une ligne. Le dictionnaire d’ensembles utilise O(n + m) emplacements, à un facteur constant près pour un graphe non orienté. Parcourir un ensemble de successeurs visite seulement ces voisins. Il ne faut pas confondre récupérer une collection et parcourir son contenu.

Le code vérifie les étiquettes, les extrémités et la forme de la matrice. Une valeur booléenne n’est pas acceptée à la place d’un entier 0 ou 1. La conversion inverse recrée aussi les sommets isolés. Ces contrôles font partie du coût du programme fourni ; ils ne sont pas gratuits sous prétexte qu’une opération élémentaire est O(1). ajouter_arete modifie le graphe non orienté sur place et renvoie None ; une extrémité invalide est refusée avant toute écriture.

Le programme client d’une file utilise enfiler, defiler, tete, est_vide et observer. Il ne lit ni _donnees ni _tete. Une seconde implantation peut alors employer deux piles : une pile d’entrée reçoit les arrivées, une pile de sortie fournit les retraits. Ici, chaque pile est réalisée par une liste avec append et pop à droite.

Quand la pile de sortie est vide, transfère toute la pile d’entrée vers elle. L’inversion fait remonter le plus ancien élément au sommet de la sortie. Si la sortie n’est pas vide, ne transfère rien : ses éléments sont arrivés avant ceux qui attendent encore dans l’entrée. Transférer trop tôt ferait passer un nouveau venu devant eux.

L’état abstrait observable correspond à reversed(sortie) suivi de entree. tete() peut provoquer un transfert interne, mais elle ne change ni l’ordre logique ni le nombre d’éléments. C’est un exemple où « observer sans modifier la file » ne signifie pas « aucune case interne ne change ». Le contrat parle de ce que le client est autorisé à observer.

Chaque élément est empilé à l’entrée, transféré au plus une fois, puis retiré de la sortie. Sur une suite d’opérations, cela justifie un coût amorti O(1) par opération de file, avec les coûts usuels amortis des listes Python. Un transfert isolé peut coûter O(n). Copier une observation de toute la file coûte toujours O(n), quelle que soit l’implantation étudiée.

Le banc de conformité reçoit une fabrique d’objets et joue les mêmes commandes. Il vérifie l’ordre, les observations répétées, les erreurs sur le vide et l’indépendance de deux instances. Réussir un corpus fini donne des preuves sur ces cas, pas sur tous les usages possibles. La substituabilité exige le même contrat complet ; la rapidité se compare dans une analyse séparée.