Ventajas de BST sobre Hash Table

Hash Table admite las siguientes operaciones en tiempo Θ(1). 1) Buscar 2) Insertar 3) Eliminar La complejidad temporal de las operaciones anteriores en un árbol de búsqueda binaria (BST) autoequilibrado (como el árbol rojo-negro , el árbol AVL , el árbol Splay , etc.) es O (Iniciar sesión). Entonces Hash Table parece vencer a BST en todas las operaciones comunes. ¿Cuándo deberíamos preferir BST a las tablas hash? ¿Cuáles son las ventajas? Los siguientes son algunos puntos importantes a favor de los BST.

1. Podemos obtener todas las claves ordenadas simplemente haciendo Inorder Traversal of BST. Esta no es una operación natural en Hash Tables y requiere esfuerzos adicionales.
2. Hacer estadísticas de orden , encontrar elementos inferiores y mayores más cercanos , hacer consultas de rango son fáciles de hacer con BST. Al igual que la clasificación, estas operaciones no son una operación natural con tablas hash.
3. Los BST son fáciles de implementar en comparación con el hashing, podemos implementar fácilmente nuestro propio BST personalizado. Para implementar Hashing, generalmente confiamos en las bibliotecas proporcionadas por los lenguajes de programación.
4. Con los BST de autoequilibrio, se garantiza que todas las operaciones funcionarán en tiempo O (Inicio de sesión). Pero con Hashing, Θ(1) es el tiempo promedio y algunas operaciones particulares pueden ser costosas, es decir, O(n ² ), especialmente cuando ocurre el cambio de tamaño de la tabla.
5. En BST podemos realizar búsquedas de rango de manera eficiente, pero en Hash Table no podemos realizar búsquedas de rango de manera eficiente.
6. BST son eficientes en memoria, pero la tabla Hash no lo es.