Piles, files et arbres binaires · NSI Terminale (maths expertes)

Les piles (LIFO)

Une pile fonctionne comme une pile d'assiettes : on pose une assiette sur le dessus, et on ne reprend que celle du dessus.

On décrit une structure par son interface (ce qu'on peut faire avec) et non par son implémentation (comment c'est codé). Une pile peut être codée avec une liste Python, une liste chaînée, etc. : l'interface reste la même.

class Pile:

    def __init__(self):

        self.elements = []

    def empiler(self, x):

        self.elements.append(x)

    def depiler(self):

        return self.elements.pop()

    def est_vide(self):

        return len(self.elements) == 0

Entraîne-toi★☆☆

On considère une pile initialement vide. On effectue successivement les opérations suivantes : empiler(4), empiler(7), empiler(2), depiler(), empiler(9), depiler(). a)…

On considère une pile initialement vide. On effectue successivement les opérations suivantes : empiler(4), empiler(7), empiler(2), depiler(), empiler(9), depiler().

a) Donner le contenu de la pile après chaque opération (le sommet étant indiqué).

b) Donner la valeur renvoyée par chacun des deux appels à depiler().

c) Indiquer le principe (LIFO ou FIFO) suivi par une pile.

Résoudre

Entraîne-toi★★☆

On souhaite vérifier qu'une expression contenant des parenthèses, par exemple ((3+2)(4-1)), est bien parenthésée, à l'aide d'une pile. a) Décrire l'algorithme : que…

On souhaite vérifier qu'une expression contenant des parenthèses, par exemple ((3+2)*(4-1)), est bien parenthésée, à l'aide d'une pile.

a) Décrire l'algorithme : que fait-on à la lecture d'une parenthèse ouvrante, puis d'une parenthèse fermante ? Quelle condition finale garantit que l'expression est bien parenthésée ?

b) Appliquer l'algorithme à ((3+2)*(4-1)) en donnant la taille de la pile après la lecture de chaque parenthèse.

c) Appliquer l'algorithme à (5*(2+1))*3) et indiquer à quel moment l'erreur est détectée.

Résoudre

Les files (FIFO)

Une file s'implémente avec une liste Python, mais retirer le premier élément d'une liste (pop(0)) oblige à décaler tous les autres. On peut aussi utiliser collections.deque.

class File:

    def __init__(self):

        self.elements = []

    def enfiler(self, x):

        self.elements.append(x)

    def defiler(self):

        return self.elements.pop(0)

    def est_vide(self):

        return len(self.elements) == 0

Entraîne-toi★☆☆

On considère une file initialement vide. On effectue successivement : enfiler("Anna"), enfiler("Hugo"), enfiler("Léa"), defiler(), enfiler("Paul"), defiler(). a) Donner…

On considère une file initialement vide. On effectue successivement : enfiler("Anna"), enfiler("Hugo"), enfiler("Léa"), defiler(), enfiler("Paul"), defiler().

a) Donner le contenu de la file après chaque opération (en précisant la tête et la queue).

b) Donner les valeurs renvoyées par les deux appels à defiler().

c) Indiquer le principe (LIFO ou FIFO) suivi par une file.

Résoudre

Entraîne-toi★★☆

Dans un service d'urgences de l'hôpital de Lille, les patients sont pris en charge dans l'ordre d'arrivée. On modélise la salle d'attente par une file. Arrivent dans…

Dans un service d'urgences de l'hôpital de Lille, les patients sont pris en charge dans l'ordre d'arrivée. On modélise la salle d'attente par une file. Arrivent dans l'ordre : Martin, Dubois, Petit, Roux. Martin est pris en charge, puis Lemaire arrive, puis deux patients sont pris en charge.

a) Donner l'état de la file à la fin.

b) Indiquer quels patients ont été pris en charge, dans l'ordre.

c) Écrire en Python une classe File avec les méthodes enfiler, defiler et est_vide, en utilisant une liste Python comme attribut.

Résoudre

Entraîne-toi★★★

On implémente une file à l'aide de deux piles entree et sortie. Pour enfiler, on empile dans entree. Pour défiler, si sortie est vide, on transfère tous les éléments de…

On implémente une file à l'aide de deux piles entree et sortie. Pour enfiler, on empile dans entree. Pour défiler, si sortie est vide, on transfère tous les éléments de entree vers sortie (en dépilant puis empilant), puis on dépile sortie.

a) Exécuter la séquence : enfiler 1, 2, 3 ; défiler ; enfiler 4 ; défiler ; défiler. Donner l'état des deux piles après chaque opération.

b) Montrer que l'ordre FIFO est bien respecté.

c) Un défilement peut coûter $n$ opérations élémentaires. Montrer néanmoins que, pour $n$ éléments enfilés puis tous défilés, le coût total est en $O(n)$.

Résoudre

Arbres binaires

Un système de fichiers, un arbre généalogique ou un tournoi à élimination directe se représentent par un arbre.

La taille est le nombre de nœuds (ici 6).
La hauteur est le nombre de niveaux (ici 3, avec la convention : racine seule = hauteur 1).
Les feuilles sont D, E et F.

Pourquoi ? Chaque niveau contient au moins un nœud, d'où $n \ge h$. Le niveau $k$ contient au plus $2^{k-1}$ nœuds, d'où $n \le 1 + 2 + \dots + 2^{h-1} = 2^h - 1$. Le logarithme sert ici simplement à compter : $2^h \ge n+1$.

Entraîne-toi★☆☆

On considère l'arbre binaire suivant : la racine est A ; A a pour fils gauche B et pour fils droit C ; B a pour fils gauche D et pour fils droit E ; C a pour unique fils…

On considère l'arbre binaire suivant : la racine est A ; A a pour fils gauche B et pour fils droit C ; B a pour fils gauche D et pour fils droit E ; C a pour unique fils droit F ; D, E et F sont des feuilles.

a) Donner la taille de cet arbre.

b) Donner sa hauteur (en convenant que la racine seule a une hauteur de 1).

c) Donner la liste des feuilles.

Résoudre

Entraîne-toi★★★

Un arbre binaire de hauteur $h$ (la racine seule ayant pour hauteur 1) a une taille $n$. a) Montrer que $h \le n \le 2^h - 1$. b) En déduire un encadrement de $h$ en…

Un arbre binaire de hauteur $h$ (la racine seule ayant pour hauteur 1) a une taille $n$.

a) Montrer que $h \le n \le 2^h - 1$.

b) En déduire un encadrement de $h$ en fonction de $n$ et justifier que $h \ge \lceil \log_2(n+1) \rceil$.

c) Un arbre binaire de recherche de 1 000 nœuds a au minimum quelle hauteur ? Donner la hauteur maximale et expliquer dans quel cas elle est atteinte.

Résoudre

Parcours et arbres binaires de recherche

Pour parcourir un arbre, on visite chaque nœud une fois. Trois parcours en profondeur (récursifs) existent, et un parcours en largeur.

Parcours	Ordre
préfixe	racine, sous-arbre gauche, sous-arbre droit
infixe	sous-arbre gauche, racine, sous-arbre droit
suffixe	sous-arbre gauche, sous-arbre droit, racine
en largeur	niveau par niveau, de gauche à droite (avec une file)

Sur l'arbre A, B, C, D, E, F ci-dessus : préfixe A B D E C F ; infixe D B E A C F ; suffixe D E B F C A ; largeur A B C D E F.

def infixe(arbre):

    if arbre is not None:

        infixe(arbre.gauche)

        print(arbre.valeur)

        infixe(arbre.droit)

Le parcours en largeur utilise une file : on enfile la racine, puis tant que la file n'est pas vide, on défile un nœud, on l'affiche et on enfile ses fils.

Conséquence : le parcours infixe d'un ABR donne les valeurs dans l'ordre croissant (on visite d'abord les plus petites, puis la racine, puis les plus grandes, et cela vaut à chaque niveau).

class Noeud:

    def __init__(self, valeur):

        self.valeur = valeur

        self.gauche = None

        self.droit = None

def inserer(arbre, v):

    if arbre is None:

        return Noeud(v)

    if v <= arbre.valeur:

        arbre.gauche = inserer(arbre.gauche, v)

    else:

        arbre.droit = inserer(arbre.droit, v)

    return arbre

Entraîne-toi★★☆

Un arbre binaire a pour racine 10. Le fils gauche de 10 est 6, son fils droit est 14. Le fils gauche de 6 est 3 ; le fils droit de 6 est 8. Le fils gauche de 14 est 12 ;…

Un arbre binaire a pour racine 10. Le fils gauche de 10 est 6, son fils droit est 14. Le fils gauche de 6 est 3 ; le fils droit de 6 est 8. Le fils gauche de 14 est 12 ; 14 n'a pas de fils droit.

a) Dessiner (décrire) l'arbre et donner sa taille et sa hauteur (on convient qu'un arbre réduit à sa seule racine a pour hauteur 1).

b) Donner les parcours préfixe, infixe et suffixe.

c) Donner le parcours en largeur.

d) Montrer que cet arbre est un arbre binaire de recherche.

Résoudre

Entraîne-toi★★★

On représente un arbre binaire de recherche par une classe Noeud possédant les attributs valeur, gauche et droit (ces deux derniers valant None en l'absence de fils). a)…

On représente un arbre binaire de recherche par une classe Noeud possédant les attributs valeur, gauche et droit (ces deux derniers valant None en l'absence de fils).

a) Écrire une fonction récursive inserer(arbre, v) qui insère la valeur v dans l'arbre et renvoie la racine.

b) Dessiner l'arbre obtenu en insérant successivement 8, 3, 10, 1, 6, 14, 4, puis donner son parcours infixe.

c) Justifier que le parcours infixe d'un arbre binaire de recherche fournit les valeurs triées dans l'ordre croissant.

d) Donner la hauteur de l'arbre obtenu si l'on insère 1, 2, 3, 4, 5, 6, 7 dans cet ordre et commenter le coût d'une recherche.

Résoudre

À s'entraîner ! 9 exercices dans cette section

★☆☆ On considère une pile initialement vide. On effectue successivement les opérations…★☆☆ On considère une file initialement vide. On effectue successivement : enfiler("Anna"),…★☆☆ On considère l'arbre binaire suivant : la racine est A ; A a pour fils gauche B et pour…

L'essentiel

Pile : LIFO, opérations empiler, depiler, est_vide. File : FIFO, opérations enfiler, defiler, est_vide.
L'interface décrit ce qu'on peut faire ; l'implémentation décrit comment c'est codé.
Un arbre binaire a une racine, des nœuds, des feuilles ; sa taille $n$ et sa hauteur $h$ vérifient $h \le n \le 2^h - 1$.
Parcours : préfixe, infixe, suffixe (récursifs), largeur (avec une file).
Dans un ABR, le parcours infixe donne les valeurs triées ; la recherche est rapide si l'arbre est équilibré (hauteur proche de $\log_2 n$).
Vers le début : la file de la gare est une file (FIFO), le bouton « page précédente » repose sur une pile (LIFO).