Algorithmes sur les arbres

Numérique et sciences informatiques

donnees

Algorithmes sur les arbres :

Parcourir un arbre, c’est ordonner la liste des noeuds et feuilles de celui-ci en vue d’effectuer un certain traitement (par exemple imprimer la liste des étiquettes de cet arbre). On distingue au moins 4 types de parcours :

  • Le parcours préfixe (parcours en profondeur)
  • Le parcours suffixe (parcours en profondeur)
  • Le parcours infixe (parcours en profondeur)
  • Le parcours hiérarchique(parcours en largeur)
Arbre
Arbre T

Ballade autour de l'arbre

On se balade autour de l’arbre en suivant les pointillés dans l’ordre des numéros indiqués :

Première définition des trois parcours

Arbre
Arbre T

A partir de ce contour, on définit trois parcours des sommets de l’arbre :

  1. l’ordre préfixe : on liste chaque sommet la première fois qu’on le rencontre dans la balade.
  2. l’ordre suffixe : on liste chaque sommet la dernière fois qu’on le rencontre.
  3. l’ordre infixe : on liste chaque sommet ayant un fils gauche la seconde fois qu’on le voit et chaquesommet sans fils gauche la première fois qu’on le voit.

Ce qui donne ici : . . .

Voir une solution

Pour tester les différents parcours, nous allons utiliser la classe Noeud et la classe Arbrebin vu au précedant chapitre et le module Digraph en ligne pour vérifier et visualiser les résultats. 

from graphviz import Digraph

class Noeud():
    """Représente un noeud dans un arbre binaire
    - Propriétés :
        * valeur : valeur du noeud
        * gauche : noeud gauche ou None
        * droit  : noeud droit ou None
    - Méthodes   :
        * est_feuille()            : renvoie True ou False
        * cree_fils_gauche(valeur) : ajoute un fils de valeur valeur
        * cree_fils_droit(valeur)  : ajoute un fils de valeur valeur
        * __repr__()               : affichage d'un noeud
        * insere(cle)              : insere un noeud avec la valeur cle"""
    
    def __repr__(self):
        """la méthode __repr__ définit ce qui sera affiché
        lorsqu'on tapera l'objet dans Jupyter ou un terminal
        Ici, on affiche juste la valeur du noeud"""
        return str(f"## {self.valeur} ##")
    
    def __init__(self,valeur):
        self.valeur = valeur
        self.gauche = None
        self.droit = None
        
    def est_feuille(self):
        return self.gauche == None and self.droit == None
    
    def cree_fils_gauche(self,valeur):
        self.gauche = Noeud(valeur)
        return self.gauche
    
    def cree_fils_droit(self,valeur):
        self.droit = Noeud(valeur)
        return self.droit
    
    def insere(self, cle):
        if cle < self.valeur :
            if self.gauche == None :
                self.gauche = Noeud(cle)
            else :
                self.gauche.insere(cle)
        elif cle > self.valeur :
            if self.droit == None :
                self.droit = Noeud(cle)
            else :
                self.droit.insere(cle)

    
class Arbrebin:
    """Représente un objet arbre binaire
    - Propriétés : 
        * racine   : objet de type Noeud désignant la racine de l'arbre
    - Méthodes :
        * show()   : Représentation graphique de l'arbre à l'aide de graphviz
        * taille() : Renvoie la taille d'un arbre
        * hauteur(): Renvoie la hauteur d'un arbre
    """
     
    def __init__(self, nd = None):
        # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel
        self.racine = nd
    
    def importe(self, tableau):
        """Importe un arbre depuis un tableau
        ["Noeud", [S_A_G], [S_A_D]]
        [ ] désigne un arbre vide"""
        def importe_tableau(tableau):
            # Cas particuliers
            if tableau == []:
                return None
            if len(tableau) == 1:
                return Noeud(tableau[0])

            # tableau a une longueur >= 2
            nd = Noeud(tableau[0])
            nd.gauche = importe_tableau(tableau[1])
            nd.droit  = importe_tableau(tableau[2]) if len(tableau) > 2 else None
            return nd
        
        self.racine = importe_tableau(tableau)
        
    def show(self):
        """Renvoie un objet graphviz pour la visualisation graphique de l'arbre"""
        def representation(dot, noeud, aretes):
            # Ajoute la représentation du noeud à la représentation dot de l'arbre
            if noeud is not None:
                dot.node(str(id(noeud)), str(noeud.valeur))
                # Appel récursif de la fonction representation
                if noeud.gauche is not None:
                    representation(dot, noeud.gauche, aretes)
                    aretes.append((str(id(noeud)) , str(id(noeud.gauche))))
                if noeud.droit is not None:
                    representation(dot, noeud.droit, aretes)
                    aretes.append((str(id(noeud)) , str(id(noeud.droit))))
                    
        dot = Digraph(comment="Arbre binaire", format='svg')
        aretes = []
        representation(dot, self.racine, aretes)
        dot.edges(aretes)
        return dot
    
    def taille(self):
        """Renvoie la taille de l'arbre"""
        def taille_arbre(nd):
            # condition d'arrêt
            if nd is None:
                return 0
            # Appel récursif
            return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)
        
        return taille_arbre(self.racine)
    
    def hauteur(self):
        """Renvoie la hauteur de l'arbre"""
        def hauteur_arbre(nd):
            # condition d'arrêt
            if nd is None:
                return 0
            # Appel récursif
            return 1 + max(hauteur_arbre(nd.gauche) , hauteur_arbre(nd.droit))
        return hauteur_arbre(self.racine)
                  
    def parcours_prefixe(self):
        """Renvoie la liste des noeuds dans un parcours Prefixe"""
        def prefixe(noeud):
            # Condition d'arrêt
            if noeud is None:
                return []
            # Appel récursif et renvoi réponse
            # La valeur est insérée AVANT les appels
            return [noeud.valeur] + prefixe(noeud.gauche) + prefixe(noeud.droit)

        return prefixe(self.racine)

Le parcours préfixe

Le parcours préfixe consiste à parcourir l’arbre suivant l’ordre : inspection -→ fils g -→ fils d . On descend de la racine vers une feuille, puis on remonte à la racine, plusieurs fois, afin de passer par tous les noeuds de l’arbre.
Dans l’exemple qui suit, il correspond au parcours de l’arbre suivant l’ordre A - B - D - E - C - F - G :

Arbre
Arbre T
VARIABLE
T : arbre
x : noeud

DEBUT
PARCOURS-PREFIXE(T) :
  si T ≠ NIL :
    x ← T.racine
    affiche x.clé
    PARCOURS-PREFIXE(x.gauche)
    PARCOURS-PREFIXE(x.droit)
  fin si
FIN

Entrainement 1 :

A partir du code précédent, implémenter l'arbre ABCDEFG et tester la méthode parcours_prefixe().

Voir une solution

Le parcours suffixe

Dans ce mode de parcours, le noeud courant est traité après le traitement des noeuds gauche et droit. Soit parcourir l’arbre suivant l’ordre : fils g. −→ fils d. −→ Inspection.
Ainsi, si l'arbre précédent est utilisé, le parcours sera D, E, B, F, G, C, A.

Arbre
Arbre T
VARIABLE
T : arbre
x : noeud

DEBUT
PARCOURS-SUFFIXE(T) :
  si T ≠ NIL :
    x ← T.racine
    PARCOURS-SUFFIXE(x.gauche)
    PARCOURS-SUFFIXE(x.droit)
    affiche x.clé
  fin si
FIN

Entrainement 2 :

A partir de l'algorithme précédent, implémenter une méthode pour un parcours suffixe d'un arbre binaire et vérifier vos résultats.

Voir une solution

Le parcours infixe

Le parcours infixe (ou parcours symétrique) consiste à parcourir l’arbre suivant l’ordre : fils g. −→ Inspection −→ fils d. Le noeud courant est traité entre le traitement des fils gauche et droit.
Dans l’exemple précédent, le parcours sera D - B - E - A - F - C puis G.

Arbre
Arbre T
VARIABLE
T : arbre
x : noeud

DEBUT
PARCOURS-INFIXE(T) :
  si T ≠ NIL :
    x ← T.racine
    PARCOURS-INFIXE(x.gauche)
    affiche x.clé
    PARCOURS-INFIXE(x.droit)
  fin si
FIN

Entrainement 3 :

A partir de l'algorithme précédent, implémenter une méthode pour un parcours infixe d'un arbre binaire et vérifier vos résultats.

Voir une solution

Le parcours en largeur

Le parcours en largeur correspond à un parcours par niveau de noeuds de l'arbre et en général de la gauche vers la droite pour une profondeur donnée. Un niveau est un ensemble de noeuds ou de feuilles situés à la même profondeur.
Ainsi, si l'arbre de l'exemple est utilisé, le parcours sera A - B - C - D - E - F - G.

Arbre
Arbre T
VARIABLE
T : arbre
Tg : arbre
Td : arbre
x : noeud
f : file (initialement vide)

DEBUT
PARCOURS-LARGEUR(T) :
  enfiler(T.racine, f) //on place la racine dans la file
  tant que f non vide :
    x ← defiler(f)
    affiche x.clé
    si x.gauche ≠ NIL :
      Tg ← x.gauche
      enfiler(Tg.racine, f)
    fin si
    si x.droit ≠ NIL :
      Td ← x.droite
      enfiler(Td.racine, f)
    fin si
  fin tant que
FIN

Cet algorithme n'utilise pas de fonction récursive mais une file (FIFO) pour le parcours en largeur.

Entrainement 4 :

A partir de l'algorithme précédent, implémenter une méthode pour un parcours en largeur d'un arbre binaire.

Voir une solution

Entrainement 5 :

Donner les parcours prefixe, suffixe et infixe pour l'arbre ci-dessous :

Arbre
Arbre ex 5
Voir une solution

Arbres binaires de recherche

Un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque noeud possède une étiquette, telle que chaque noeud du sous-arbre gauche ait une étiquette inférieure ou égale à celle du noeud considéré, et que chaque noeud du sous-arbre droit possède une étiquette supérieure ou égale à celle-ci. Selon la mise en oeuvre de l'ABR, on pourra interdire ou non des étiquettes de valeur égale. Dans ce cours, nous supposerons que chaque étiquette est unique.

Arbre
Arbre T

Entrainement 6 :

  • Vérifiez que l'arbre ci-dessus est bien un arbre binaire de recherche.
  • Appliquez l'algorithme de parcours infixe sur l'arbre ci-dessous. Que remarquez vous ?
Voir une solution

Pour la suite, nous ajouterons une classe ABR pour les arbres binaires de recherche qui héritera des méthodes des classes Noeud et Arbrebin. 

class Abr(Arbrebin):
    """Arbre Binaire de Recherche
    Hérite de la classe Arbre binaire
    - Propriétés :
        * racine : valeur du noeud
    - Méthodes   :
        * insere : insere un noeud à la bonne place"""
    
    def __init__(self):
        """A l'initialisation, notre arbre est vide"""
        self.racine = None
        
    def insere(self, cle):
        """Insere un noeud de valeur cle

        @param :
            cle : étiquette du noeud
        """
        self.racine.insere(cle)

Ajouter aussi la methode insere à la classe Noeud. 

def insere(self, cle):
        if cle < self.valeur :
            if self.gauche == None :
                self.gauche = Noeud(cle)
            else :
                self.gauche.insere(cle)
        elif cle > self.valeur :
            if self.droit == None :
                self.droit = Noeud(cle)
            else :
                self.droit.insere(cle)

Insertion d'une clé dans un arbre binaire de recherche

L'insertion d'un noeud commence par une recherche : on cherche l'étiquette du noeud à insérer. Si on la trouve, on ne fait rien. Sinon, lorsqu'on ne peut plus descendre dans l'arbre, cela signifie qu'on a trouvé le père. On insère le noeud en comparant son étiquette à celle de son père : si elle est inférieure, le nouveau noeud sera son fils gauche ; sinon il sera son fils droit. Ainsi, chaque noeud ajouté sera une feuille.
La complexité de l'insertion est O(log(n)) dans le cas moyen et O(n) dans le pire des cas.

Entrainement 7 :

Etudier la classe Abr et tester ce programme en insérant les noeuds pour créer l'instance arbre_T de l'exemple précendant.

Recherche dans un Arbres binaires de recherche

La recherche dans un arbre binaire d'un noeud ayant une étiquette particulière est un procédé récursif. On commence par examiner la racine. Si l'étiquette de la racine est l'étiquette recherchée, l'algorithme se termine et renvoie la racine. Si l'étiquette cherchée est inférieure, alors elle est dans le sous-arbre gauche, sur lequel on effectue alors récursivement la recherche. De même, si l'étiquette recherchée est strictement supérieure à l'étiquette de la racine, la recherche continue sur le sous-arbre droit. Si on atteint une feuille dont l'étiquette n'est pas celle recherchée, on sait alors que cette étiquette n'est pas dans l'arbre. Cette opération requiert un temps en O(log(n)) dans le cas moyen, mais O(n) dans le pire des cas où l'arbre est complètement déséquilibré où chaque père a un seul fil

Entrainement 8 :

Implémenter une méthode permettant de rechercher une clé de valeur k dans un arbre binaire de recherche. Si k est bien présent dans l'arbre binaire de recherche, la méthode renvoie vrai, dans le cas contraire, elle renvoie faux

Voir une solution


Savoir faire

  • Parcours de l'arbre de différentes façons
  • Recherche et insertion d'une clé dans un arbre binaire de recherche.

Fiche de cours