En informatique, un arbre de recherche est un arbre enraciné utilisé pour localiser des clés spécifiques à partir d'un ensemble. Afin qu'un arbre fonctionne comme un arbre de recherche, l'étiquette (la valeur contenue dans le nœud) de chaque nœud doit être supérieure à toutes les étiquettes dans le sous-arbre gauche et inférieure à toutes les étiquettes dans le sous-arbre droit.[1]
L'avantage des arbres de recherche est leur efficace temps de recherche étant donné que l'arbre est raisonnablement équilibré, c'est à dire que lesfeuilles sont à des profondeurs comparables. Différentes structures de données d'arbre de recherche existent, dont plusieurs permettent également une insertion et une suppression efficace des éléments, tout en maintenant l'équilibre de l'arbre.
Les arbres de recherches sont souvent utilisés pour implémenter un tableau associatif.
Type d'Arbres
editArbre binaire de recherche
editUn arbre binaire de recherche est une structure de données basée sur des nœuds où chaque nœud contient une étiquette et deux sous-arbres, le gauche et le droit. Pour chaque nœud, l'étiquette de la sous-arborescence gauche doit être inférieure à l'étiquette du nœud actuel, et l'étiquette du sous-arbre droit doit être supérieure à l'étiquette du nœud. Ces sous-arbres doivent aussi être des arbres binaires de recherche.
La complexité en temps pour chercher un élément requiert un temps en O(log(n)) dans le cas moyen, mais O(n) dans le cas critique où l'arbre est complètement déséquilibré et ressemble à une liste chaînée.
Arbre B
editUn arbre B est une généralisation des arbres binaire de recherche dans le sens où il peut peut avoir un nombre variable de sous-arbres à chaque nœud. Ce principe minimise la taille de l'arbre et réduit le nombre d'opérations d'équilibrage. De plus un B-arbre grandit à partir de la racine, contrairement à un arbre binaire de recherche qui croît à partir des feuilles.
Le créateur des arbres B, Rudolf Bayer, n'a pas explicité la signification du « B ». L'explication la plus fréquente est que le B correspond au terme anglais « balanced » (en français : « équilibré »). Cependant, il pourrait aussi découler de « Bayer », du nom du créateur, ou de « Boeing », du nom de la firme pour laquelle le créateur travaillait (Boeing Scientific Research Labs).
En raison de leur nombre de nœuds variable, les arbres B sont optimisés pour les systèmes qui lisent de gros blocs de données. Ils sont également couramment utilisés dans les bases de données.
La complexité en temps pour chercher un élément requiert un temps en O(log(n)).
(a,b)-arbre
editA (a,b)-arbre est un arbre de recherche où toutes les feuilles sont à la même profondeur. Chaque nœud a au moins a fils et au plus b' fils, et la racine a au moins 2 fils et au plus b fils.
a et b peuvent être décidés avec la formule suivante :[2]
La complexité en temps pour chercher un élément requiert un temps en O(log(n)).
Arbre ternaire de recherche
editUn arbre ternaire de recherche (ATR ou TST — pour Ternary Search Tree en anglais) est une structure de données adaptée pour la recherche et combinant les avantages d'un arbre binaire de recherche et d'un arbre préfixe.
La complexité en temps pour chercher un élément dans un arbre ternaire de recherche équilibré requiert un temps en O(log(n)).
Algorithmes de Recherche
editRecherche d'une étiquette spécifique
editEn assumant que l'arbre est ordonnée, on peut prendre une étiquette et essayer de la localiser dans l'arbre. Les algorithmes suivants sont pour un arbre binaire de recherche, mais la même idée peut être appliqué pour les arbres d'autres formats.
Récursivement
editrecherche-récursive(étiquette, nœud) si nœud est NULL retourner ARBRE_VIDE si étiquette < nœud.étiquette retourner recherche-récursive(étiquette, nœud.gauche) sinon si étiquette > nœud.étiquette retourner recherche-récursive(étiquette, nœud.droite) sinon retourner nœud
Itérativement
editrecherche-itérative(étiquette, nœud) nœudCourant := nœud tant que nœudCourant n'est pas NULL si nœudCourant.étiquette = étiquette retourner nœudCourant sinon si nœudCourant.étiquette > étiquette nœudCourant := nœudCourant.gauche sinon nœudCourant := nœudCourant.droite
Recherche du Min et du Max
editDans un arbre trié, le minimum est situé dans le nœud le plus profondément à gauche, et le maximum est situé dans le nœud le plus profond à droite.[3]
Minimum
edittrouverMinimum(nœud) si nœud est NULL retourner ARBRE_VIDE min := nœud tant que min.gauche n'est pas NULL min := min.gauche retourner min.étiquette
Maximum
edittrouverMaximum(nœud) si nœud est NULL retourner ARBRE_VIDE max := nœud tant que max.droite n'est pas NULL max := max.droite retourner max.étiquette
Voir aussi
edit- ^ Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures
- ^ Toal, Ray. "(a,b) Trees"
- ^ Gildea, Dan (2004). "Binary Search Tree"