Ventajas de los árboles de búsqueda binaria sobre las tablas hash

¿Cuáles son las ventajas de los árboles de búsqueda binarios sobre las tablas hash?

Las tablas hash pueden buscar cualquier elemento en tiempo Theta (1) y es igual de fácil agregar un elemento ... pero no estoy seguro de las ventajas de ir al revés.

Recuerde que los árboles de búsqueda binaria (basados ​​en referencias) son eficientes en memoria. No reservan más memoria de la que necesitan.

Por ejemplo, si una función hash tiene un rango R(h) = 0...100, entonces necesita asignar una matriz de 100 elementos (punteros a), incluso si solo está usando el hash de 20 elementos. Si utilizara un árbol de búsqueda binario para almacenar la misma información, solo asignaría tanto espacio como necesitara, así como algunos metadatos sobre los enlaces.

Una ventaja que nadie más ha señalado es que el árbol de búsqueda binaria le permite realizar búsquedas de rango de manera eficiente.

Para ilustrar mi idea, quiero hacer un caso extremo. Supongamos que desea obtener todos los elementos cuyas claves están entre 0 y 5000. Y en realidad solo hay uno de estos elementos y otros 10000 elementos cuyas claves no están en el rango. BST puede realizar búsquedas de rango de manera bastante eficiente ya que no busca en un subárbol que sea imposible tener la respuesta.

Mientras tanto, ¿cómo se pueden realizar búsquedas de rango en una tabla hash? O debe iterar cada espacio de depósito, que es O (n), o debe buscar si existe cada uno de 1,2,3,4 ... hasta 5000. (¿Qué pasa con las claves entre 0 y 5000 son un conjunto infinito? Por ejemplo, las claves pueden ser decimales)

Una "ventaja" de un árbol binario es que se puede recorrer para enumerar todos los elementos en orden. Esto no es imposible con una tabla hash, pero no es una operación normal un diseño en una estructura hash.

Además de todos los otros buenos comentarios:

Las tablas hash en general tienen un mejor comportamiento de caché y requieren menos lecturas de memoria en comparación con un árbol binario. Para una tabla hash, normalmente solo se realiza una lectura antes de tener acceso a una referencia que contiene sus datos. El árbol binario, si es una variante balanceada, requiere algo del orden de k * lg (n) lecturas de memoria para alguna constante k.

Por otro lado, si un enemigo conoce su función hash, el enemigo puede hacer cumplir su tabla hash para hacer colisiones, lo que obstaculiza enormemente su rendimiento. La solución es elegir la función hash al azar de una familia, pero un BST no tiene esta desventaja. Además, cuando la presión de la tabla hash aumenta demasiado, a menudo tiende a agrandar y reasignar la tabla hash, lo que puede ser una operación costosa. El BST tiene un comportamiento más simple aquí y no tiende a asignar repentinamente una gran cantidad de datos y hacer una operación de refrito.

Los árboles tienden a ser la estructura de datos promedio final. Pueden actuar como listas, se pueden dividir fácilmente para operaciones en paralelo, se pueden eliminar, insertar y buscar rápidamente en el orden de O (lg n) . No hacen nada particularmente bien, pero tampoco tienen un comportamiento excesivamente malo.

Finalmente, los BST son mucho más fáciles de implementar en lenguajes funcionales (puros) en comparación con las tablas hash y no requieren la implementación de actualizaciones destructivas (el argumento de persistencia de Pascal anterior).

Las principales ventajas de un árbol binario sobre una tabla hash es que el árbol binario le brinda dos operaciones adicionales que no puede realizar (fácil y rápidamente) con una tabla hash.

• encontrar el elemento más cercano (no necesariamente igual a) algún valor clave arbitrario (o más cercano arriba / abajo)

• iterar a través del contenido del árbol en orden ordenado

Los dos están conectados: el árbol binario mantiene su contenido en un orden ordenado, por lo que las cosas que requieren ese orden son fáciles de hacer.

Un árbol de búsqueda binario (balanceado) también tiene la ventaja de que su complejidad asintótica es en realidad un límite superior, mientras que los tiempos "constantes" para las tablas hash son tiempos amortizados: si tiene una función hash inadecuada, podría terminar degradándose a tiempo lineal , en lugar de constante.

Una tabla hash ocuparía más espacio cuando se crea por primera vez; tendrá espacios disponibles para los elementos que aún no se han insertado (ya sea que se hayan insertado o no), un árbol de búsqueda binaria solo será tan grande como sea necesario ser. Además, cuando una tabla hash necesita más espacio, expandirse a otra estructura podría llevar mucho tiempo, pero eso podría depender de la implementación.

Se puede implementar un árbol de búsqueda binaria con una interfaz persistente , donde se devuelve un árbol nuevo, pero el árbol antiguo continúa existiendo. Implementados con cuidado, los árboles nuevos y viejos comparten la mayoría de sus nodos. No puede hacer esto con una tabla hash estándar.

Un árbol binario es más lento de buscar e insertar, pero tiene la característica muy agradable del recorrido infijo que esencialmente significa que puede iterar a través de los nodos del árbol en un orden clasificado.

Iterar las entradas de una tabla hash simplemente no tiene mucho sentido porque están todas dispersas en la memoria.

De Cracking the Coding Interview, sexta edición

Podemos implementar la tabla hash con un árbol de búsqueda binario balanceado (BST). Esto nos da un tiempo de búsqueda O (log n). La ventaja de esto es que potencialmente usa menos espacio, ya que ya no asignamos una matriz grande. También podemos iterar a través de las claves en orden, lo que a veces puede ser útil.

Los BST también proporcionan las operaciones "findPredecessor" y "findSuccessor" (para encontrar el siguiente elemento más pequeño y el siguiente más grande) en tiempo O (logn), que también pueden ser operaciones muy útiles. Hash Table no puede proporcionar eficiencia en ese tiempo.

Si desea acceder a los datos de forma ordenada, debe mantener una lista ordenada en paralelo a la tabla hash. Un buen ejemplo es el Diccionario en .Net. (consulte http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx ).

Esto tiene el efecto secundario de no solo ralentizar las inserciones, sino que consume una mayor cantidad de memoria que un árbol b.

Además, dado que un árbol b está ordenado, es sencillo encontrar rangos de resultados o realizar uniones o fusiones.

También depende del uso, Hash permite localizar coincidencias exactas. Si desea consultar un rango, BST es la opción. Suponga que tiene muchos datos e1, e2, e3 ..... en.

Con la tabla hash puedes localizar cualquier elemento en tiempo constante.

Si desea encontrar valores de rango mayores que e41 y menores que e8, BST puede encontrarlo rápidamente.

La clave es la función hash que se usa para evitar una colisión. Por supuesto, no podemos evitar totalmente una colisión, en cuyo caso recurrimos al encadenamiento u otros métodos. Esto hace que la recuperación ya no sea un tiempo constante en el peor de los casos.

Una vez llena, la tabla hash tiene que aumentar su tamaño de cubo y copiar todos los elementos nuevamente. Este es un costo adicional que no está presente en BST.

Las tablas hash no son buenas para indexar. Cuando busca un rango, las BST son mejores. Esa es la razón por la que la mayoría de los índices de bases de datos usan árboles B + en lugar de tablas hash.

Los árboles de búsqueda binaria son una buena opción para implementar el diccionario si las claves tienen definido algún orden total (las claves son comparables) y desea conservar la información de la orden.

Como BST conserva la información de la orden, le proporciona cuatro operaciones de conjuntos dinámicos adicionales que no se pueden realizar (eficientemente) usando tablas hash. Estas operaciones son:

1. Máximo
2. Mínimo
3. Sucesor
4. Predecesor

Todas estas operaciones, como todas las operaciones BST, tienen una complejidad de tiempo de O (H). Además, todas las claves almacenadas permanecen ordenadas en la BST, lo que le permite obtener la secuencia ordenada de claves simplemente atravesando el árbol en orden.

En resumen, si todo lo que desea son operaciones de inserción, eliminación y eliminación, la tabla hash es inmejorable (la mayoría de las veces) en rendimiento. Pero si desea alguna o todas las operaciones enumeradas anteriormente, debe usar un BST, preferiblemente un BST autoequilibrado.

La principal ventaja de la tabla hash es que hace casi todas las operaciones en ~ = O (1). Y es muy fácil de entender e implementar. Resuelve muchos "problemas de entrevistas" de manera eficiente. Entonces, si quieres descifrar una entrevista de codificación, haz mejores amigos con la tabla hash ;-)

Un mapa de hash es una matriz asociativa establecida. Por lo tanto, su matriz de valores de entrada se agrupa en depósitos. En un esquema de direccionamiento abierto, tiene un puntero a un depósito, y cada vez que agrega un nuevo valor a un depósito, descubre en qué lugar del depósito hay espacios libres. Hay algunas formas de hacer esto: comienza desde el principio del depósito e incrementa el puntero cada vez y prueba si está ocupado. A esto se le llama sondeo lineal. Luego, puede hacer una búsqueda binaria como agregar, donde duplica la diferencia entre el comienzo del depósito y donde dobla hacia arriba o hacia abajo cada vez que busca un espacio libre. A esto se le llama sondeo cuadrático. OKAY. Ahora, el problema en ambos métodos es que si el depósito se desborda en la siguiente dirección de depósito, entonces necesita-

1. Duplique el tamaño de cada cubeta: malloc (N cubos) / cambie la función hash: tiempo requerido: depende de la implementación de malloc
2. Transfiera / copie cada uno de los datos de los depósitos anteriores en los datos de los depósitos nuevos. Esta es una operación O (N) donde N representa todos los datos

OKAY. pero si usa una lista vinculada, no debería haber tal problema, ¿verdad? Sí, en listas enlazadas no tienes este problema. Teniendo en cuenta que cada segmento comienza con una lista vinculada, y si tiene 100 elementos en un segmento, debe atravesar esos 100 elementos para llegar al final de la lista vinculada, por lo tanto, List.add (Elemento E) tomará tiempo para-

1. Hash el elemento en un depósito: normal como en todas las implementaciones
2. Tómese el tiempo para encontrar el último elemento en dicha operación de cubo-O (N).

La ventaja de la implementación de la lista vinculada es que no necesita la operación de asignación de memoria y la transferencia / copia O (N) de todos los depósitos como en el caso de la implementación de direccionamiento abierto.

Entonces, la forma de minimizar la operación O (N) es convertir la implementación a la de un Árbol de búsqueda binario donde las operaciones de búsqueda son O (log (N)) y agrega el elemento en su posición en función de su valor. ¡La característica adicional de un BST es que viene ordenado!

Los árboles de búsqueda binaria pueden ser más rápidos cuando se usan con claves de cadena. Especialmente cuando las cuerdas son largas.

Árboles de búsqueda binaria que utilizan comparaciones para menor / mayor que son rápidas para cadenas (cuando no son iguales). Entonces, un BST puede responder rápidamente cuando no se encuentra una cadena. Cuando se encuentre, solo tendrá que hacer una comparación completa.

En una tabla hash. Debe calcular el hash de la cadena y esto significa que debe pasar por todos los bytes al menos una vez para calcular el hash. Por otra parte, cuando se encuentra una entrada coincidente.