Cours

Introduction : les structures de données

Les arbres

Introduction

Définition

Les noeuds qui ne sont pas des feuilles sont aussi qualifiés de noeuds internes.

Exemple d'arbre ayant 7 noeuds, 4 feuilles, 6 branches et pour racine : le noeud A.

Caractéristiques

Exemple : Le HTML

Les arbres binaires

Vocabulaire

• Un arbre binaire est un arbre d'arité 2. Cela signifie que la racine et chaque noeud ne peut avoir au maximum que deux enfants. On parlera alors de sous-arbre gauche (noté SAG) et de sous-arbre droit (noté SAD). Le fils gauche est la racine du SAG tandis que le fils droit est la racine du SAD.
• Un arbre dégénéré est filiforme. Chaque noeud n'a qu'un enfant.
• Un arbre binaire localement complet est un arbre dont chaque noeud a strictement deux enfants.
• Un arbre binaire complet est un arbre localement complet avec toutes ses feuilles à la même profondeur. On dit aussi qu'il est parfaitement équilibré.

Exemple : Expressions arithmétiques

Les expressions arithmétiques sont représentables sous forme d'arbre binaire. En effet les opérateurs d'addition, de soustraction, de multiplication ou de division sont d'arité 2, c'est-à-dire qu'ils s'appliquent à deux opérandes. Les arbres binaires, par définition d'arité 2, sont donc tout désignés pour les repésenter.

Représentation d'un arbre binaire

Sous forme d'une liste

L = [A, B, C, , , G, H]

Les espaces vides dans la liste correspondent aux noeuds vides dans l'arbre binaire complet correspondant. Cette représentation repose sur la relation suivante entre les indices d'un père et de ses fils :

Sous forme de listes imbriquées

Pour l'Arbre 03, rappelé ci-dessous, on peut aussi imaginer cette structure :

L = [A, B, [C, G, H]]

Sous forme d'un dictionnaire

Reprenons toujours l'exemple de l'Arbre 03. Sa représentation sous forme de dictionnaire peut être :

D = {racine:A, sag:B, sad:{racine:C, sag:G, sad:H}}

4.4. Implémentation en POO

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

a = Noeud("A")
a.gauche = Noeud("B")
a.droit = Noeud("C")

TAD Arbre Binaire

class Arbre:
    """Implémentation de la structure de données «Arbre» en Python."""

    # creerArbre(arbre, racine) → arbre
    def __init__(self, racine=None):
        self._racine = racine    # valeur
        self._gauche = None      # Sous-arbre gauche
        self._droit = None       # Sous-arbre droit

    # estVide(arbre) → booléen
    def estVide(self):
        return self._racine is None

    # racine(arbre) → valeur
    def racine(self):
        assert not self.estVide(), "L'arbre est vide."
        return self._racine

    # sag(arbre) → arbre
    def sag(self):
        return self._gauche

    # sad(arbre) → arbre
    def sad(self):
        return self._droit

    # assembler(arbre, arbre, arbre) → arbre
    def assembler(self, sag = None, sad = None):
        assert not self.estVide(), "L'arbre est vide."
        self._gauche = sag
        self._droit = sad

    # définition de l'impression (print) de l'objet
    def __str__(self):
        return "({},{},{})".format(self._racine, self._gauche, self._droit)

    # définition de l'affichage d'appel de l'objet
    def __repr__(self):
        return "Arbre()"

    # affiche l'arbre binaire dans la console
    def afficher(self):
        if self.estVide():
            print("L'arbre est vide.")
        else:
             self._afficher(0)

    def _afficher(self, level):
        if self._droit:
            self._droit._afficher(level + 1)
        print("{}{}".format(' ' * 4 * level, self._racine))
        if self._gauche:
            self._gauche._afficher(level + 1)

• Les attributs _racine, _gauche et _droit, et sont précédés d'un underscore _ ce qui signifie qu'ils sont privés. Le programmeur signale ainsi que l'utilisateur ne doit pas intéragir directement avec ces attributs mais doit passer par les seules méthodes qu'il a proposées. Cela permet de sécuriser les usages.
• Python ne permet pas de rendre réellement privé un attribut ou une méthode, comme c'est le cas en C ou en Java. L'underscore _ en préfixe n'est qu'une indication non-bloquante.
• Des méthodes d'affichage __str__(), __repr__() et afficher() sont également définie pour vous permettent d'afficher l'arbre et ainsi vérifier son contenu.

Algorithmes sur les arbres binaires

Parcours en largeur d'un arbre binaire

Le parcours en largeur d'un arbre binaire consiste à parcourir l'arbre, niveau par niveau en partant de la racine en en lisant les noeuds de gauche à droite.
Le parcours en largeur de l'arbre ci-dessus donne : A-B-C-D-E-F-G-H-I

Pseudo code : L'algorithme de parcours en largeur utilise une file.

Parcours en profondeur d'un arbre binaire

Lors du parcours en profondeur d'un arbre, nous passons sur chaque noeud à trois reprises, avant son fils gauche, entre ses deux fils et après son fils droit.

• Lorsqu'on traite un noeud dès sa première visite (ronds rouges en cliquant sur l'image), nous obtenons l'ordre du parcours en profondeur préfixe des noeuds. Algorithmiquement, cela revient à faire :
  [racine] + appel récursif sur SAG + appel récursif sur SAD
  Le parcours en profondeur préfixe de l'arbre binaire 01 ci-contre donne : A-B-D-E-G-H-C-F-I

• Lorsqu'on traite un noeud lors de sa deuxième visite (carrés bleus), nous obtenons l'ordre du parcours en profondeur infixe des noeud. Algorithmiquement, cela revient à faire :
  appel récursif sur SAG + [racine] + appel récursif sur SAD
  Le parcours en profondeur préfixe de l'arbre binaire 01 ci-contre donne : D-B-G-E-H-A-C-I-F

• Lorsqu'on traite un noeud lors de sa troisième visite (triangles verts), nous obtenons l'ordre du parcours en profondeur postfixe des noeud. Algorithmiquement, cela revient à faire :
  appel récursif sur SAG + appel récursif sur SAD + [racine]
  Le parcours en profondeur postfixe de l'arbre binaire 01 ci- donne : D-G-H-E-B-I-F-C-A

Taille d'un arbre binaire

• 𝑇(A) = 0 si A est un arbre vide
• sinon 𝑇(A) = 1 + 𝑇(sag(A)) + 𝑇(sad(A))

Pseudo code : Algorithme pour déterminer la taille d'un arbre.

a ← arbreBinaire
FONCTION taille(a):
    SI a EST vide:
        RETOURNER 0
    SINON:
        t ← 1
        SI a A sag:
            t ← t + taille(sag)
        SI a A sad:
            t ← t + taille(sad)
        RETOURNER t

Hauteur d'un noeud

Attention : La convention utilisée ici est : Le niveau de la racine vaut 1 tandis que sa hauteur (ou sa profondeur) valent 0.

Pour l'instant nos arbres ne sont pas triés (il ne s'agit pas encore d'arbre binaire de recherche). Ainsi, pour savoir où se situe un noeud et en déduire sa hauteur (ou sa profondeur), il faut parcourir tout l'arbre à sa recherche. L'idée ici va être de descendre dans l'arbre, de manière récursive, en partant de la racine (hauteur 0, niveau 1). Pour chaque noeud rencontré, on va enregistrer dans un dictionnaire sa valeur et son niveau.

Pseudo code :

dicoN ← dictionnaire vide
a ← arbre binaire
h ← 0
FONCTION hauteursNoeuds(a, dicoN, h):
    AJOUTER à dicoN, le couple (racine(a), h)
    SI a A un sag :
        dicoN ← hauteursNoeuds(sag(a), dicoN, h+1)
    SI a A un sad :
        dicoN ← hauteursNoeuds(sad(a), dicoN, h+1)
    RETOURNER dicoN

Hauteur d'un arbre

Les arbres binaires de recherche (ABR)

• Les valeurs du SAG doivent être inférieures à celle de la racine.
• Les valeurs du SAD doivent être supérieures à celle de la racine.

Algorithmes sur les arbres binaires de recherche

Parcours des valeurs dans l'ordre croissant

Recherche d'une valeur

a ← arbre binaire de recherche
x ← valeur à rechercher

FONCTION rechercher(a, x) :
    SI x = racine(a) ALORS
        REPONDRE vrai
    SINON SI x < racine(a) ALORS
        SI a A un sag ALORS
            recherche(sag(a), x)
        SINON REPONDRE faux
    SINON
        SI a A un sad ALORS
            recherche(sad(a), x)
        SINON REPONDRE faux

Insertion d'une valeur

Recherche du minimum et du maximum

Aller plus loin !

Vérifier un ABR

Suppression d'une valeur d'un ABR

1. Rajouter un attribut _parent dans le constructeur __init__ de la classe Arbre pour mémoriser le père.
2. Modifier, lorsque c'est nécessaire, les méthodes écrites précédemment.
3. Écrire une méthode nombreFils(self, x) qui donne le nombre de fils (0, 1 ou 2) du Noeud x dans l'arbre.
4. Écrire les trois méthodes correspondant au troix cas expliqué précédement : supprimeFeuille(self, x), supprimeUnFils(self,x) et supprimeDeuxFils(self, x).

Équilibrer un ABR