Quand un arbre AVL mieux qu'une table de hachage?

Question

Plus précisément, ce qu'il ya des opérations qui peuvent être effectuées de manière plus efficace en cas d'utilisation d'un arbre AVL plutôt que d'une table de hachage?

Answer 1

Je préfère généralement AVL aux tables de hachage. Je sais que le O-temps prévu (1) la complexité des tables de hachage bat la complexité O-temps garanti (log n) d'arbres AVL, mais en pratique, les facteurs de constants rendent les deux structures de données généralement compétitifs, et il n'y a pas de soucis de tatillonne sur certaines données inattendues qui évoquent un mauvais comportement. De plus, je trouve souvent que quelque temps pendant la durée de l'entretien d'un programme, dans une situation non prévue lorsque le choix initial d'une table de hachage me semblait juste, que j'ai besoin des données dans l'ordre de tri, donc je finis par la réécriture du programme d'utiliser un arbre AVL au lieu d'une table de hachage; faire cela suffisamment de fois, et vous apprenez que vous pouvez tout aussi bien commencer par AVL.

Si vos clés sont des chaînes, ternaires essais de recherche offrent une alternative raisonnable aux arbres AVL ou tables de hachage.

Answer 2

Une différence évidente, bien sûr, est que, avec AVL (et d'autres arbres équilibrés), vous pouvez avoir persistance : vous pouvez insérer / retirer un élément de l'arbre en O (log N) l'espace et le temps et se retrouver avec non seulement le nouvel arbre, mais aussi de garder le vieil arbre.

Avec une table de hachage, vous pouvez généralement pas faire en moins de O (N) le temps et l'espace.

Une autre différence importante est les opérations nécessaires sur les touches:. AVL tress besoin d'une comparaison de <= entre les touches, tandis que les tables de hachage ont besoin d'une comparaison de = ainsi qu'une fonction hash