Arbre binaire de recherche
A étant un arbre binaire, nous désignons par :
val(A), la valeur de la racine de l'arbre,
max(A), la valeur maximale contenue dans A,
min(A), la valeur minimale contenue dans A,
filsgauche(A), le sous-arbre enraciné comme fils gauche de la racine de A,
filsdroit(A), le sous-arbre enraciné comme fils droit de la racine de A.
Remarque :
Notez que les définitions max et min supposent un ordre total sur les données contenues dans l'arbre.
Définition :
Un arbre binaire de recherche (ABR) est un arbre binaire possédant les propriétés suivantes :
Le type de l'information contenue par un nœud possède un ordre total,
À chaque nœud n de l'arbre, la relation max(filsgauche(A))< val(A) <min(filsdroit(A).