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 chaque sommet 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écédant 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
    
    
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):
	        # 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:
	                dot.edge(str(id(noeud)), str(id(noeud.gauche)), label='gauche')
	                representation(dot, noeud.gauche)
	            if noeud.droit is not None:
	                dot.edge(str(id(noeud)), str(id(noeud.droit)), label='droit')
	                representation(dot, noeud.droit)

	    dot = Digraph(comment="Arbre binaire", format='svg')
	    dot.attr('node', shape='circle')  # Définit la forme des nœuds
	    dot.attr('edge', arrowhead='vee')  # Définit le style des flèches
	    dot.attr(rankdir='TB')  # Orientation de haut en bas

	    representation(dot, self.racine)
	    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

Entraînement 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

Entraînement 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

Entraînement 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.

Entraînement 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

Entraînement 5 :

Donner les parcours préfixe, suffixe et infixe pour l'arbre ci-dessous :

Arbre
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.

Arbre
Exemples

L'arbre 3 n'est pas un ABR à cause de la feuille 9, qui fait partie du sous-arbre gauche de 8 sans lui être inférieure.
L'arbre 4 n'est pas un ABR à cause de la feuille 32, qui fait partie du sous-arbre gauche de 30 sans lui être inférieure.

Entraînement 6 :

Arbre
Arbre T
  • 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

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

L'insertion d'un nœud dans un ABR est un processus qui commence par une recherche pour trouver la position correcte où insérer le nouveau nœud. Voici les étapes détaillées :

  1. Recherche de la position :
    • On commence par comparer l'étiquette du nœud à insérer avec celle de la racine.
    • Si l'étiquette est inférieure, on descend dans le sous-arbre gauche.
    • Si l'étiquette est supérieure, on descend dans le sous-arbre droit.
    • On continue ce processus jusqu'à ce qu'on atteigne une position où il n'y a plus de nœud (une feuille).
  2. Insertion du nœud :
    • Une fois la position trouvée, on insère le nouveau nœud à cet endroit.
    • Si l'étiquette du nouveau nœud est inférieure à celle du nœud parent, il devient le fils gauche.
    • Si elle est supérieure, il devient le fils droit.
  3. Complexité de l'opération :
    • Cas moyen : L'insertion prend un temps proportionnel à O(log(n)), où n est le nombre de nœuds dans l'arbre.
    • Pire des cas : Si l'arbre est complètement déséquilibré (chaque nœud n'a qu'un seul enfant), l'insertion peut prendre un temps proportionnel à O(n).

Pour la suite, nous ajouterons une classe ABR à notre programme python 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 : insère 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 méthode 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)

Entraînement 7 :

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

http://www.lumni.fr/video/arbres-binaires-de-recherche

Recherche dans un Arbres binaires de recherche

La recherche d'un nœud avec une étiquette spécifique dans un arbre binaire de recherche est un processus récursif. Voici comment cela fonctionne :

  1. Examen de la racine : On commence par comparer l'étiquette recherchée avec celle de la racine de l'arbre.
    • Si l'étiquette de la racine est celle que l'on cherche, la recherche est terminée et on renvoie la racine.
    • Si l'étiquette recherchée est inférieure à celle de la racine, on continue la recherche dans le sous-arbre gauche.
    • Si l'étiquette recherchée est supérieure à celle de la racine, on continue la recherche dans le sous-arbre droit.
  2. Recherche récursive : On applique le même processus récursivement sur le sous-arbre approprié (gauche ou droit).
  3. Cas d'une feuille : Si on atteint une feuille (un nœud sans enfants) et que son étiquette n'est pas celle recherchée, cela signifie que l'étiquette n'est pas présente dans l'arbre.
Complexité de l'Opération
  • Cas moyen : La recherche dans un ABR bien équilibré prend un temps proportionnel à O(log(n)), où n est le nombre de nœuds dans l'arbre.
  • Pire des cas : Si l'arbre est complètement déséquilibré (chaque nœud n'a qu'un seul enfant), la recherche peut prendre un temps proportionnel à O(n).

Entraînement 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