Algorithmes sur les arbres

Dans ce classeur, nous allons mettre en oeuvre les algorithmes vus en cours. Nous partirons de deux classes :

  • Noeud permettant de décrire la structure d'un noeud dans un arbre binaire
  • Arbrebin qui est l'arbre proprement dit. Il se caractérise par
    • sa racine qui est un Noeud
    • des méthodes pour peupler cet arbre et l'afficher sous forme graphique
    • des méthodes que vous allez construire pour mettre le cours en pratique

Découverte des classes de base

Validez les cellules suivantes et analysez bien la structure proposée.

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() 
        * __repr__() : affichage d'un noeud"""
    
    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):
        """Renvoie un booleen selon que le noeud est une feuille"""
        return self.gauche is None and self.droit is None
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
    """
    
    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

Regardons notre classe en action : Nous allons recréer l'arbre exemple du cours.

# On crée la structure d'arbre à l'aide d'un tableau  ["Noeud", [S_A_G], [S_A_D]]
arbre_liste = ["A",
                ["B", ["C",[],["E"]], 
                      ["D"]],
                ["F", ["G", ["I"]], 
                      ["H",["J", ["K"]]] ],
              ]
# On crée une instance vide de notre arbre
arbre = Arbrebin()
# On importe le tableau ci-dessus
arbre.importe(arbre_liste)
# On visualise l'arbre graphiquement
arbre.show()

Taille et Hauteur d'un arbre

Nous allons ajouter nos premières méthodes personelles à la classe Arbrebin. Commençons par la taille de l'arbre. Nous avons conçu un algorithme récursif en cours se basant sur le principe que la taille d'un arbre est égal à 1 + la taille du Sous Arbre Gauche + la taille du Sous Arbre Droit. Voici une implémentation de cet algorithme dans la classe Arbrebin, elle vous servira de modèle pour les autres méthodes que vous aurez à implémenter dans ce TD.

Vous remarquerez que pour éviter la multiplication des méthodes, nous créons une fonction locale taille_arbre qui n'est visible que dans la méthode taille. C'est cette fonction qui implémente en réalité l'algorithme, la méthode n'étant là que pour invoquer la fonction taille_arbre sur la racine de l'arbre.

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
    """
     
    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)
# Utilisation sur l'arbre exemple :

# On instancie notre arbre
arbre = Arbrebin()
arbre.importe(arbre_liste)

# On invique la méthode taille
arbre.taille()

A vous de jouer

En utilisant le même modèle que pour la taille, vous allez implémenter la méthode hauteur déterminant la hauteur de l'arbre. Vous complèterez donc la cellule ci-dessous et vérifierez qu'elle passe bien le test.

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
    """
    
    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):
            # YOUR CODE HERE
            raise NotImplementedError()
        
        return hauteur_arbre(self.racine)
# Cellule de tests
arbre = Arbrebin()
arbre.importe(arbre_liste)

assert arbre.hauteur() == 5
# On indique la méthode taille

Parcours en profondeur

Voici la méthode permettant le parcours en profondeur préfixe.

  1. Ajoutez-la à la classe Arbrebin
  2. Vérifiez son bon fonctionnement
  3. Implémentez de même les parcours suffixe et infixe.
  4. Validez votre travail grâce à la cellule de tests.

Vous ferez attention de choisir les mêmes noms de méthodes que dans la cellule de test pour passer ces derniers avec succès.

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)
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
    """
    
    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)
    
    # YOUR CODE HERE
    raise NotImplementedError()
# Cellule de tests
arbre = Arbrebin()
arbre.importe(arbre_liste)

assert arbre.parcours_prefixe() == ['A', 'B', 'C', 'E', 'D', 'F', 'G', 'I', 'H', 'J', 'K']
assert arbre.parcours_suffixe() == ['E', 'C', 'D', 'B', 'I', 'G', 'K', 'J', 'H', 'F', 'A']
assert arbre.parcours_infixe() == ['C', 'E', 'B', 'D', 'A', 'I', 'G', 'F', 'K', 'J', 'H']

Parcours en largeur

Pour finir, ajoutez à la classe Arbrebin la méthode parcours_largeur()

Vous vérifierez votre travail avec la cellule de tests. Il pourra être utile de revoir l'implémentation des files FIFO avec un tableau python.

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
    """
    
    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)
# YOUR CODE HERE
raise NotImplementedError()
# Cellule de tests
arbre = Arbrebin()
arbre.importe(arbre_liste)

assert arbre.parcours_largeur() == ['A', 'B', 'F', 'C', 'D', 'G', 'H', 'E', 'I', 'J', 'K']

Arbres Binaires de Recherche

Il est temps de passer aux arbres binaires de recherche. Un ABR est un arbre binaire particulier. Il est donc souhaitable que toutes les méthodes définies dans la classe Arbrebin soient aussi disponibles dans la classe Abr que nous allons créer.

Faire un copier/coller de ces dernières serait fort maladroit. La structure d'objet nous offre un mécanisme particulièrement intéressant ici : la notion d'héritage. En faisant hériter notre classe Abr de la classe Arbrebin, toutes les méthodes d'Arbrebin seront disponibles pour Abr et nous n'aurons juste qu'à nous soucier des méthodes spécifiques aux arbres binaires de recherche.

Insertion

Afin de pouvoir commencer à manipuler nos ABR, nous allons implémenter la méthode insere. Complétez la classe ci-dessous

class Abr(Arbrebin):
    """Arbre Binaire de Recherche
    Hérite de la classe Arbre binaire"""
    
    def __init__(self):
        """A l'initialisation, notre arbre est vide"""
        self.racine = None
    
    def insere(self, valeur):
        """Insère valeur dans note ABR
        paramètre : valeur à insérer"""
        def insere_noeud(nd, valeur):
            # insère la valeur dans nd
            # renvoie le noeud complété
            # YOUR CODE HERE
            raise NotImplementedError()
        
        self.racine = insere_noeud(self.racine, valeur)
    

Si votre méthode insere fonctionne, la cellule ci-dessous doit construire un ABR en utilisant l'arbre d'exemple.

Une fois votre classe au point, changez l'ordre de parcours de l'arbre de départ pour observer l'impact sur l'ABR construit. Vous constarerez alors que l'ABR est loin d'être unique : tout dépend de l'ordre d'insertion des valeurs. Un de ces ABR sera plus efficace pour la recherche. Trouvez-vous lequel ?

# Vous pouvez modifier le contenu de cette cellule !
# On crée un ABR vide
mon_abr = Abr()
# On insère les valeurs de notre arbre de départ dans un certain ordre
for v in arbre.parcours_prefixe():
    mon_abr.insere(v)
mon_abr.show()
# Cellule de test
mon_abr = Abr()
for v in arbre.parcours_prefixe():
    mon_abr.insere(v)

# les méthodes de Arbrebin sont disponibles pour Abr sans avoir eu a les recréer
# c'est la magie de l'héritage

assert mon_abr.hauteur() == 9

recherche

Pour la suite de notre activité, nous changerons un peu et jouerons avec les termes d'une suite célèbre. Peut-être la reconnaîtrez-vous ! Commmençons par construire notre ABR. Que constatez-vous ? Cet arbre est-il intéressant pour rechercher une valeur ?

suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]
suite_abr = Abr()
for v in suite:
    suite_abr.insere(v)
suite_abr.show()

Pour résoudre ce problème, nos allons utiliser une technique surprenante : appeler l'aléatoire à la rescousse ! Vous allez constater qu'en mélangeant notre suite, la situation s'améliore très sensiblement !

from random import shuffle
suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]
shuffle(suite)
suite_abr = Abr()
for v in suite:
    suite_abr.insere(v)
suite_abr.show()

Voilà qui est nettement mieux !!

Vous allez maintenant pour terminer cette activité implémenter la méthode recherche qui prend une valeur en paramètre et renvoie un booleen selon que la valeur est dans l'arbre ou non.

class Abr(Arbrebin):
    """Arbre Binaire de Recherche
    Hérite de la classe Arbre binaire"""
    
    def __init__(self):
        """A l'initialisation, notre arbre est vide"""
        self.racine = None
    
# YOUR CODE HERE
raise NotImplementedError()
suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]
shuffle(suite)
suite_abr = Abr()
for v in suite:
    suite_abr.insere(v)
assert suite_abr.recherche(233)
assert not suite_abr.recherche(317)