¿Cuándo debo usar un árbol de búsqueda binario sobre un mapa hash?

1. Cuando le importa el orden de las teclas y desea utilizarlo para algunas operaciones.
2. Cuando necesite la garantía del peor de los casos en el tiempo de ejecución. Especialmente cuando las solicitudes provienen del exterior, y usted no las controla ni las restringe de ninguna manera, un adversario podría hacer que su servicio responda muy lentamente si usa una tabla hash.
3. Cuando desee que algunas operaciones difíciles funcionen rápido, como cortar un segmento de una cadena y luego volver a insertarlo en otra posición.

¿Cuándo debo usar un árbol de búsqueda binario sobre un mapa hash?

(Asumiré que este es un árbol de búsqueda binaria con equilibrio automático, y también supondré que te referías a la tabla hash).

Si bien ambos están diseñados para contener una colección de artículos únicos, también tienen diferentes fortalezas y debilidades.

• Si necesita pedir todos los artículos de su colección en todo momento, entonces un árbol de búsqueda binaria suele ser una mejor opción.

• Las tablas hash no admiten el pedido de artículos. Diría que las cosas se colocan en los lugares más aleatorios, pero hay un conjunto muy estricto de reglas sobre dónde se colocan las cosas en una tabla hash.

• Mover todos los elementos a un contenedor más grande en el mapa hash lleva O (n) tiempo.
• Eliminar elementos de un mapa hash no libera tanta memoria como eliminarlos de un árbol de búsqueda binaria. A menos que coloque los elementos restantes en un contenedor más pequeño (de tamaño predeterminado), lo que tomaría O (n) tiempo para hacerlo.

• Una de las otras respuestas ya mencionó esto, pero la tabla hash necesita tiempo para ejecutar el elemento a través de la función hash. Esto le ahorrará mucho tiempo al tratar con una gran cantidad de elementos, ya que puede usar el resultado de la función hash de la misma manera que usamos el índice en la parte posterior del libro. Le permite saltar directamente a los lugares que pueden contener la información que está buscando.

Sirven 2 propósitos muy diferentes. Se utiliza un árbol de búsqueda binario para ordenar los datos en una estructura fácilmente transitable. En un BST, las inserciones y eliminaciones toman la misma cantidad de tiempo y el árbol siempre se ordena una vez que se completa la operación. Un mapa hash es una lista sin clasificar con el hash de algún valor. Proporciona acceso rápido a elementos arbitrarios de la lista a los que hace referencia su clave correspondiente. Las principales consideraciones de un mapa hash son la eficiencia de la función hash utilizada y su propensión a colisiones.

Gracias por el A2A.

La principal ventaja de los BST sobre las tablas hash es que los BST son más eficientes en memoria. Como otros han señalado, los BST solo reservan memoria cuando es necesario.

Como ejemplo, si una tabla hash tiene un rango de 100 elementos, entonces deberíamos asignar una matriz de 100 elementos, incluso si solo estamos utilizando hash 10. Si tuviéramos que usar un BST para almacenar la misma información, solo asignaría tanto espacio como sea necesario.

Sin embargo, tenga en cuenta que las tablas hash suelen ser más eficientes para recuperar elementos que los árboles de búsqueda.

Los árboles de búsqueda binarios se adaptan mejor a los recorridos en orden y las funciones como min () y max () se implementan fácilmente.

Las tablas hash están diseñadas para que las inserciones, eliminaciones y búsquedas basadas en una clave se puedan realizar en tiempo constante siempre que la matriz de cubos sea lo suficientemente grande . Sin embargo, por diseño, a cada elemento se le asigna una posición aparentemente aleatoria en la matriz de cubetas, por lo que los recorridos en orden y las funciones min () y max () son mucho más difíciles de implementar.

Debe usar un Árbol de búsqueda binaria cuando:

1.> Deberá iterar sobre los elementos que estaría almacenando en el conjunto de datos en un orden ordenado.

2.> Si desea realizar operaciones como encontrar todos los datos que son más pequeños / mayores que un valor particular y otro tipo de consultas de rango.

Debe usar una tabla hash cuando:

1.> Necesita una búsqueda rápida de un artículo. Las tablas hash teóricamente admiten la operación de búsqueda O (1), pero depende de cuán buena sea su estrategia de hashing.

2.> Vas a hacer muchas adiciones y eliminaciones. Pero aquí, si en caso de que la matriz subyacente deba ser redimensionada para poder encajar eficientemente en más datos, podría llevar mucho tiempo. Además, necesita una buena estrategia de hash aquí para que no termine con el mismo valor de hash para muchas de las claves y, en consecuencia, cadenas largas.