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)