Piles, files et arbres binaires

La pile : dernier arrivé, premier sorti

Imagine une pile d'assiettes. Tu poses une assiette sur le dessus, et tu reprends toujours celle du dessus. On ne touche pas à celles du dessous.

Une structure se décrit par son interface : la liste des opérations autorisées, sans dire comment elles sont codées.

Une implémentation possible en Python utilise une liste comme attribut : le sommet est la fin de la liste.

class Pile:

    def __init__(self):

        self.contenu = []

    def empiler(self, x):

        self.contenu.append(x)

    def depiler(self):

        return self.contenu.pop()

    def est_vide(self):

        return len(self.contenu) == 0

On pourrait écrire une autre implémentation (avec des maillons chaînés, par exemple) : l'interface resterait la même. C'est toute la différence entre interface et implémentation.

La file : premier arrivé, premier sorti

À la boulangerie, le premier client arrivé est le premier servi. On entre par la queue, on sort par la tête.

class File:

    def __init__(self):

        self.contenu = []

    def enfiler(self, x):

        self.contenu.append(x)      # ajout à la queue

    def defiler(self):

        return self.contenu.pop(0)  # retrait de la tête

    def est_vide(self):

        return len(self.contenu) == 0

Une file avec deux piles

On peut implémenter une file avec deux piles entree et sortie : l'interface de la file reste la même, seule l'implémentation change.

• enfiler(x) : on empile x dans entree.

• defiler() : si sortie est vide, on transfère tout entree dans sortie (en dépilant puis empilant : l'ordre est alors inversé), puis on dépile sortie.

Pourquoi ça marche ? Le plus ancien élément est au fond de entree ; après le transfert, il se retrouve au sommet de sortie. Le transfert est coûteux (autant d'opérations que d'éléments), mais chaque élément n'est transféré qu'une seule fois : il est empilé au plus deux fois et dépilé au plus deux fois au total.

Arbres binaires : vocabulaire

Un dossier contient des sous-dossiers, qui contiennent d'autres sous-dossiers : cette organisation hiérarchique ne se représente pas bien avec une liste. On utilise un arbre.

• La racine est le nœud tout en haut (ici S).

• Un fils (gauche ou droit) est un nœud directement sous un autre, son père. T et W sont les fils de S.

• Une feuille est un nœud sans fils : ici U, V et Y.

• La taille est le nombre de nœuds : ici 7.

• La hauteur est le nombre de niveaux : ici 4 (chemin S, W, X, Y). Convention : la racine seule a une hauteur de 1, et l'arbre vide a une hauteur de 0.

En Python, un arbre se représente par une classe Noeud ; l'absence de fils est notée None :

class Noeud:

    def __init__(self, valeur):

        self.valeur = valeur

        self.gauche = None

        self.droit = None

def taille(arbre):

    if arbre is None:

        return 0

    return 1 + taille(arbre.gauche) + taille(arbre.droit)

def hauteur(arbre):

    if arbre is None:

        return 0

    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

La structure de l'arbre est récursive, donc les fonctions qui le parcourent le sont aussi : on traite le cas de l'arbre vide, puis on combine les résultats des deux sous-arbres.

Taille et hauteur : un encadrement

Un arbre peut être « maigre » (une chaîne) ou « touffu » (tous les niveaux remplis). Quelle hauteur $h$ peut avoir un arbre de taille $n$ ?

Retiens l'idée : un arbre bien équilibré a une hauteur proportionnelle à $\log_2 n$, un arbre en chaîne a une hauteur proportionnelle à $n$. C'est ce qui rendra la recherche très rapide... ou pas.

Parcourir un arbre

Pour afficher ou traiter tous les nœuds, il faut choisir un ordre. Prenons cet arbre :

Les trois parcours en profondeur sont récursifs. Ils ne diffèrent que par le moment où on traite la racine :

def infixe(arbre):

    if arbre is not None:

        infixe(arbre.gauche)      # 1. sous-arbre gauche

        print(arbre.valeur)       # 2. racine

        infixe(arbre.droit)       # 3. sous-arbre droit

Le parcours en largeur visite les nœuds niveau par niveau, de gauche à droite : 15, 9, 20, 4, 12, 18, 25. Il utilise une file :

def largeur(arbre):

    f = File()

    f.enfiler(arbre)

    while not f.est_vide():

        n = f.defiler()

        if n is not None:

            print(n.valeur)

            f.enfiler(n.gauche)

            f.enfiler(n.droit)

Le nœud visité est le plus ancien de la file ; ses fils sont ajoutés à la queue, donc ils passent après tous les nœuds du niveau actuel : c'est le FIFO qui impose l'ordre par niveaux.

Arbres binaires de recherche

L'arbre précédent a une propriété particulière : à gauche de chaque nœud, il n'y a que des valeurs plus petites, à droite, que des plus grandes.

Rechercher une valeur

On compare la valeur cherchée à la racine : si elle est égale, on a trouvé ; si elle est plus petite, on cherche à gauche ; sinon, à droite. À chaque étape, on élimine un sous-arbre.

def rechercher(arbre, v):

    if arbre is None:

        return False

    if v == arbre.valeur:

        return True

    if v < arbre.valeur:

        return rechercher(arbre.gauche, v)

    return rechercher(arbre.droit, v)

Chercher 12 dans l'arbre précédent : $12 < 15$ → gauche ; $12 > 9$ → droite ; $12 = 12$ : trouvé en visitant 3 nœuds (15, 9 puis 12).

Insérer une valeur

On suit le même chemin que pour la recherche, jusqu'à arriver sur un emplacement vide (None) : c'est là qu'on crée le nouveau nœud, qui sera une feuille.

Le parcours infixe trie

Dans un ABR, le parcours infixe visite le sous-arbre gauche (valeurs plus petites que la racine), puis la racine, puis le sous-arbre droit (plus grandes). Cette propriété vaut à tous les niveaux, donc les valeurs sont affichées dans l'ordre croissant. Vérifie sur l'exemple : 4, 9, 12, 15, 18, 20, 25.

Hauteur et efficacité

Une recherche dans un ABR coûte au plus la hauteur $h$ de l'arbre. Si l'arbre est équilibré, $h$ est de l'ordre de $\log_2 n$ : en 1 000 nœuds, une dizaine de comparaisons : $h \ge \lceil \log_2(1001) \rceil = 10$ car $2^9 = 512 < 1001 \le 2^{10} = 1024$, donc un ABR de 1 000 nœuds a une hauteur minimale de 10 et une hauteur maximale de 1 000 (chaîne). Ici, $\log_2$ sert simplement à compter les niveaux. Mais si on insère des valeurs déjà triées (1, 2, 3, ...), chaque nouvelle valeur devient le fils droit de la précédente : l'arbre est une chaîne, de hauteur $n$, et la recherche coûte $n$ comparaisons.

Reviens au début : une page web précédente se retrouve avec une pile, les travaux d'impression avec une file, et un annuaire trié se parcourt vite avec un ABR bien équilibré.

L'essentiel

• Une pile est LIFO : empiler, depiler, est_vide. Une file est FIFO : enfiler, defiler, est_vide. On décrit une structure par son interface, indépendante de l'implémentation.

• Un arbre binaire a une racine, des nœuds, des feuilles, des sous-arbres gauche et droit. Sa taille est le nombre de nœuds, sa hauteur le nombre de niveaux (racine seule : 1).

• Encadrement : $h \le n \le 2^h - 1$, donc $h \ge \lceil \log_2(n+1) \rceil$.

• Parcours en profondeur : préfixe (racine, gauche, droit), infixe (gauche, racine, droit), suffixe (gauche, droit, racine). Parcours en largeur : niveau par niveau, avec une file.

• Dans un ABR, la recherche et l'insertion suivent un chemin depuis la racine ; le parcours infixe donne les valeurs triées. Le coût dépend de la hauteur.