Arbre binaire de recherche
I. Concept et introduction
Arbre de recherche binaire (en anglais : Binary Search Tree), également appelé arbre binaire de recherche, arbre de recherche binaire, arbre binaire ordonné ou arbre binaire trié. Il satisfait aux conditions suivantes :
- Si son sous-arbre gauche n'est pas vide, toutes les valeurs des nœuds du sous-arbre gauche sont inférieures à son nœud racine.
- Si son sous-arbre droit n'est pas vide, toutes les valeurs des nœuds du sous-arbre droit sont supérieures à son nœud racine.
Ses sous-arbres gauche et droit sont également des arbres de recherche binaires.
Comme le montre la figure ci-dessous :
II. Notes d'applicabilité
Les arbres de recherche binaires offrent des opérations efficaces d'insertion, de suppression et de recherche.
La complexité temporelle moyenne estO(log n), le pire cas estO(n). Les arbres de recherche binaires sont différents des tas ; ils ne sont pas nécessairement des arbres binaires complets, et la couche sous-jacente n'est pas facilement représentée directement par des tableaux, c'est pourquoi des listes chaînées sont utilisées pour implémenter les arbres de recherche binaires.
| Rechercher un élément | Insérer un élément | Supprimer un élément | |
|---|---|---|---|
| Tableau normal | O(n) | O(n) | O(n) |
| Tableau ordonné | O(logn) | O(n) | O(n) |
| Arbre binaire de recherche | O(logn) | O(logn) | O(logn) |
Ci-dessous, nous présentons d'abord la méthode de recherche binaire sous forme de tableau comme référence conceptuelle, puis nous continuons à présenter la méthode de recherche des arbres binaires de recherche.
III. Illustration du processus de la méthode de recherche binaire
L'idée de la recherche binaire a été proposée en 1946. Le problème de recherche est un problème fondamental très important en informatique. La recherche binaire ne peut être utilisée que sur des séquences ordonnées. Si nous voulons trouver un élément, examinons d'abord la relation entre la valeur du milieu V du tableau et les données cibles. Il y a trois cas :
- 1. S'il est égal aux données cibles, il est trouvé directement.
- 2. S'il est inférieur à V, continuez la recherche dans le groupe inférieur à V.
- 2. S'il est supérieur à V, continuez la recherche dans le groupe supérieur à V.
IV. Exemple de code Java
Téléchargement du paquet de code source :Télécharger
Code du fichier src/example/binary/BinarySearch.java :
/**
* Méthode de recherche dichotomique
*/
public class BinarySearch {
// Méthode de recherche dichotomique : trouver target dans le tableau trié arr
// Si target est trouvé, renvoyer l'indice correspondant
// Si target n'est pas trouvé, renvoyer -1
public static int find(Comparable[] arr, Comparable target) {
// trouver target dans arr[l...r]
int l = 0, r = arr.length-1;
while( l <= r ){
//int mid = (l + r)/2;
// pour éviter un dépassement d'entier dans les cas extrêmes, utiliser la logique suivante pour calculer mid
int mid = l + (r-l)/2;
if( arr[mid].compareTo(target) == 0 )
return mid;
if( arr[mid].compareTo(target) > 0 )
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
}