Aller au contenu

Algorithmes Arbres Binaires de Recherche (ABR)

Les Arbres Binaires de Recherche (ABR, BST en anglais) sont des arbres binaires qui possèdent les propriétés suivantes :

  • Toutes les Ă©tiquettes de des noeuds du sous-arbre gauche sont infĂ©rieures Ă  l'Ă©tiquette de la racine.
  • Toutes les Ă©tiquettes de des noeuds du sous-arbre droit sont supĂ©rieures Ă  l'Ă©tiquette de la racine.
  • Les sous-arbres gauche et droit sont eux mĂŞme des ABR.

ILs peuvent être implémentés avec la POO.

En plus du constructeur de la classe Noeud, nous avons besoin de 3 méthodes :

  • rechercher(v) : qui retourne true si v est l'une des Ă©tiquettes de l'ABR, false sinon.

  • inserer(v) : qui insère un nouveau noeud d'Ă©tiquette v dans l'ABR, en le plaçant Ă  un endroit (non forcĂ©ment unique) qui respecte le maintient des propriĂ©tĂ©s des ABR.

  • supprimer(v) : qui supprime un noeud le noeud trouvĂ© d'Ă©tiquette v en reconstruisant un ABR. Il y a plusieurs choses Ă  rĂ©flĂ©chir pour implĂ©menter cette mĂ©thode...

  • Enfin, La mĂ©thode inserer 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
1
2
3
4
5
6
class Noeud:

    def __init__(self, v):
        self.ag = None
        self.ad = None
        self.v = v
Ainsi la classe Noeud permet de créer un arbre, l'arbre est le noeud racine.

Méthode rechercher⚓︎

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

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
        else:
                return self.ag.rechercher(v)
                return False
        if v < self.v:
            return self.ad.rechercher(v)
        if self.ad == None:
    def rechercher(self, v):

        ''' Renvoie True si v est une Ă©tiquette de l'arbre, False sinon'''
           return True
                return False
            else:
        if self.v == v:
            if self.ag == None:

Méthode inserer⚓︎

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

Python
1
2
3
4
5
6
7
...
        if 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
1
2
3
    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
1
2
    arbre = Noeud(15)
    arbre.inserer_tout([17,21,10,8,7,25])

Méthode 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.