Algorithmes sur les arbres binaires

Introduction

L'arbre binaire est une structure récursive par construction : chaque nœud porte une valeur et peut posséder un sous-arbre gauche et un sous-arbre droit, eux-mêmes des arbres binaires. Cette nature récursive imprègne tous les algorithmes qui s'y appliquent — ils suivent presque tous le schéma « traiter la racine, recommencer à gauche, recommencer à droite ».

Cette forme arborescente n'est pas une invention de l'informatique : on la retrouve dans la classification du vivant de Linné (règnes, ordres, espèces), dans un organigramme d'entreprise, ou dans un arbre généalogique. Partout où l'on décrit une hiérarchie qui se ramifie, on peut la lire comme un arbre.

Cette section suppose la familiarité avec la structure d'arbre binaire et son vocabulaire (racine, feuille, nœud interne, hauteur, taille) — voir le chapitre Structures de données (TA01). Ici, on les parcourt.

Une classe Python pour les nœuds

On représente un arbre par une classe Noeud, chaque nœud référençant ses deux enfants éventuels. L'absence d'enfant est codée par None.

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

# Un petit arbre :
#         4
#        / \
#       2   6
#      / \   \
#     1   3   7
arbre = Noeud(4,
              Noeud(2, Noeud(1), Noeud(3)),
              Noeud(6, None, Noeud(7)))

Taille et hauteur

La taille d'un arbre est son nombre de nœuds ; sa hauteur est la longueur du plus long chemin de la racine à une feuille. Toutes deux se calculent par récurrence en suivant le squelette de la structure.

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

def hauteur(a):
    if a is None:
        return -1                          # par convention : arbre vide
    return 1 + max(hauteur(a.gauche), hauteur(a.droite))

Convention : la hauteur de l'arbre vide vaut $-1$, celle d'une feuille vaut $0$. Le coût des deux fonctions est en $\mathcal{O}(n)$ — chaque nœud est visité exactement une fois.

Les trois parcours en profondeur

Un parcours en profondeur visite récursivement un sous-arbre entier avant de passer au suivant. Trois ordres se distinguent selon quand on traite la racine relativement à ses enfants.

def prefixe(a):
    if a is None: return
    print(a.valeur, end=" ")
    prefixe(a.gauche)
    prefixe(a.droite)

def infixe(a):
    if a is None: return
    infixe(a.gauche)
    print(a.valeur, end=" ")
    infixe(a.droite)

def suffixe(a):
    if a is None: return
    suffixe(a.gauche)
    suffixe(a.droite)
    print(a.valeur, end=" ")

Parcours en largeur (BFS)

Le parcours en largeur (BFS, Breadth-First Search) visite les nœuds niveau par niveau. Il ne se programme pas naturellement par récursion : on utilise une file (FIFO).

from collections import deque

def parcours_largeur(a):
    if a is None: return
    file = deque([a])
    while file:
        n = file.popleft()
        print(n.valeur, end=" ")
        if n.gauche is not None:  file.append(n.gauche)
        if n.droite is not None:  file.append(n.droite)

# Sortie sur l'arbre exemple : 4 2 6 1 3 7

Invariant de boucle : à chaque itération, la file contient les nœuds découverts mais non encore traités, du moins profond au plus profond. Quand la file se vide, tout l'arbre a été parcouru — d'où le coût en $\mathcal{O}(n)$.

Arbre binaire de recherche : rechercher, insérer

Un arbre binaire de recherche (ABR) respecte une propriété d'ordre : pour tout nœud de valeur $v$, toutes les valeurs du sous-arbre gauche sont $< v$, et toutes celles du sous-arbre droit sont $> v$.

def rechercher(a, cle):
    if a is None:           return False
    if cle == a.valeur:     return True
    if cle <  a.valeur:     return rechercher(a.gauche, cle)
    return rechercher(a.droite, cle)

def inserer(a, cle):
    if a is None:                       return Noeud(cle)
    if cle <  a.valeur:  a.gauche = inserer(a.gauche, cle)
    elif cle > a.valeur: a.droite = inserer(a.droite, cle)
    # Si cle == a.valeur, on ne fait rien : pas de doublons dans cet ABR.
    return a

À chaque étape, on élimine la moitié des descendants encore à explorer. Si l'arbre est équilibré (hauteur $\Theta(\log n)$), le coût de rechercher et inserer est en $\mathcal{O}(\log n)$ — c'est l'intérêt majeur de la structure. On peut voir un ABR équilibré comme un annuaire trié vivant : la recherche d'un nom y obéit au même principe que la recherche dichotomique dans un dictionnaire papier — on ouvre au milieu, puis on choisit la moitié gauche ou droite selon l'ordre alphabétique.

Pour aller plus loin

La récursion sur les arbres se prête particulièrement bien à la preuve par induction structurelle : on démontre une propriété pour l'arbre vide (cas de base), puis pour un nœud à partir de l'hypothèse sur ses deux sous-arbres (hérédité). C'est la version arborescente du raisonnement par récurrence.