Arbre de recherche
Un arbre de recherche est un arbre
utilisé pour stocker des données d'un domaine ordonnée de manière à ce que la donnée
la plus petite (selon l'ordre du domaine) est stockée dans la feuille
la plus a gauche, et la donnée la plus grande dans la feuille la plus
à droite. Un tel arbre est souvent utilisé pour implémenter le type abstrait dictionnaire lorsque le domaine est ordonné.
Il y a deux variations possibles :
- Soit chaque sommet de l'arbre contient une information stockée.
Dans ce cas, l'arbre est souvent binaire et le sous arbre de
gauche d'une sommet contient des données strictement inférieures à
celle stockée dans le sommet, et le sous arbre de droite d'un sommet
contient des données strictement supérieures à celle stockée dans le
sommet.
- Soit c'est uniquement dans les feuilles que sont stockées
les informations. Dans ce cas, les sommets intérieurs contiennent pour
chaque sous arbre une indication de l'intervalle des informations
stockées dans ce sous arbre, permettant ainsi de choisir le bon sous
arbre pour retrouver une information.
Arbre binaire de recherche