Les arbres binaires

Comment utiliser cette page

Cette page suit toujours le même plan : le vocabulaire, la définition, un exemple unique (repris dans toute la page pour ne pas avoir à en retenir plusieurs), l'implémentation en Python avec une classe Noeud, la hauteur, la taille, un aperçu du codage avec un arbre, puis la complexité.

1. Vocabulaire à connaître avant de commencer

Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.

2. Qu'est-ce qu'un arbre ? Définition récursive

Beaucoup d'informations peuvent être organisées sous la forme d'un arbre : un arbre généalogique, une arborescence de fichiers sur un ordinateur, ou encore la structure d'une phrase. Voici un exemple simple, avec un nœud racine qui a trois fils :

Un arbre avec une racine et 3 fils : c'est un exemple d'arbre n-aire (ici, chaque nœud peut avoir jusqu'à 3 fils). « Fils 1 », « Fils 2 » et « Fils 3 » sont ici tous des feuilles, car ils n'ont eux-mêmes aucun fils.

3. L'arbre binaire : le cas particulier étudié dans cette fiche

Un arbre binaire est un arbre n-aire avec n = 2 : chaque nœud a donc au plus deux fils, appelés le fils gauche et le fils droit. Le sous-arbre qui part du fils gauche est appelé le sous-arbre gauche ; celui qui part du fils droit, le sous-arbre droit.

4. L'exemple utilisé dans toute la suite de cette page

Le même arbre binaire, avec 8 nœuds nommés A, G, D, Gp, O, P, Dg et Dd, est repris dans toutes les sections qui suivent : construction avec la classe Noeud, calcul de la hauteur, puis calcul de la taille.

Cet arbre n'est pas symétrique : sa branche gauche (A → G → Gp → O ou P) descend d'un niveau de plus que sa branche droite (A → D → Dg ou Dd). Ce choix est volontaire : il permet de bien voir, plus loin, que la hauteur d'un arbre dépend de sa branche la plus profonde, pas de la moyenne de ses branches.

5. Implémentation en Python avec une classe Noeud

5.1 — Les opérations primitives

5.2 — La classe Noeud

On représente un arbre binaire avec une classe Noeud : chaque objet Noeud a un attribut racine (la valeur du nœud), un attribut gauche (le sous-arbre gauche, ou None s'il est vide) et un attribut droit (le sous-arbre droit, ou None s'il est vide).

class Noeud:
    def __init__(self, racine):
        self.gauche = None
        self.racine = racine
        self.droit = None

    def __repr__(self):
        return f'{self.racine}({str(self.gauche)},{str(self.droit)})'

5.3 — Construire pas à pas l'arbre de l'exemple

1. Créer les feuilles O et P.
2. Créer Gp, puis relier O comme son fils gauche et P comme son fils droit.
3. Créer G, puis relier Gp comme son fils gauche (son fils droit reste vide, None).
4. Créer les feuilles Dg et Dd.
5. Créer D, puis relier Dg comme son fils gauche et Dd comme son fils droit.
6. Créer la racine A, puis relier G comme son fils gauche et D comme son fils droit.

O = Noeud('O')P = Noeud('P')Gp = Noeud('Gp')Gp.gauche = OGp.droit = PG = Noeud('G')G.gauche = Gp          # G.droit reste vide (None)Dg = Noeud('Dg')Dd = Noeud('Dd')D = Noeud('D')D.gauche = DgD.droit = DdA = Noeud('A')A.gauche = GA.droit = D

Pour se donner une idée de l'arbre construit, on peut afficher A directement (c'est la méthode __repr__ qui est invoquée) :

>>> A
A(G(Gp(O(None,None),P(None,None)),None),D(Dg(None,None),Dd(None,None)))

On retrouve, en le lisant, exactement la notation parenthésée de l'arbre : chaque nœud est suivi de ses deux sous-arbres entre parenthèses, dans l'ordre gauche puis droit, et None représente un sous-arbre vide.

6. La hauteur d'un arbre binaire

6.1 — Trace pas à pas sur l'exemple

On calcule la hauteur en partant des feuilles (les plus faciles, car leurs deux sous-arbres sont vides) et en remontant vers la racine A.

La hauteur de l'arbre complet, hauteur(A), vaut donc 3.

La hauteur de chaque nœud est indiquée par le petit badge vert. On voit que le nœud G vaut 2 (et pas 1 + hauteur de Gp + 1) : c'est bien 1 + max(hauteur(Gp), hauteur(vide)) = 1 + max(1, -1) = 2.

6.2 — Le code Python

def hauteur(self):
    if self is None:
        return -1
    else:
        hauteur_gauche = self.gauche.hauteur() if self.gauche else -1
        hauteur_droit = self.droit.hauteur() if self.droit else -1
        return 1 + max(hauteur_gauche, hauteur_droit)

7. La taille d'un arbre binaire

7.1 — Trace pas à pas sur le même exemple

La taille de l'arbre complet, taille(A), vaut donc 8 : c'est bien le nombre total de nœuds (A, G, D, Gp, O, P, Dg, Dd).

7.2 — Le code Python

def taille(self):
    if self is None:
        return 0
    else:
        taille_gauche = self.gauche.taille() if self.gauche else 0
        taille_droit = self.droit.taille() if self.droit else 0
        return 1 + taille_gauche + taille_droit

Cette méthode a exactement la même structure que hauteur : un cas de base pour l'arbre vide (0 au lieu de -1), et un appel récursif sur chaque sous-arbre existant.

8. Aperçu : coder des éléments avec un arbre binaire

On peut utiliser la structure d'un arbre binaire pour associer un code fait de 0 et de 1 à chaque feuille : « 0 » quand on emprunte le sous-arbre gauche, « 1 » quand on emprunte le sous-arbre droit. C'est ce principe, avec des arbres plus grands et plus élaborés, qui sera étudié en détail avec le codage de Huffman dans la séquence 9. Voici une version simplifiée, avec 4 fruits codés sur 2 bits chacun :

8.1 — Trace pas à pas du décodage de "01100011"

Le message décodé est donc : Poire, Banane, Pomme, Orange.

8.2 — Le code Python

def decoder(arbre, code):
    """Décode une chaîne de 0 et de 1 en suivant l'arbre, et renvoie
    la liste des feuilles rencontrées (dans l'ordre)."""
    resultat = []
    noeud = arbre
    for bit in code:
        noeud = noeud.gauche if bit == '0' else noeud.droit
        if noeud.gauche is None and noeud.droit is None:
            # noeud est une feuille : on a fini un symbole
            resultat.append(noeud.racine)
            noeud = arbre
    return resultat

9. Récapitulatif des complexités

n désigne ici le nombre de nœuds de l'arbre (sa taille). Un arbre binaire de n nœuds a une hauteur minimale égale au nombre de chiffres de n écrit en base 2 (par exemple, un arbre de 197 nœuds a une hauteur minimale de 8, car 197 s'écrit avec 8 chiffres en base deux) ; sa hauteur peut cependant être bien plus grande si l'arbre n'est pas équilibré.

10. Points clés à retenir

• Un arbre binaire est soit vide, soit un nœud avec un sous-arbre gauche et un sous-arbre droit, qui sont eux-mêmes des arbres binaires (définition récursive).
• Un nœud sans fils est une feuille ; un sous-arbre vide se représente en Python par None.
• La classe Noeud a trois attributs : gauche, racine, droit.
• La hauteur d'un arbre vide est -1 ; la hauteur d'un nœud est 1 + max(hauteur gauche, hauteur droit).
• La taille d'un arbre vide est 0 ; la taille d'un nœud est 1 + taille gauche + taille droit.
• Presque tous les algorithmes sur les arbres binaires sont récursifs, avec le même schéma : un cas de base pour l'arbre vide, puis un calcul qui combine les résultats obtenus sur le sous-arbre gauche et sur le sous-arbre droit.
• Un arbre binaire peut aussi servir à coder des données (chemin gauche/droite = suite de 0 et de 1), comme dans le codage de Huffman.