Aller au contenu

Algorithmes Arbres Binaires de recherche

Les Arbres Binaires de recherche peuvent être implémentés avec la POO.

En plus du constructeur de la classe Noeud, nous allons utiliser 3 méthodes :

  • rechercher

  • inserer

  • supprimer

La méthode insrrer sera utilisée de manière successive sur les éléments d'une liste dans la méthode inserer_tout.

Définition de la classe Noeud et de son construteur⚓︎

Python
class Noeud:

    def __init__(self, v):
        self.ag = None
        self.ad = None
        self.v = v

Dans le code qui suit les lignes des codes des méthodes ont été mélangées. Il faut les remettre dans l'ordre.

Rechercher

Python
        if v < self.v:

        if self.v == v:

    def rechercher(self, v):

                return False

           return True

        ''' Renvoie True si v est une étiquette de l'arbre, False sinon'''

        else:

                return False

            if self.ag == None:

                return self.ad.rechercher(v)

            else:

                return self.ag.rechercher(v)

            if self.ad == None:

            else:

Inserer

Seule une partie du code de la méthdoe inserer a été retrouvée. Le reste est a écrire.

Python
...
        elif v < self.v:
            if self.ag == None:
                self.ag = Noeud(v)
            else:
                self.ag.inserer(v)
...

Pour permettre un ajout de noeuds par lot, nous utlisons la méthode inserer_tout

Python
    def inserer_tout(self, liste_noeud):
        for n in liste_noeud:
            self.inserer(n)

Ainsi pour représenter un ABR avec les noeuds 15,17,21,10,8,7 et 25, nous écrivons.

Python
    arbre = Noeud(15)
    arbre.inserer_tout([17,21,10,8,7,25])

Supprimer

Pour la méthode supprimer tout est à écrire

Extra

Le code fonctionne mais ne vérifie jamais si la condition d'unicité des clés est respectée pour les ABR. Écrire un supplément dans le code qui ajoute cette vérification.