Arbres binaires de recherche

Définition

Un arbre binaire de recherche (ABR) (binary search treeBST) est un arbre binaire tel que :

  • les clefs des nœuds doivent être ordonnables (il doit exister entre elles une relation d’ordre)
  • pour chacun de ses nœuds:
    • chaque nœud du sous-arbre gauche a une clé inférieure (ou égale) à celle du nœud considéré,
    • chaque nœud du sous-arbre droit possède une clé supérieure (ou égale) à celle-ci

Remarque : selon la mise en œuvre de l’ABR, on pourra interdire ou non des clés de valeurs égales.

Lorsqu’on ajoute un nœud à un ABR, il devient une feuille de l’arbre.

Activité : validité d'un ABR

Soit l’arbre binaire suivant :

S’agit-il d’un ABR (justifier) ?

 

Définitions spécifiques

Arbre binaire parfait : arbre dont tous les niveaux sont remplis et dont toutes les feuilles sont à la même profondeur (le dernier niveau est complètement occupé).

Arbre binaire complet : tous les niveaux de l’arbre sont remplis, sauf éventuellement le dernier, sur lequel les nœuds (feuilles) sont à gauche.

Arbre binaire équilibré : tous les chemins de la racine aux feuilles ont la même longueur.

Arbre binaire dégénéré : chacun de ses nœuds a au plus un fils.

 

Interface

Soit l’ABR suivant, qui servira comme support pour illustrer la suite :

Télécharger la version PDF

 

 

Plus petite (grande) valeur

Pour accéder à la clé la plus petite dans un ABR, il suffit de descendre sur le fils gauche autant que possible. Le dernier nœud visité qui n’a pas de fils gauche porte la valeur la plus petite de l’arbre.

Activité : valeurs extrêmes d'un ABR
Sur l’arbre donné en exemple, tracer les chemins permettant d’accéder à la plus petite valeur de ses clés, puis à la plus grande valeur.

 

Tri des clés

Pour obtenir la suite ordonnée de toutes les clés d’un ABR, il suffit de le parcourir l’arbre dans l’ordre infixe.

Exemple :

 

Activité : tri des clés d'un ABR
Vérifier que l’arbre donné en exemple est bien un ABR en parcourant ses clés dans l’ordre infixe.

 

Recherche

Comme son nom l’indique, un ABR est spécifiquement adapté à la recherche d’enregistrements dont les clés sont données par les nœuds de l’arbre.

Exemple : recherche de la clé de valeur 6

Un ABR permet de rechercher rapidement (faible coût temporel).

Activité : coût de la recherche

Arbre dégénéré (ou filiforme)

Supprimer des nœuds à l’arbre donné en exemple pour former un arbre dégénéré.

 

En déduire l’ordre de complexité de l’algorithme de recherche d’une valeur parmi ses clés.

Arbre équilibré

Transformer l’arbre donné en exemple en arbre équilibré en supprimant le moins de nœuds possible.

 

À l’aide de l’encadrement de la hauteur d’un arbre binaire, estimer l’ordre de complexité de l’algorithme de recherche d’une valeur parmi ses nœuds.

 

 

Insertion

Pour insérer un nœud dans un arbre, on recherche la feuille dont la clé est la plus proche de celle du nœud à insérer (comme pour l’algorithme de recherche). On ajoute le nœud à gauche si sa clé est inférieure à celle de la feuille, et à droite dans le cas contraire.

Exemple : ajout d’un nœud dont la clé vaut 5 :

Dans le cas d’un ABR qui n’autorise pas les clés multiples, il faudra empêcher l’insertion d’un nœud dont la clé est déjà dans l’arbre.

Activité : insertions
Sur l’arbre fourni en exemple, ajouter un nœud de clé égale à 33, puis un autre de clé égale à 95.

 

 

Suppression

L’opération dépend du nombre de fils du nœud à supprimer.

Cas n°1 : le nœud à supprimer est une feuille

  • On cherche le père du nœud à supprimer,
  • On supprimer le lien père-fils.

Exemple : suppression du nœud 5

Cas n°2 : le nœud à supprimer a un unique fils

  • On recherche le père du nœud à supprimer,
  • On redirige le lien père-fils vers le fils (unique) du nœud à supprimer.

Exemple : suppression du nœud 6

Cas n°3 : le nœud à supprimer a deux fils

  • On recherche le nœud de sa branche de gauche ayant la plus grande valeur,
    comme c’est le plus grand de cette branche, il n’a pas de fils droit (voir Plus grande valeur)
  • On rompt le lien père-fils, (comme dans le cas n°2 !)
  • Et on remplace la valeur du nœud à supprimer par celle du nœud décroché.

Exemple : suppression du nœud 11

Remarque : alternativement, on peut décrocher le nœud ayant la plus petite valeur de sa branche de droite.

Activité : valeurs extrêmes d'un ABR
Sur l’arbre donné en exemple, supprimer les nœuds 29, 71 et 55.

 

 

Implémentation

On se propose d’implémenter l’interface présentée plus haut en langage Python.

Pour cela, on utilisera, comme des modules (sans les modifier !), les programmes suivant :

 

Implémenter une classe Arbre_br(Arbre Binaire de Recherche), héritant de la classe Arbre_b(Arbre Binaire).
Implémenter, sous forme de méthodes de la classe Arbre_br, les opérations de l’interface évoquée plus haut :
  • min()Noeud_b
  • max()Noeud_b
CORRECTION
def min(self):
    """ Renvoie la plus petite valeur de l'arbre """
    def m(n):
        while n.g is not None:
            return m(n.g)
        return n
    return m(self.racine)


def max(self):
    """ Renvoie la plus grande valeur de l'arbre """
    def m(n):
        while n.d is not None:
            return m(n.d)
        return n
    return m(self.racine)
  • chercher(v)Noeud_b
CORRECTION
def chercher(self, v):
    """ Renvoie le Noeud de valeur v
        None si aucun noeud n'a cette valeur
    """
    n = self.racine
    while n is not None:
        if v > n.v:
            n = n.d
        elif v < n.v:
            n = n.g
        else:
            return n
  • verifier()bool (méthode récursive, d’après la définition d’un ABR)
Aide
  • La classe Arbre_brn’étant pas récursive (contrairement à la classe Noeud_b), pour coder une méthode de l’objet Arbre_br, il faudra passer par une fonction auxiliaire (récursive) définie comme sous-fonction de la méthode verifier().
  • Afin de bien identifier la validité d’une branche de racine n, il faut identifier les 5 conditions qui doivent être vérifiées :
    • 1 portant sur la valeur du nœud  n
    • 2 portant sur la valeur des fils de n
    • 2 portant sur la validité des branches partant des fils de n
CORRECTION
def verif(self):
    """ Renvoie True si self est bien un ABR """

    def verif_noeud(n, mini, maxi):
        g = d = mini < n.v < maxi

        if n.d is not None:
            d = verif_noeud(n.d, n.v, maxi) and n.d.v > n.v

        if n.g is not None:
            g = verif_noeud(n.g, mini, n.v) and n.g.v < n.v

        return g and d

    return verif_noeud(self.racine, mini = -inf, maxi = inf)
  • inserer(v)
CORRECTION
def inserer(self, v):
    """ Insère un nouveau Noeud de valeur v dans l'arbre
        (version itérative)
    """
    if self.racine is None:
        self.racine = Noeud_b(v)

    else:
        n = self.racine
        while n is not None:
            if v < n.v:
                if n.g is None:
                    n.g = Noeud_b(v)
                    return
                n = n.g

            elif v > n.v:
                if n.d is None:
                    n.d = Noeud_b(v)
                    return
                n = n.d

            else:
                return # clé déjà dans l'arbre
  • supprimer(v)
CORRECTION
def supprimer(self, v):
    """ Supprime le Noeud de valeur v dans l'arbre
        (s'il existe)
    """
    n = self.racine
    p = None
    continuer = True
    while continuer and n is not None:
        if v > n.v:
            p = n
            n = n.d
        elif v < n.v:
            p = n
            n = n.g
        else:
            continuer = False # Pour terminer la boucle

    if p is not None and n is not None:
        if n.d is None and n.g is None: #Feuille
            if n.v < p.v:
                p.g = None
            else:
                p.d = None
                
        elif n.d is None or n.g is None:  # Fils unique
            if n.v < p.v:
                if n.d is not None:
                    p.g = n.d
                else:
                    p.g = n.g
            else:
                if n.d is not None:
                    p.d = n.d
                else:
                    p.d = n.g
                    
        else:
            m = n.g
            p = n
            while m.d is not None:
                p = m
                m = m.d
            if m.v < p.v:
                p.g = m.g
            else:
                p.d = m.g
            n.v = m.v

 

 

Sources :
https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche
http://pageperso.lif.univ-mrs.fr/~francois.denis/algoMPCI/chap1.pdf

 

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code