Chapitre 4: Arbres

Dans ce chapitre, on présente une nouvelle structure de donnée: les arbres qui sont particulièrement adaptés à la représentation des données hiérarchiques comme un arbre généalogique ou encore le DOM d'une page html.

Vocabulaire

Arbre

Un arbre est constitué de nœuds reliés par des arêtes. Souvent les nœuds ont une valeur: l'étiquette.

Racine d'un arbre enraciné

Un arbre enraciné (ou arborescence) possède à sa base une racine auxquels sont reliés d'autres nœuds qui sont ses descendants.

Un nœud situé à l'extrémité de l'arbre qui n'a donc pas de descendants est une feuille.

Profondeur d'un nœud

La profondeur d'un nœud est la distance, c'est-à-dire, le nombre d'arêtes de la racine au nœud.

Hauteur d'un arbre

La hauteur d'un arbre est la plus grande profondeur d'une feuille de l'arbre.

Taille d'un arbre

La taille d'un arbre est son nombre de nœuds.

Arbres binaires

Définition

Arbre binaire

Les arbres binaires sont un type d'arbres particuliers pour lesquels chaque nœud a au plus deux fils.

Implémentation récursive

Comme chaque nœud d'un arbre binaire a au plus deux enfants, on définit les sous arbres gauche et sous arbre droit d'un nœud.

[CC-BY-SA David Roche]{.cite-source}

On peut ainsi définir une classe ArbreBinaire récursive comme suit:

# nécessaire pour pouvoir annoter le type de la classe
from __future__ import annotations


class ArbreBinaire:
    """Structure de donnée d'arbre binaire"""

    def __init__(self, étiquette: str, gauche: ArbreBinaire, droit: ArbreBinaire):
        self.étiquette = étiquette
        self.gauche = gauche
        self.droit = droit

Parcours d'un arbre binaire

Il existe diverses façons de parcourir les nœuds d'un arbre.

Le parcours en largeur d'abord: les nœuds sont parcourus comme si on lisait l'arbre, de haut en bas et de gauche à droite.

Le parcours en profondeur d'abord: on explore complétement le sous-arbre gauche avant de commencer l'exploration du droit. Il existe trois façons de faire:

• Parcours préfixe ou préordre (NGD): on visite d'abord le nœud, puis son sous-arbre gauche, puis son sous-arbre droit.
• Parcours infixe ou en ordre (GND): on visite d'abord le sous-arbre gauche, puis le nœud, puis le sous-arbre droit.
• Parcours postfixe ou en postordre (GDN): on visite d'abord le sous-arbre gauche, puis le sous-arbre droit, et enfin le nœud.

Arbres binaires de recherche

Définition

Arbre binaire de recherche

Il s'agit d'un arbre binaire dans lequel toutes les valeurs dans le sous-arbre gauche d'un nœud sont inférieures à la valeur à la racine de l'arbre et toutes les valeurs dans le sous-arbre droit d'un nœud sont supérieures ou égales à la valeur à la racine de l'arbre.

Implémentation en P.O.O.

Dans un arbre binaire de recherche, les nœuds ne peuvent pas être placés n'importe comment et doivent respecter l'ordre entre les sous arbres et le nœud: $G<N<D$.

On peut créer une classe ABR semblable à la classe ArbreBinaire, mais en lui ajoutant une méthode insérer pour ajouter l'élément à sa place dans l'arbre binaire de recherche.

On peut ainsi définir une classe ArbreBinaire récursive comme suit:

# nécessaire pour pouvoir annoter le type de la classe
from __future__ import annotations


class ABR:
    """Structure de donnée d'arbre binaire de recherche"""

    def __init__(self, étiquette: int, gauche: ABR, droit: ABR):
        self.étiquette = étiquette
        self.gauche = gauche
        self.droit = droit

    def insérer(self, valeur):
        """Insère une valeur à sa place dans l'arbre"""

        # si la valeur est inférieure on l'insère à gauche
        if valeur < self.étiquette:
            # si il y a pas de noeud à gauche, on l'insère
            if self.gauche is None:
                self.gauche = ABR(valeur, None, None)
            # sinon on fait un appel récursif sur le sous arbre gauche
            else:
                self.gauche.insérer(valeur)
        else:
            if self.droit is None:
                self.droit = ABR(valeur, None, None)
            else:
                self.droit.insérer(valeur)

Intérêt des arbres binaires de recherche

Le caractère trié d'un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, ce que nous verrons dans la partie algorithmique.