Arbre binaire de recherche
Un arbre binaire de recherche est un arbre dans lequel chaque nœud est supérieur à son fils gauche et inférieur à son fils droit et il n’y a pas de nœuds égaux
Un arbre binaire de recherche est intéressant puisqu’il est toujours possible de connaître dans quelle branche de l’arbre se trouve un élément et de proche en proche le localiser dans l’arbre.
Les propriétés ci-dessus de l'arbre binaire de recherche permettent de classer les clés afin que les opérations telles que recherche, minimum et maximum puissent être effectuées rapidement. S'il n'y a pas d'ordre, il se peut que nous devions comparer chaque clé pour rechercher une clé donnée.
Rechercher un élément
Pour rechercher une clé donnée dans L'arbre binaire de recherche, nous la comparons d'abord avec racine, si la clé est présente à racine, nous retournons racine. Si la clé est supérieure à la clé de la racine, on recommence pour le sous-arbre droit du noeud racine. Sinon, le sous-arbre gauche.
Algorithme rechercher(Noeud , cle)
Si (Noeud = Null) alors
Retourne Faux
Sinon Si (Noeud.val = cle ) alors
Retourne Vrai
Sinon Si (cle < Noeud.val ) alors
Retourne rechercher(Noeud.gauche, cle)
Sinon
Retourne rechercher(Noeud.droit, cle)
Fin SI
FIN
class Noeud:
def __init__(self, cle):
self.gauche = None
self.droit = None
self.val = cle
def rechercher(Noeud, cle):
assert Noeud != None
if Noeud is None:
return False
elif Noeud.val == cle:
return True
if Noeud.val < cle:
return rechercher(Noeud.droit, cle)
return rechercher(Noeud.gauche, cle)
Insertion d'un élément
Une nouvelle clé est toujours inséré dans la feuille. On commence à chercher une valeur à partir de la racine jusqu'à ce qu'on atteigne une feuille. Une fois qu'une feuille est trouvée, le nouveau nœud est ajouté en tant qu'enfant de la feuille.
Algorithme Inserer(Noeud , cle)
Si (Noeud = null) alors
« ajouter un nœud pour cle à cet endroit»
Si(val > Noeud.val)
Insérer (Noeud.droit, val)
Sinon
Insérer (Noeud.gauche, val)
FINSI
FIN
class Noeud:
def __init__(self, key):
self.gauche = None
self.droit = None
self.val = key
def inserer(noeud,cle):
if noeud is None:
noeud = Noeud(cle)
else:
if noeud.val < cle:
if noeud.droit is None:
noeud.droit = Noeud(cle)
else:
inserer(noeud.droit, cle)
else:
if noeud.gauche is None:
noeud.gauche = Noeud(cle)
else:
inserer(noeud.gauche, cle)
