Recherche dans un arbre binaire de recherche et recherche par hachage

En 30 secondes

• Arbre binaire de recherche : comparer à chaque nœud, complexité proportionnelle à la hauteur de l'arbre.
• Table de hachage : calculer l'indice par la fonction de hachage, complexité O(1) en moyenne, O(n) si collisions nombreuses.
• Pour beaucoup de données, la recherche par hachage est en moyenne plus rapide qu'un arbre binaire de recherche.

Ce que tu sauras faire

• Rechercher une valeur dans un arbre binaire de recherche en comparant la valeur cherchée à chaque nœud rencontré.
• Rechercher une valeur dans une table de hachage et justifier sa complexité moyenne.
• Comparer la complexité de la recherche selon la structure utilisée (arbre binaire de recherche, table de hachage).

Les mots à connaître

Arbre binaire de recherche

un arbre binaire dans lequel, pour chaque nœud, toutes les valeurs de sa partie gauche lui sont inférieures et toutes les valeurs de sa partie droite lui sont supérieures.

Racine

le nœud de départ d'un arbre, qui n'est l'enfant d'aucun autre nœud.

Nœud

l'élément de base d'un arbre, qui stocke une valeur et des connexions vers ses enfants.

Le piège classique

Croire que la recherche dans un arbre binaire de recherche a toujours la même complexité qu'une recherche par hachage : elle dépend de la hauteur de l'arbre, pas d'un calcul direct d'indice.

L'astuce

Arbre binaire de recherche : la complexité dépend de la HAUTEUR ; table de hachage : la complexité dépend des COLLISIONS.