Arbre Binaire de Recherche (ABR) ou Binary Search Tree (BST)
Publié le 23/04/2023
Extrait du document
«
Arbre Binaire de Recherche (ABR)
ou
Binary Search Tree (BST)
Un arbre binaire de recherche est un cas particulier d'arbre binaire dont les clés des noeuds
composant l'arbre possède une relation d’ordre totale, c'est-à-dire qu'il doit exister une manière de
dire si un élément est plus grand ou plus petit qu'un autre.
Par exemple, on peut trier des nombres par valeur ou des personnes par ordre alphabétique de leur
nom de famille.
Définition :
Un arbre binaire de recherche est un arbre binaire muni d’une
relation d’ordre sur ses clés telles qu’en tout noeud v de l’arbre :
● les clés du sous-arbre gauche du noeud v sont inférieures à
la clé de v,
● les clés du sous-arbre droit du noeud v sont supérieures à la
clé de v.
N'importe quelle collection de n éléments appartenant à un ensemble ordonné peut être stockée et
classée à l'intérieur d'un arbre binaire de n noeuds.
Dans ce cas, les noeuds contiennent les
éléments et les liens père-fils permettent de gérer l'ordre entre ces éléments.
Construction d'un ABR par ajouts successifs en feuille :
Le premier élément inséré dans l'arbre devient la racine.
Ensuite, il suffit de mettre à gauche les
éléments plus petits et à droite les éléments plus grands.
Traduire la séquence {18,10,35,6,14,30,8,11,16,33}
sous la forme d’un ABR
Traduire la séquence {14,10,35,6,11,30,8,16,33,18}
sous la forme d’un ABR
Il peut y avoir plusieurs ABRs représentant un même ensemble de données : {6,8,10,11,14,16,18,30,33,35}
Recherche d’une clé k dans un arbre binaire de recherche
Si k est bien présent dans l'arbre binaire de recherche, l'algorithme renvoie vrai, dans le cas contraire, il renvoie
faux.
La recherche dans un arbre binaire d'un nœud ayant une clé particulière est un procédé récursif.
PRINCIPE
On commence par examiner la racine.
Si sa clé est la clé recherchée, l'algorithme se termine et renvoie vraie.
Si elle est strictement inférieure, alors elle est dans le sous-arbre gauche, sur lequel on effectue alors
récursivement la recherche.
De même si la clé recherchée est strictement supérieure à la clé de la racine, la recherche continue dans le
sous-arbre droit.....
»
↓↓↓ APERÇU DU DOCUMENT ↓↓↓
Liens utiles
- À LA RECHERCHE D·UN NOUVEL ORDRE MONDIAL DEPUIS LES ANNÉES 1970
- Paul McCarthy: Tree
- La recherche scientifique est-elle une recherche de la vérité
- RUSSELL: «La science nous incite donc à abandonner la recherche de la vérité absolue, et à y substituer ce qu'on peut appeler la vérité "technique".»
- Platon: La recherche philosophique de la vérité