Les arbres binaires de recherche

1. Définitions:

Définition 1:

Un arbre binaire a est un arbre binaire de recherche si, pour tout nœud nd de a, les contenus des nœuds du sous-arbre gauche de nd sont strictement inférieurs au contenu de nd, et que les contenus des nœuds du sous-arbre droit de nd sont strictement supérieurs au contenu de nd.

Définition 2:

a est un arbre binaire de recherche si :
1- a est un arbre binaire
2- Le parcours infixé de a donne une liste ordonnée.

                                                       
                                                                           Fig 1 : arbre binaire de recherche 
2. La recherche d'une clé dans un arbre binaire de recherche:
Pour chercher si un élément val figure dans un arbre A, on commence par comparer val au contenu inf de la racine de A. S’il y a égalité, on a trouvé la réponse; sinon il y a deux cas selon que val est inférieur au contenu de a ou  val est supérieur au contenu de a. S'il est inferieur alors, alors val figure peut-être dans le sous-arbre gauche (fg) de A. On élimine ainsi de la recherche tous les nœuds du sous-arbre droit. et s'il superieur alors val figure peut-être dans le sous-arbre droit (fd) de A. On élimine ainsi de la recherche tous les nœuds du sous-arbre gauche. 
Version récursive :


Version itérative: