Les arbres

Introduction aux arbres

Un arbre est une structure de données hiérarchique composée de nœuds reliés par des arêtes. Mathématiquement, un arbre est un graphe connexe et acyclique (sans cycle).

On retrouve des arbres dans de nombreuses situations :

• l’arborescence d’un système de fichiers ;
• un arbre généalogique ;
• la structure d’un document HTML (DOM) ;
• l’organisation hiérarchique d’une entreprise.

Vocabulaire des arbres

Nœuds particuliers

Dans un arbre, on distingue trois types de nœuds selon leur position :

• la racine : unique nœud sans parent, situé au sommet de l’arbre ;
• les feuilles : nœuds sans fils, situés aux extrémités ;
• les nœuds internes : nœuds ayant au moins un fils.

Relations entre nœuds

Les relations s’expriment avec un vocabulaire familial :

• le père (ou parent) d’un nœud est le nœud directement au-dessus de lui ;
• les fils (ou enfants) d’un nœud sont les nœuds directement en dessous.

Caractéristiques chiffrées

Plusieurs mesures permettent de caractériser la structure :

• le degré d’un nœud est son nombre de fils ;
• la profondeur d’un nœud est le nombre d’arêtes entre la racine et ce nœud (la racine a une profondeur de 0) ;
• la hauteur d’un arbre est la profondeur maximale de ses feuilles (un arbre vide a une hauteur de \(-1\), un arbre réduit à sa racine a une hauteur de 0) ;
• la taille d’un arbre est son nombre total de nœuds.

Exercice : analyse d’un arbre

Soit l’arbre suivant :

        A
      / | \
     B  C   D
    / \  \
   E   F  G
  / \
 H   I

1. Identifier les nœuds particuliers :

   • Racine : …
   • Feuilles : …
   • Nœuds internes : …

2. Identifier les relations :

   • Père de E : …
   • Fils de B : …

3. Calculer les caractéristiques :

   • Degré de A : …
   • Degré de B : …
   • Profondeur de G : …
   • Profondeur de I : …
   • Hauteur : …
   • Taille : …

Arbres binaires

Un arbre binaire est un arbre où chaque nœud possède au plus deux fils, appelés fils gauche et fils droit.

C’est une structure définie de manière récursive. Un arbre binaire peut être :

• vide (aucun nœud) ;
• non vide : composé d’une racine et de deux sous-arbres (gauche et droit), eux-mêmes des arbres binaires.

Interface d’un arbre binaire

L’interface décrit les opérations disponibles sur un arbre binaire a, indépendamment de la façon dont il est programmé ; l’implémentation ci-dessous les réalise avec une classe Arbre dont les attributs sont valeur, gauche et droit, l’arbre vide étant représenté par None.

Précondition : les opérations racine, gauche, droit et est_feuille ne s’appliquent qu’à un arbre non vide. Une autre implémentation (par exemple une liste de listes, ou une classe avec un objet « arbre vide ») garderait la même interface : les algorithmes écrits avec ces opérations resteraient valables.

Implémentation en Python

class Arbre:

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

    def __repr__(self):
        if self.gauche is None and self.droit is None:
            return str(self.valeur)
        return str(self.valeur) + "-(" + str(self.gauche) + "," + str(self.droit) + ")"

    def est_vide(self):
        return False

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

Remarque : dans cette implémentation, un arbre vide est représenté par None, et un arbre non vide par un objet Arbre. La méthode est_vide() renvoie toujours False car elle n’est appelée que sur un objet existant.

Exercice : construction d’un arbre binaire

1. Écrire le code Python pour construire l’arbre binaire suivant :

      5
     / \
    3   8
   / \ / \
  1  4 7  9

2. Que renvoient les expressions suivantes ?
   • a.valeur
   • a.gauche.valeur
   • a.droit.gauche.valeur
   • a.gauche.est_feuille()
   • a.gauche.gauche.est_feuille()

a = Arbre(5,
        Arbre(3, Arbre(1), Arbre(4)),
        Arbre(8, Arbre(7), Arbre(9)))

Algorithmes récursifs sur les arbres

La structure récursive des arbres binaires permet d’écrire des algorithmes élégants. Pour chaque fonction, on traitera d’abord le cas de base (arbre vide), puis l’étape de récurrence.

Exercice : implémentation de la taille

Compléter la fonction taille(arbre) :

def taille(arbre):
    if arbre is None:
        return ...
    return ...

def taille(arbre):
    if arbre is None:
        return 0
    return 1 + taille(arbre.gauche) + taille(arbre.droit)

Exercice : implémentation de la hauteur

Compléter la fonction hauteur(arbre) :

def hauteur(arbre):
    if arbre is None:
        return ...
    return ...

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

Exercice : nombre de feuilles

Écrire une fonction nb_feuilles(arbre) qui renvoie le nombre de feuilles.

def nb_feuilles(arbre):
    if arbre is None:
        return 0
    if arbre.gauche is None and arbre.droit is None:
        return 1
    return nb_feuilles(arbre.gauche) + nb_feuilles(arbre.droit)

Parcours d’arbres binaires

Un parcours permet de visiter tous les nœuds d’un arbre dans un certain ordre.

Parcours en profondeur (DFS)

On distingue trois types de parcours selon l’ordre de traitement de la racine :

• préfixe : nœud, gauche, droit — on traite le nœud avant ses fils ;
• infixe : gauche, nœud, droit — on traite le nœud entre ses fils ;
• suffixe : gauche, droit, nœud — on traite le nœud après ses fils.

def prefixe(arbre):
    if arbre is not None:
        print(arbre.valeur, end=' ')
        prefixe(arbre.gauche)
        prefixe(arbre.droit)

def infixe(arbre):
    if arbre is not None:
        infixe(arbre.gauche)
        print(arbre.valeur, end=' ')
        infixe(arbre.droit)

def suffixe(arbre):
    if arbre is not None:
        suffixe(arbre.gauche)
        suffixe(arbre.droit)
        print(arbre.valeur, end=' ')

Exercice : parcours en profondeur

Donner l’ordre de visite pour chaque parcours de l’arbre suivant :

      5
     / \
    3   8
   / \ / \
  1  4 7  9

• Préfixe : …
• Infixe : …
• Suffixe : …

Parcours en largeur (BFS)

Le parcours en largeur visite les nœuds niveau par niveau, de gauche à droite. Il utilise une file (FIFO : First In, First Out).

def largeur(arbre):
    if arbre is None:
        return
    file = [arbre]
    while file:
        noeud = file.pop(0)
        print(noeud.valeur, end=' ')
        if noeud.gauche is not None:
            file.append(noeud.gauche)
        if noeud.droit is not None:
            file.append(noeud.droit)

Exercice : trace du parcours en largeur

Compléter la trace d’exécution du parcours en largeur sur l’arbre précédent :

Arbres binaires de recherche (ABR)

Un ABR est un arbre binaire tel que pour tout nœud :

• toutes les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du nœud ;
• toutes les valeurs du sous-arbre droit sont strictement supérieures à la valeur du nœud.

Une propriété fondamentale est que le parcours infixe d’un ABR donne les valeurs dans l’ordre croissant.

Exercice : reconnaissance d’ABR

Parmi ces arbres, lesquels sont des ABR ? Justifier.

Arbre 1 :

      6
     / \
    4   9
   / \ / \
  2  5 7  10

Arbre 2 :

      6
     / \
    4   9
   / \    \
  2   8   10

Arbre 3 :

      6
     / \
    3   8
   / \    \
  1   4    9

Recherche dans un ABR

def rechercher(arbre, x):
    if arbre is None:
        return False
    if x == arbre.valeur:
        return True
    elif x < arbre.valeur:
        return rechercher(arbre.gauche, x)
    else:
        return rechercher(arbre.droit, x)

Complexité

• Cas moyen (arbre équilibré) : \(O(\log n)\) — on divise par 2 à chaque étape.
• Pire cas (arbre dégénéré) : \(O(n)\) — l’arbre est comme une liste.

Exercice : insertion dans un ABR

Écrire la fonction inserer(arbre, x) qui insère l’élément x dans l’ABR arbre.

def inserer(arbre, x):
    if arbre is None:
        return Arbre(x)
    if x < arbre.valeur:
        arbre.gauche = inserer(arbre.gauche, x)
    elif x > arbre.valeur:
        arbre.droit = inserer(arbre.droit, x)
    return arbre

Exercice : construction d’ABR

On insère successivement les valeurs 5, 2, 8, 1, 3, 7, 9 dans un ABR initialement vide.

1. Dessiner l’ABR obtenu après chaque insertion.

2. Quelle serait la forme de l’arbre si on insérait les valeurs dans l’ordre 1, 2, 3, 5, 7, 8, 9 ?

3. Comparer les hauteurs des deux arbres et expliquer la conséquence sur les performances.