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

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]]
Ici chaque arbre et sous-arbre est représenté par une liste contenant trois éléments : la racine, le SAG et le SAD.

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}}
Ici, chaque arbre et sous-arbre est un dictionnaire avec trois clés : la racine, le SAG et le SAD.

4.4. Implémentation en POO

TAD Arbre Binaire

• 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 06 ci-dessus 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 06 ci-dessus 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 06 ci-dessus donne : D-G-H-E-B-I-F-C-A

Taille d'un arbre binaire

• T(A)=0${\displaystyle T\left(A\right)=0}$ si A est un arbre vide
• sinon T(A)=1+T(sag(A))+T(sad(A))${\displaystyle T\left(A\right)=1+T\left(sag\left(A\right)\right)+T\left(sad\left(A\right)\right)}$

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

La hauteur (ou la profondeur) d'un noeud est le nombre de branches entre ce noeud et la racine de l'arbre. La hauteur d'un noeud est définit par :

• H(x)=0${\displaystyle H\left(x\right)=0}$ si x est la racine de l'arbre
• H(x)=1+H(y)${\displaystyle H\left(x\right)=1+H\left(y\right)}$ si y est le père de x

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

Exemple : Dans cet arbre, le noeud "H" est de hauteur 3.

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

Parcourt des valeurs dans l'ordre croissant

Recherche d'une valeur

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