Arbre de recherche - Search tree
En informatique , un arbre de recherche est une structure de données arborescente utilisée pour localiser des clés spécifiques à partir d'un ensemble. Pour qu'un arbre fonctionne comme un arbre de recherche, la clé de chaque nœud doit être supérieure à toutes les clés des sous-arbres à gauche et inférieure à toutes les clés des sous-arbres à droite.
L'avantage des arbres de recherche est leur temps de recherche efficace étant donné que l'arbre est raisonnablement équilibré, c'est-à-dire que les feuilles à chaque extrémité sont de profondeurs comparables. Diverses structures de données d'arbre de recherche existent, dont plusieurs permettent également une insertion et une suppression efficaces d'éléments, dont les opérations doivent alors maintenir l'équilibre de l'arbre.
Les arbres de recherche sont souvent utilisés pour implémenter un tableau associatif . L'algorithme de l'arborescence de recherche utilise la clé de la paire clé-valeur pour trouver un emplacement, puis l'application stocke l'intégralité de la paire clé-valeur à cet emplacement particulier.
Types d'arbres
Arbre de recherche binaire
Un arbre de recherche binaire est une structure de données basée sur des nœuds où chaque nœud contient une clé et deux sous-arbres, le gauche et le droit. Pour tous les nœuds, la clé du sous-arbre gauche doit être inférieure à la clé du nœud et la clé du sous-arbre droit doit être supérieure à la clé du nœud. Ces sous-arbres doivent tous être qualifiés d'arbres de recherche binaires.
La complexité temporelle dans le pire des cas pour rechercher un arbre de recherche binaire est la hauteur de l'arbre , qui peut être aussi petite que O(log n) pour un arbre avec n éléments.
B-arbre
Les arbres B sont des généralisations des arbres de recherche binaires en ce sens qu'ils peuvent avoir un nombre variable de sous-arbres à chaque nœud. Bien que les nœuds enfants aient une plage prédéfinie, ils ne seront pas nécessairement remplis de données, ce qui signifie que les arbres B peuvent potentiellement perdre de l'espace. L'avantage est que les arbres B n'ont pas besoin d'être rééquilibrés aussi fréquemment que les autres arbres auto-équilibrés .
En raison de la plage variable de leur longueur de nœud, 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é temporelle pour rechercher un B-tree est O(log n).
(a,b)-arbre
Un arbre (a,b) est un arbre de recherche où toutes ses feuilles ont la même profondeur. Chaque nœud a au moins un enfant et au plus b enfants, tandis que la racine a au moins 2 enfants et au plus b enfants.
a et b peuvent être décidés avec la formule suivante :
La complexité temporelle pour rechercher un arbre (a,b) est de O(log n).
Arbre de recherche ternaire
Un arbre de recherche ternaire est un type d' arbre qui peut avoir 3 nœuds : un enfant bas, un enfant égal et un enfant haut. Chaque nœud stocke un seul caractère et l'arbre lui-même est ordonné de la même manière qu'un arbre de recherche binaire, à l'exception d'un éventuel troisième nœud.
La recherche d'un arbre de recherche ternaire implique la transmission d'une chaîne pour tester si un chemin le contient.
La complexité temporelle pour rechercher un arbre de recherche ternaire équilibré est de O(log n).
Algorithmes de recherche
Recherche d'une clé spécifique
En supposant que l'arbre soit ordonné, nous pouvons prendre une clé et tenter de la localiser dans l'arbre. Les algorithmes suivants sont généralisés pour les arbres de recherche binaires, mais la même idée peut être appliquée aux arbres d'autres formats.
Récursif
search-recursive(key, node)
if node is NULL
return EMPTY_TREE
if key < node.key
return search-recursive(key, node.left)
else if key > node.key
return search-recursive(key, node.right)
else
return node
Itératif
searchIterative(key, node)
currentNode := node
while currentNode is not NULL
if currentNode.key = key
return currentNode
else if currentNode.key > key
currentNode := currentNode.left
else
currentNode := currentNode.right
Recherche de min et max
Dans un arbre trié, le minimum est situé au nœud le plus à gauche, tandis que le maximum est situé au nœud le plus à droite.
Le minimum
findMinimum(node)
if node is NULL
return EMPTY_TREE
min := node
while min.left is not NULL
min := min.left
return min.key
Maximum
findMaximum(node)
if node is NULL
return EMPTY_TREE
max := node
while max.right is not NULL
max := max.right
return max.key