Piles, files et arbres binaires

Piles : dernier arrivé, premier sorti

Une pile est une structure de données où l'on n'accède qu'à un seul élément : le sommet. Comme une pile d'assiettes, on pose une assiette sur le dessus et on reprend celle du dessus. On dit que la pile suit le principe LIFO (Last In, First Out).

L'interface d'une pile se réduit à quelques méthodes :

Application : vérifier un parenthésage

Pour savoir si ((3+2)*(4-1)) est bien parenthésée, on lit l'expression de gauche à droite :

• parenthèse ouvrante : on l'empile ;

• parenthèse fermante : si la pile est vide, erreur ; sinon on dépile ;

• à la fin, l'expression est bien parenthésée si et seulement si la pile est vide.

Le dernier ( ouvert doit être le premier refermé : c'est exactement le principe LIFO.

Files : premier arrivé, premier sorti

Une file suit le principe FIFO (First In, First Out) : on ajoute à la queue et on retire à la tête, comme à la caisse d'un supermarché.

Implémentation en Python

Une même interface peut avoir plusieurs implémentations. Voici une file écrite avec une liste Python comme attribut :

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

L'utilisateur de la classe n'a besoin que de l'interface : il ne sait pas (et n'a pas à savoir) que c'est une liste qui est cachée à l'intérieur.

Une file avec deux piles

On peut aussi implémenter une file avec deux piles entree et sortie. On enfile dans entree. Pour défiler : si sortie est vide, on y transfère tout entree (ce qui inverse l'ordre), puis on dépile sortie. L'inversion de l'inversion rétablit l'ordre d'arrivée : c'est ce qui garantit le FIFO.

Un défilement peut coûter $n$ opérations, mais chaque élément n'est transféré qu'une seule fois : pour $n$ éléments enfilés puis défilés, le coût total reste proportionnel à $n$.

Arbres binaires

Une liste est linéaire. Pour représenter une hiérarchie (dossiers, arbre généalogique), on utilise un arbre. Dans un arbre binaire, chaque nœud a au plus deux fils : un fils gauche et un fils droit.

Encadrement de la hauteur

Un arbre de hauteur $h$ a au moins un nœud par niveau, et au plus $2^{k-1}$ nœuds au niveau $k$. Donc

On en déduit $h \ge \log_2(n+1)$, donc $h \ge \lceil \log_2(n+1) \rceil$. Un arbre « bien rempli » est donc très peu haut : 1 023 nœuds tiennent sur 10 niveaux.

Parcours d'un arbre binaire

Parcourir un arbre, c'est visiter chaque nœud une fois. Trois parcours en profondeur (récursifs) existent, selon le moment où l'on traite la racine par rapport à ses sous-arbres :

Le parcours en largeur visite les nœuds niveau par niveau, de gauche à droite. Il s'écrit avec une file : on enfile la racine ; tant que la file n'est pas vide, on défile un nœud, on l'affiche, puis on enfile ses fils gauche et droit.

Arbres binaires de recherche

Un arbre binaire de recherche (ABR) range des valeurs comparables avec la règle suivante : pour chaque nœud de valeur $v$, toutes les valeurs du sous-arbre gauche sont inférieures ou égales à $v$ (ou strictement inférieures, selon la convention) et toutes celles du sous-arbre droit sont supérieures.

Pourquoi c'est utile ? Pour chercher une valeur, on la compare à la racine : si elle est plus petite on va à gauche, sinon à droite. Chaque comparaison élimine un sous-arbre : dans un arbre bien équilibré, le coût est en $\log_2 n$ au lieu de $n$.

Parcours infixe. Il visite d'abord les valeurs inférieures à la racine, puis la racine, puis les valeurs supérieures, et ce à chaque niveau. Le parcours infixe d'un ABR donne donc les valeurs dans l'ordre croissant (ici : 1, 3, 6, 8, 10).

Insertion

Pour insérer v : si l'arbre est vide, on crée un nœud ; sinon on insère récursivement dans le sous-arbre gauche si v est plus petit que la racine, dans le droit sinon.

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

Vers le début : dans la salle d'attente, la file garantit l'ordre d'arrivée ; pour « Retour », la pile ramène à la dernière page.

L'essentiel

• Pile (LIFO) : empiler, depiler, est_vide ; on n'accède qu'au sommet.

• File (FIFO) : enfiler, defiler, est_vide ; on ajoute à la queue, on retire à la tête. Plusieurs implémentations sont possibles (liste Python, deux piles).

• Arbre binaire : racine, nœuds, feuilles, taille $n$, hauteur $h$, avec $h \le n \le 2^h - 1$.

• Parcours : préfixe, infixe, suffixe (en profondeur) ; en largeur (avec une file).

• ABR : gauche ≤ nœud < droit ; le parcours infixe est trié ; la recherche coûte environ $\log_2 n$ si l'arbre est équilibré, $n$ s'il est dégénéré.