Arbre de recherche binaire

Un arbre de recherche binaire (Binary Search Tree) est un arbre dans lequel tous les nœuds suivent les propriétés suivantes : le sous-arbre gauche d'un nœud a une clé inférieure ou égale à la clé de son nœud parent, le sous-arbre droit d'un nœud a une clé supérieure à la clé de son nœud parent, ainsi l’arbre de recherche binaire divise tous ses sous-arbres en deux segments : le sous-arbre gauche et le sous-arbre droit.

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Recherche d'une valeur dans un arbre B

La recherche d'une valeur dans un arbre implique la comparaison de la valeur entrant avec la valeur sortant des nœuds. Ici aussi, nous parcourons les nœuds de gauche à droite et finalement avec le parent. Si la valeur recherchée ne correspond à aucune des valeurs sortantes, nous renvoyons le message non trouvé, sinon le message trouvé est renvoyé.

Exemple