Correction : Arbres binaires de recherche

Construire un ABR

Questions sur la méthode

1. Cette méthode est récursive comme on peut le voir à chaque return ( appel de la fonction à elle-même ).
2. Les préconditions ( = conditions sur les paramètres ) sont les suivantes : self doit être un ABR et v une valeur ayant une relation d'ordre avec les éléments déjà présent dans self
3. L'élément n'est pas inséré car aucune des deux conditions n'est réalisée ( strictement plus grand ou plus petit )
4. Les postconditions ( = condition vérifié par le(s) résultat(s) renvoyé(s) ) : cette méthode renvoie un ABR.

Construction d'un ABR

Pour construire les deux arbres le code suivant peut être utilisé :

				
liste1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
ABR1 = ABR(None)
for elmt in liste1:
	ABR1 = ABR1.inserer(elmt)
ABR1.dessine()
			

1. l'ABR correspond à une liste chaînée, que l'on appelle aussi ici "arbre peigne".
2. Dans le pire des cas (un peigne...), la complexité est en O(n); dans le meilleur des cas, en O(log(n))
3. L'ABR2 est plus équilibré que l'ABR1 ( il est même presque parfait ).
4. Pour l'ABR2 on a choisit l'élément central de la liste triée ( la médiane ) comme racine.

Recherche dans un ABR

Fonction de test

	
def test_recherche():
    liste = [5, 2, 1, 3, 4, 8, 7, 6, 9]
    arbrerech = ABR(None)
    for a in liste:
        arbrerech = arbrerech.inserer(a)
    if arbrerech.rechercher_rec(5) and arbrerech.rechercher_rec(8) and arbrerech.rechercher_rec(4) and not arbrerech.rechercher_rec(18):
        print('ca marche')
    else:
        print('il y a au moins une erreur')    			
			

Fonction de recherche itérative

	
def rechercher_it(abr ,v):
    while abr is not None and v != abr.valeur:
        if v < abr.valeur:
            abr = abr.filsgauche
        else:
            abr = abr.filsdroit

     if abr is None:
         return False
     else:
         return True
         
     # ou encore mieux :
     # return abr is not None # renvoie donc 'True' si l'arbre n'est pas vide, donc que la valeur a été trouvée; 'False' sinon ( = valeur pas trouvée )
			

Fonction de recherche récursive

	
def rechercher_rec(abr, v):
    if v == abr.valeur:
        return True
    else:
        if v < abr.valeur and abr.filsgauche != None:
            return abr.filsgauche.rechercher_rec(v)
        elif v > abr.valeur and abr.filsdroit != None:
            return abr.filsdroit.rechercher_rec(v)
        else:
            return False			
			

Application

Construire l'arbre

Il faut adapter la méthode d'insertion pour qu'elle stocke un tableau ['Nom_pays', 'PIB', 'Rang'] comme étiquette de chaque noeud.

Le test à faire se fera alors sur le 3^ème élément de ces tableaux ( indice = 2 ); il faut prendre garde que dans un fichier .csv, toutes les données sont de type str : pour faire la comparaison, il faut donc au préalable transtyper ce 3^ème élément en int ( la comparaison en Python de deux chaînes se fait selon l'ordre lexicographique de ses caractères; ainsi, on aurait par exemple : '236' < '32' !...)

	
import csv
from classe_arbre import *

liste_payspib = []

with open("fichiers/pib.csv", 'r', encoding='utf-8') as f:
    lecteur = csv.reader(f, delimiter=',')
    for ligne in lecteur :
        liste_payspib.append(ligne)			
			

class ABR(Arbre):
	
    def insererPays(self, liste):
        if self.valeur==None:
            return ABR(liste,None,None)

        if self.valeur!=None:

            if int(liste[2]) < int(self.valeur[2]):
                if self.filsgauche==None:
                    return ABR(self.valeur,ABR(liste,None,None),self.filsdroit)
                else:
                    return ABR(self.valeur,self.filsgauche.insererPays(liste),self.filsdroit)

            elif int(liste[2]) > int(self.valeur[2]):
                if self.filsdroit==None:
                    return ABR(self.valeur,self.filsgauche,ABR(liste,None,None))
                else:
                    return ABR(self.valeur,self.filsgauche,self.filsdroit.insererPays(liste))
			
			
a = ABR(None)
for i in range(len(liste_payspib)):
	a = a.insererPays(liste_payspib[i])
	
a.dessinePays()
								
			

Rechercher le 111^ème pays

	
class ABR(Arbre):
    def insererPays(self, liste):
        ...
        # code ci-dessus
        
    def recherchePays(self,r):
        while self !=None and r!=int(self.valeur[2]):
            if r<int(self.valeur[2]):
                self=self.filsgauche
            else:
                self=self.filsdroit

        if self==None:
            return False
        else:
            return self.valeur
            
print(a.recherchePays(111))
			

Comparaison avec une liste triée...IMPORTANT

1. L'algorithme qui permet de trouver un élément dans une liste triée est la recherche par DICHOTOMIE
2. Pour une liste de longueur n, la complexité de cet algorithme est O(log₂(n))
3. L'ordre de grandeur de la hauteur d'un ABR contenant n données est log₂(n)
4. La complexité de la recherche dans un ABR est donc O(log₂(n))

1. La complexité de l'insertion d'un élément dans une liste triée est en O(n)
2. La complexité de l'insertion d'un élément dans un ABR est en O(log₂(n))