Lycée Moulay ABDELLAH 2TSI & MP
Centre de CPGE –Safi - Informatique
Année2019/2020
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.
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.
1
Lycée Moulay ABDELLAH 2TSI & MP
Centre de CPGE –Safi - Informatique
Année2019/2020
Suppression d'un élément
L’opération dépend du nombre de fils du nœud à supprimer.
Cas 1 : le nœud à supprimer n’a pas de fils, c’est une feuille. Il suffit de décrocher le nœud de l’arbre, c’est-à-
dire de l’enlever en modifiant le lien du père, si il existe, vers ce fils. Si le père n’existe pas l’arbre devient
l’arbre vide.
Cas 2 : le nœud à supprimer a un fils et un seul. Le nœud est décroché de l’arbre comme dans le cas 1. Il est
remplacé par son fils unique dans le nœud père, si ce père existe. Sinon l’arbre est réduit au fils unique du
nœud supprimé.
2
Lycée Moulay ABDELLAH 2TSI & MP
Centre de CPGE –Safi - Informatique
Année2019/2020
Cas 3 : L’élément à supprimer a deux fils : on le remplace par son successeur qui est toujours le minimum de
ses descendants droits.
Notez que le prédécesseur peut également être utilisé (nœud de clé maximum dans le sous-arbre
gauche du nœud).
