Arbres binaires

Introduction

Quand les données ont une hiérarchie naturelle — un système de fichiers, un arbre généalogique, le DOM d'une page web, la décomposition syntaxique d'une expression — les structures linéaires ne suffisent plus. On utilise alors un arbre : un ensemble de nœuds organisés autour d'une racine, où chaque nœud porte un nombre fini d'enfants.

L'image la plus familière est l'arbre généalogique : une personne en haut, ses descendants qui se ramifient à mesure qu'on descend. La racine informatique est en haut par convention — les arbres en informatique poussent vers le bas, contrairement à leurs cousins botaniques.

Ce cours traite spécifiquement des arbres binaires (chaque nœud a au plus deux enfants), conformément à [TA01]. Les algorithmes associés (parcours préfixe, infixe, suffixe, BFS, DFS) sont abordés au chapitre TE.

Vocabulaire

Implémentation Python

On reprend l'outil objet du cours précédent. Un nœud est un objet portant une valeur, un fils gauche et un fils droit (qui sont eux-mêmes des nœuds ou None).

class Noeud:
    """Nœud d'un arbre binaire."""

    def __init__(self, valeur, gauche=None, droite=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droite = droite

    def est_feuille(self):
        return self.gauche is None and self.droite is None

Création d'un petit arbre :

#       1
#      / \
#     2   3
#    /
#   4
arbre = Noeud(1, Noeud(2, Noeud(4)), Noeud(3))

Mesurer un arbre binaire

Taille

Le nombre total de nœuds, défini récursivement :

def taille(noeud):
    if noeud is None:
        return 0
    return 1 + taille(noeud.gauche) + taille(noeud.droite)

Hauteur

La convention $\mathrm{hauteur}(\emptyset) = -1$ rend la formule cohérente : un arbre à un seul nœud a alors une hauteur $1 + \max(-1, -1) = 0$.

def hauteur(noeud):
    if noeud is None:
        return -1
    return 1 + max(hauteur(noeud.gauche), hauteur(noeud.droite))

Encadrement de la hauteur

Question canonique du BO : pour un arbre binaire de taille $n$ et de hauteur $h$, peut-on borner $h$ en fonction de $n$ ?

Preuve par récurrence

Montrons : un arbre binaire de hauteur $h$ vérifie $h + 1 \le n \le 2^{h+1} - 1$.

Initialisation ($h = 0$). L'arbre est réduit à sa racine. On a $n = 1$, et $h + 1 = 1$, et $2^{h+1} - 1 = 1$. L'inégalité $1 \le 1 \le 1$ tient.

Hérédité. Supposons la propriété vraie pour toute hauteur strictement inférieure à $h$ (avec $h \ge 1$). Soit $A$ un arbre binaire de hauteur $h$. Ses sous-arbres $A_g$ et $A_d$ ont chacun une hauteur $\le h - 1$, et au moins l'un des deux atteint $h - 1$ (sinon $A$ aurait une hauteur strictement inférieure à $h$).

• Minoration. Le sous-arbre qui atteint $h - 1$ contient au moins $(h - 1) + 1 = h$ nœuds par hypothèse de récurrence. Avec la racine de $A$, on a donc $n \ge 1 + h = h + 1$.
• Majoration. Chaque sous-arbre a au plus $2^{h} - 1$ nœuds par hypothèse de récurrence. Donc $n \le 1 + 2(2^{h} - 1) = 2^{h+1} - 1.$

L'inégalité est démontrée pour la hauteur $h$. Par récurrence, elle est vraie pour tout $h \ge 0$. Par passage au logarithme dans la majoration $n \le 2^{h+1} - 1$, on obtient $h \ge \log_2(n+1) - 1$, ce qui ferme l'équivalence annoncée. $\blacksquare$

Conséquences

• Un arbre filiforme (chaque nœud n'a qu'un seul enfant) atteint la borne basse : $n = h + 1$, donc $h = n - 1$.
• Un arbre parfaitement équilibré et complet atteint la borne haute : $n = 2^{h+1} - 1$, donc $h = \log_2(n+1) - 1$, soit $h \in \mathcal{O}(\log n)$.
• C'est pour cela que les structures arborescentes équilibrées sont recherchées : leurs opérations sont en $\mathcal{O}(\log n)$ au lieu de $\mathcal{O}(n)$.

Pour aller plus loin

Les arbres binaires de recherche (ABR), les tas binaires et les arbres équilibrés (AVL, rouge-noir) exploitent cette propriété d'encadrement pour garantir des opérations en $\mathcal{O}(\log n)$. Vous reviendrez sur certains d'entre eux au chapitre TE.