Caractéristiques des arbres binaires de recherche

1. Ordre

Un arbre binaire de recherche peut servir d'implémentation d'une table de recherche.

Notre objectif en utilisant un arbre binaire de recherche est d'obtenir immédiatement la valeur en recherchant la clé. minimum, maximum, successeur, prédécesseur, plancher, plafond, rang (quel élément a quel rang), et sélection (quel élément est le n-ième) sont toutes des manifestations de la propriété d'ordre des arbres binaires de recherche.

2. Limites

Les arbres binaires de recherche présentent des limites en matière de performance temporelle.

Comme le montre la figure ci-dessous, avec les mêmes nœuds d'éléments, deux arbres binaires de recherche différents peuvent être formés, tous deux satisfaisant la définition :

Un arbre binaire de recherche peut dégénérer en une liste chaînée. En conséquence, l'opération de recherche d'un arbre binaire de recherche est liée à la hauteur de l'arbre, et à ce stade, la hauteur de l'arbre est son nombre de nœuds n. Parallèlement, tous les algorithmes correspondants de l'arbre binaire de recherche dégénèrent au niveau O(n).

autres extensions