Les arbres binaires

1. Terminologie de base

Un arbre est une structure de données qui organise l'information de façon hiérarchique. On le retrouve partout : arborescence de fichiers, arbre généalogique, arbre syntaxique d'une expression, taxonomie en biologie… Un arbre binaire est un arbre dans lequel chaque nœud possède au plus deux fils : un fils gauche et un fils droit.

2. Hauteur d'un arbre et profondeur d'un nœud

Deux mesures décrivent la « forme verticale » d'un arbre.

• La profondeur d'un nœud est le nombre d'arêtes du chemin qui le relie à la racine. La racine est à la profondeur 0.
• La hauteur d'un arbre est la profondeur maximale, c'est-à-dire la longueur du plus long chemin de la racine jusqu'à une feuille. Par convention, l'arbre vide a pour hauteur −1 et un arbre réduit à sa racine a pour hauteur 0.

Pour un arbre binaire de hauteur h, le nombre de nœuds n vérifie l'encadrement :

La borne inférieure correspond à un arbre filiforme (chaque nœud n'a qu'un fils), la borne supérieure à un arbre parfait (tous les niveaux sont pleins). On en déduit, pour un arbre équilibré à n nœuds, une hauteur de l'ordre de log₂ n.

# Hauteur d'un arbre (convention : arbre vide -> -1)
def hauteur(a):
    if a is None:              # arbre vide
        return -1
    return 1 + max(hauteur(a[1]), hauteur(a[2]))

La hauteur se calcule donc « de bas en haut » : on suppose connaître la hauteur des deux sous-arbres, on prend la plus grande et on ajoute 1 pour le niveau de la racine.

3. Représentation et implémentation

Le programme demande de définir un arbre binaire à l'aide d'une liste. La représentation la plus directe en Python suit la définition récursive : un nœud est une liste à trois cases.

# Un arbre = None (vide)  OU  [valeur, sous_arbre_gauche, sous_arbre_droit]
def feuille(v):
    return [v, None, None]

def noeud(v, g, d):
    return [v, g, d]

# Exemple :        4
#                /   \
#               2     6
arbre = noeud(4, feuille(2), feuille(6))
# arbre = [4, [2, None, None], [6, None, None]]

On compte facilement les nœuds avec la même structure récursive :

def nb_noeuds(a):
    if a is None:
        return 0
    return 1 + nb_noeuds(a[1]) + nb_noeuds(a[2])

def nb_feuilles(a):
    if a is None:
        return 0
    if a[1] is None and a[2] is None:   # aucun fils
        return 1
    return nb_feuilles(a[1]) + nb_feuilles(a[2])

Une autre représentation, utile pour les arbres complets, range les valeurs dans une seule liste où le fils gauche du nœud d'indice i est en 2i+1 et le fils droit en 2i+2. Cette représentation « par tableau » est précisément celle des tas (section 7).

4. Parcours en profondeur (DFS)

Parcourir un arbre, c'est visiter chacun de ses nœuds une et une seule fois. Les parcours en profondeur explorent un sous-arbre entièrement avant de passer au suivant. Ils diffèrent par le moment où l'on traite la racine par rapport à ses sous-arbres.

def prefixe(a):
    if a is None:
        return []
    return [a[0]] + prefixe(a[1]) + prefixe(a[2])

def infixe(a):
    if a is None:
        return []
    return infixe(a[1]) + [a[0]] + infixe(a[2])

def postfixe(a):
    if a is None:
        return []
    return postfixe(a[1]) + postfixe(a[2]) + [a[0]]

5. Parcours en largeur (BFS)

Le parcours en largeur visite les nœuds niveau par niveau, de gauche à droite. On ne peut plus utiliser la récursivité naturelle : on s'appuie sur une file (FIFO, « premier entré, premier sorti »). On enfile la racine, puis on défile un nœud, on le traite et on enfile ses fils.

from collections import deque

def largeur(a):
    if a is None:
        return []
    file = deque([a])         # file initialisée avec la racine
    ordre = []
    while file:
        n = file.popleft()    # on défile (FIFO)
        ordre.append(n[0])
        if n[1] is not None:
            file.append(n[1])  # on enfile le fils gauche
        if n[2] is not None:
            file.append(n[2])  # puis le fils droit
    return ordre

6. L'arbre binaire de recherche (ABR)

Un arbre binaire de recherche est un arbre binaire qui respecte, en chaque nœud, la propriété d'ordre suivante :

Cette invariant rend la recherche très efficace : à chaque nœud, on élimine la moitié de l'arbre, exactement comme dans une recherche dichotomique. Le coût d'une recherche, d'une insertion ou d'une suppression est en \(O(h)\), donc \(O(\log n)\) si l'arbre est équilibré, mais \(O(n)\) dans le pire des cas (arbre filiforme).

def recherche(a, x):
    if a is None:
        return False
    if x == a[0]:
        return True
    if x < a[0]:
        return recherche(a[1], x)   # on descend à gauche
    else:
        return recherche(a[2], x)   # on descend à droite

def inserer(a, x):
    if a is None:
        return [x, None, None]      # on crée une nouvelle feuille
    if x < a[0]:
        a[1] = inserer(a[1], x)
    elif x > a[0]:
        a[2] = inserer(a[2], x)
    return a                        # x déjà présent : on ne fait rien

Construire un ABR par insertions successives, puis appliquer le parcours infixe, fournit une méthode de tri : c'est le principe du tri par arbre.

7. Le tas (heap)

Un tas est un arbre binaire complet (tous les niveaux remplis sauf éventuellement le dernier, rempli de gauche à droite) vérifiant une propriété de tas. Dans un tas-max, la valeur de chaque nœud est supérieure ou égale à celles de ses fils ; la racine contient donc le maximum.

# Insertion dans un tas-max (remontée / "percolate up")
def inserer_tas(t, x):
    t.append(x)               # on ajoute en dernière position
    i = len(t) - 1
    while i > 0 and t[(i-1)//2] < t[i]:
        pere = (i-1)//2
        t[i], t[pere] = t[pere], t[i]   # on échange avec le père
        i = pere
    return t

Le tas est la structure idéale d'une file de priorité : insertion et extraction du maximum coûtent \(O(\log n)\). Il est au cœur du tri par tas (heapsort).

8. Récapitulatif

CPGE MP / PSI · Informatique — Les arbres binaires