Ventajas de búsqueda binaria Árboles sobre Hash Tables

Question

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

Las tablas hash puede buscar cualquier elemento en Theta (1) tiempo y es tan fácil de añadir un elemento .... pero no estoy seguro de las ventajas que van al revés.

Answer 1

Recuerde que los árboles de búsqueda binaria (basados ??referencia) presentan memoria eficiente. No se reservan más memoria de lo que necesitan.

Por ejemplo, si una función hash tiene un rango R(h) = 0...100, entonces usted necesita para asignar una matriz de elementos 100 (punteros-a), incluso si son sólo de hash 20 elementos. Si se va a utilizar un árbol de búsqueda binaria para almacenar la misma información, sólo se asigna todo el espacio que usted necesita, así como algunos metadatos sobre enlaces.

Answer 2

Una de las ventajas de que nadie más tiene que salir puntas es árbol binario de búsqueda le permite hacer búsquedas por rango de manera eficiente.

Con el fin de ilustrar mi idea, quiero hacer un caso extremo. Digamos que quiere obtener todos los elementos cuyas claves sean entre 0 y 5000. Y en realidad sólo hay uno de esos elementos y otros elementos de 10000 cuyas claves no están en el rango. BST puede hacer búsquedas por rango de forma eficiente ya que no busca un subárbol que es imposible tener la respuesta.

Si bien, ¿cómo se puede hacer búsquedas por rango en una tabla hash? O se necesita iterar cada espacio de cubo, que es O (n), o si tiene que buscar si cada uno de 1,2,3,4 ... hasta 5000 existe. (¿Qué pasa con las teclas entre 0 y 5000 son un conjunto infinito? Teclas de ejemplo se puede decimales)

Answer 3

Una "ventaja" de un árbol binario es que puede ser atravesada a la lista de todos los elementos en orden. Esto no es imposible con una tabla hash, pero no es un diseño normal de operación de un solo en una estructura de hash.

Answer 4

Además de todos los otros comentarios buenos:

Las tablas hash en general tienen un mejor comportamiento de la caché que requiere menos memoria lee en comparación con un árbol binario. Para ver una tabla hash que normalmente sólo se incurrirá en una sola lectura antes de tener acceso a una retención de referencia de los datos. El árbol binario, si se trata de una variante equilibrada, requiere algo en el orden de k * lg (n) lee la memoria para alguna constante k.

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

Los árboles tienden a ser la estructura de datos promedio final. Pueden actuar como listas, puede ser fácilmente dividida para el funcionamiento en paralelo, tienen una eliminación rápida, inserción y búsqueda en el orden de O (lg n) . No hacen nada sobre todo bien, pero que no tienen ningún comportamiento excesivamente mal.

Por último, BSTs son mucho más fáciles de implementar en (puros) lenguajes funcionales en comparación con tablas hash y que no requieren cambios destructivos para ser implementado ( persistencia argumento de Pascal arriba).

Answer 5

Las principales ventajas de un árbol binario sobre una tabla hash es que el árbol binario le da dos operaciones adicionales que no se puede hacer (fácil, rápida) con una tabla hash

• encontrar el elemento más cercano a (no necesariamente igual a) un valor clave arbitraria (o más cercano por encima / debajo)

• repetir el contenido del árbol ordenadamante

Los dos están conectados. - el árbol binario mantiene su contenido en una forma ordenada, así que las cosas que requieren que el orden de clasificación son fáciles de hacer

Answer 6

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

Answer 7

Una tabla hash ocuparía más espacio cuando se crea por primera vez - que tendrá espacios disponibles para los elementos que aún no se han insertado (ya sea que estén o no alguna vez insertados), un árbol de búsqueda binaria sólo será tan grande como Necesita ser. Además, cuando una tabla hash necesita más espacio, ampliando a otra estructura podría llevar mucho tiempo, pero que podría depender de la aplicación.

Answer 8

Un árbol de búsqueda binaria puede ser implementado con un persistente interfaz, donde se devuelve un nuevo árbol, pero el árbol viejo sigue existiendo. Implementado con cuidado, los árboles viejos y nuevos comparte la mayoría de sus nodos. No se puede hacer esto con una tabla hash estándar.

Answer 9

Un árbol binario es más lento para buscar e insertar en, pero tiene la característica muy agradable de los medios que esencialmente infijas recorrido que se puede repetir por los nodos del árbol en una forma ordenada.

iteración a través de las entradas de una tabla hash simplemente no tiene mucho sentido, ya que están esparcidos en la memoria.

Answer 10

BSTs también proporcionan la findSuccessor operaciones "" "findPredecessor" y (Para buscar la siguiente más pequeña y siguientes elementos más grandes) O en el tiempo (log n), que también podría ser operaciones muy práctico. Tabla Hash no puede prestar, en la eficiencia del tiempo.

Answer 11

Cracking the Entrevista Codificación, 6ª Edición

puede aplicar la tabla hash con un árbol binario de búsqueda equilibrado (BST). Esto nos da un O (log n) tiempo de búsqueda. La ventaja de esto es potencialmente usando menos espacio, puesto que ya no asignar una gran matriz. También podemos iterar a través de las teclas en orden, que puede ser a veces útiles.

Answer 12

Si desea acceder a los datos de una manera ordenada, a continuación, una lista ordenada tiene que ser mantenido en paralelo a la tabla hash. Un buen ejemplo es Diccionario en .NET. (Ver http://msdn.microsoft.com/en-us/library/3fcwy8h6 .aspx ).

Esto tiene el efecto secundario de no sólo la desaceleración inserciones, pero consume una mayor cantidad de memoria que un árbol B.

Además, puesto que se ordena un árbol B, es fácil de encontrar rangos de resultados, o para realizar uniones o fusiones.

Answer 13

También depende del uso, Hash permite localizar coincidencia exacta. Si desea consultar para una gama continuación BST es la elección. Suponga que tiene una gran cantidad de datos E1, E2, E3 ..... es.

Con la tabla hash se puede localizar cualquier elemento en un tiempo constante.

Si usted quiere encontrar valores de rango superior a e41 y menos del e8, BST rápidamente se puede encontrar eso.

La clave es la función hash utilizado para evitar una colisión. Por supuesto, no podemos evitar totalmente una colisión, en cuyo caso se recurre al encadenamiento u otros métodos. Esto hace que la recuperación de tiempo más largo constantes en el peor de los casos.

Una vez completa, la tabla hash tiene que aumentar su tamaño cubo y copiar todos los elementos de nuevo. Esto es un coste adicional no está presente más de BST.

Answer 14

A HashMap es un conjunto matriz asociativa. Por lo tanto, la matriz de valores de entrada se agruparon en los cubos. En un esquema de direccionamiento abierto, tiene un puntero a un cubo, y cada vez que se agrega un nuevo valor en un cubo, a averiguar en qué parte del cubo hay espacios libres. Hay algunas maneras de hacer esto: se inicia al comienzo de la cuchara y el incremento del puntero cada vez y probar si su ocupada. Esto se llama el sondeo lineal. A continuación, puede hacer una búsqueda binaria como complemento, en el que el doble de la diferencia entre el comienzo de la cubeta y cuando se hace doble hacia arriba o hacia abajo cada vez que está en busca de un espacio libre. Esto se llama cuadrática de sondeo. OKAY. Ahora los problemas en estos dos métodos es que si la cubeta se desborda en la siguiente dirección de cubos, entonces necesitas -

1. dobles cada uno cubos reducción de tamaño malloc (N cubos) / cambiar el Función- de hash Tiempo necesario: depende de la implementación de malloc
2. Transferencia / Copia cada uno de los cubos de datos anteriores en los nuevos datos de cubos. Esta es una operación O (N), donde N representa los datos enteros

OK. pero si se utiliza un LinkedList no debería ser un derecho tal problema? Sí, ligado En las listas que no tiene este problema. Teniendo en cuenta cada cubo para comenzar con una lista enlazada, y si usted tiene 100 elementos en un cubo que se requiere para atravesar esos 100 elementos para llegar al final de la Lista enlazada por lo tanto el List.add (Elemento E) tendrá tiempo para -

1. Hash el elemento a una normal bucket- como en todas las implementaciones
2. Tome tiempo para encontrar el último elemento de dicho bucket- O (N) operación.

La ventaja de la aplicación LinkedList es que no se necesita la operación de asignación de memoria y transferencia de O (N) / copia de todos los cubos como en el caso de la aplicación direccionamiento abierto.

Por lo tanto, la manera de minimizar el O (n) la operación es convertir la aplicación a la de una búsqueda binaria árbol, donde encuentran las operaciones son O (log (n)) y se agrega el elemento en su posición sobre la base de su valor . La característica añadida de una BST es que viene ordenadas!

Answer 15

Las tablas hash no son buenas para la indexación. Cuando se está en busca de un rango, BSTs son mejores. Esa es la razón por la cual la mayoría de los índices de base de datos utilizan B + árboles en lugar de las tablas Hash

Answer 16

árboles binarios de búsqueda son una buena opción para implementar el diccionario si las teclas tienen alguna orden total (teclas son comparables) definida en ellos y que quieren preservar la información del pedido.

Como BST conserva la información del pedido, que le provee de cuatro operaciones de conexión dinámicos que no pueden ser realizadas (eficientemente) usando tablas hash. Estas operaciones son:

1. máxima
2. Mínimo
3. sucesor
4. predecesor

Todas estas operaciones como cada operación BST tiene complejidad en tiempo de O (H). Asimismo, todas las claves almacenadas permanecen ordenados en el BST lo que le permite obtener la secuencia ordenada de las teclas sólo por la que atraviesa el árbol en el in-orden.

En resumen, si lo único que quieres es operaciones de inserción, borrado y eliminar a continuación, la tabla hash es inmejorable (la mayor parte del tiempo) en el rendimiento. Pero si quieres alguna o todas las operaciones mencionados anteriormente debe utilizar un BST, preferiblemente un BST auto-equilibrio.

Answer 17

árboles binarios de búsqueda puede ser más rápido cuando se utiliza con claves de cadena. Especialmente cuando las cadenas son largas.

binarios de búsqueda árboles usando comparaciones por menos / más rápido que son para cuerdas (cuando no son iguales). Por lo que un BST puede responder rápidamente cuando no se encuentra una cadena. Cuando se ha encontrado que tendrá que hacer sólo una comparación completa.

En una tabla hash. Es necesario para calcular el hash de la cadena y esto significa que hay que ir a través de todos los bytes al menos una vez para calcular el hash. Por otra parte, cuando se encuentra una entrada coincidente.

Answer 18

principal ventaja de la tabla hash es que lo hace casi todas las operaciones en ~ = O (1). Y es muy fácil de entender y aplicar. Lo hace resolver muchos problemas "entrevista" de manera eficiente. Así que si quieres romper una entrevista de codificación, hacer el mejor amigo de tabla hash; -)