Quels sont les avantages des arbres de recherche binaires par rapport aux tables de hachage?
Les tables de hachage peuvent rechercher n’importe quel élément à l’époque de Theta (1) et il est tout aussi facile d’ajouter un élément ... mais je ne suis pas sûr des avantages qui s’y inversent.
Un avantage que personne ne l'a souligné, c'est que les binaires un arbre de recherche vous permet de faire des recherches de manière efficace.
Afin d'illustrer mon idée, je veux faire un cas extrême. Dites que vous voulez obtenir tous les éléments dont les clés sont entre 0 à 5000. Et effectivement il n'y a qu'un seul élément et 10000 autres éléments dont les clés ne sont pas dans la gamme. BST peut faire la gamme de recherche assez efficace car il ne sera jamais la recherche d'un sous-arbre qui est impossible d'avoir la réponse.
Alors, comment pouvez-vous faire gamme recherche dans une table de hachage? Vous devez effectuer une itération chaque seau de l'espace, qui est en O(n), ou vous avez besoin de rechercher si chacun de 1,2,3,4... jusqu'à 5000 existe. (ce sur les touches entre 0 et 5000 sont un ensemble infini? par exemple, les touches peuvent être décimales)
N'oubliez pas que les arbres de recherche binaires (basés sur des références) utilisent efficacement la mémoire. Ils ne réservent pas plus de mémoire que nécessaire.
Par exemple, si une fonction de hachage a une plage R(h) = 0...100 , vous devez alors allouer un tableau de 100 éléments (pointeurs), même si vous ne faites que 20 éléments. Si vous utilisiez un arbre de recherche binaire pour stocker les mêmes informations, vous alloueriez seulement autant d’espace que nécessaire, ainsi que des métadonnées sur les liens.
En plus de tous les autres bons commentaires:
Les tables de hachage en général ont un meilleur comportement du cache, nécessitant moins de lectures de mémoire par rapport à un arbre binaire. Pour une table de hachage, normalement, vous n'engagera qu'une seule lecture avant d'avoir accès à une référence de la tenue de vos données. L'arbre binaire, si elle est équilibrée variante, exige quelque chose de l'ordre de k * lg(n) de la mémoire de lit pour une constante k.
D'autre part, si un ennemi qui sait votre fonction de hachage que l'ennemi peut faire exécuter votre table de hachage pour faire des collisions, entravent considérablement ses performances. La solution de contournement est de choisir la fonction de hachage au hasard d'une famille, mais un BST n'a pas cet inconvénient. Aussi, lorsque la table de hachage la pression augmente trop, vous avez souvent tendance à enlargen et de réaffecter la table de hachage qui peut être une opération coûteuse. Le BST a plus simple comportement ici et n'a pas tendance à soudainement allouer beaucoup de données et de faire une redéfinition de l'opération.
Les arbres ont tendance à être l'ultime moyen de structure de données. Ils peuvent agir comme des listes, peuvent être divisés en parallèle rapide de suppression, d'insertion et de recherche sur l'ordre de O(lg n). Ils ne font rien en particulier , mais ils n'ont pas trop mauvais comportement.
Enfin, techniciennes se chargent sont beaucoup plus faciles à mettre en œuvre (pur), les langages fonctionnels par rapport à hash-tables et ils ne nécessitent pas de mises à jour destructive pour être mis en œuvre (la persistance de l' argument de Pascal ci-dessus).
Les principaux avantages d'un arbre binaire sur une table de hachage est que l'arbre binaire vous donne deux opérations supplémentaires que vous ne pouvez pas le faire (facile, rapide) avec une table de hachage
trouver l'élément le plus proche (pas nécessairement égal à) certains arbitraire de la valeur de la clé (ou la plus proche au-dessus/en-dessous)
parcourir le contenu de l'arbre dans l'ordre de tri
Les deux sont connectés-l'arbre binaire conserve son contenu dans un ordre trié, donc les choses qui exigent que l'ordre de tri sont faciles à faire.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
