O grande de la Tabla de Hash vs. árbol de búsqueda binaria

Question

¿Qué llevaría más tiempo?

imprimir todos los elementos almacenados en un árbol de búsqueda binaria en forma ordenada o imprimir todos los elementos almacenados en una tabla hash en el orden establecido.

Se necesitaría más tiempo para imprimir los elementos de una tabla hash a cabo en forma ordenada, porque una tabla hash no está ordenada correcta? y una BST es?

Answer 1

Usted está correcto. Tablas hash están ordenadas según alguna función hash, no por su orden natural, por lo que tendría que extraer todas las entradas S (N) y ordenarlos O (NlogN), mientras que se puede recorrer un árbol binario de búsqueda en orden natural en O ( N).

Nota sin embargo, que en Java, por ejemplo, hay un LinkedHashSet y LinkedHashMap que le da algunas de las ventajas de Hash, pero que pueden ser recorridos en el orden en que fue añadido a, por lo que podría solucionar el problema y ser capaces de atravesar en ese orden ordenadas, así como la extracción de artículos de hash.

Answer 2

Así es, una tabla hash no es "ordenado" en el camino es probable que desee. Los elementos de las tablas hash aún están un poco ordenados, por lo general, a pesar de la disposición es a menudo un poco en la vecindad de una especie. Pero ellos están dispuestos de acuerdo a la función hash, que suele ser muy diferentes de frases similares. No es una clase por cualquier métrica que un humano podría utilizar.

Si la principal cosa que está haciendo con su colección está imprimiendo en forma ordenada, estás mejor uso de algún tipo de BST.

Answer 3

Un árbol binario de búsqueda se almacena de una manera que si lo hace una profundidad primer recorrido, se encuentran los elementos en el orden establecido (suponiendo que tiene una función de comparación constante). El Big O simplemente de devolución de los elementos que ya están en el árbol sería el Big O de recorrer el árbol.

Tiene razón sobre tablas hash, no están ordenados. De hecho, con el fin de enumerar todo en una tabla hash llano, usted tiene que comprobar cada cubo para ver lo que está ahí, tire de él, a continuación, ordenar lo que se obtiene. Mucho trabajo para obtener una lista ordenada de eso.

Answer 4

Los datos de impresión correcto, ordenados almacenados en una tabla hash sería más lento debido a una tabla hash no está ordenada de datos. Simplemente le da una forma rápida de encontrar un artículo en particular. En " Big O Notación ", se dice que el artículo se puede encontrar en un tiempo constante, es decir, O (1) tiempo.

Por otro lado, se puede encontrar un elemento en un árbol binario de búsqueda en "tiempo logarítmica" (O (log n)) porque los datos ya ha sido ordenados para usted.

Así que si objetivo es imprimir una lista ordenada, es mucho mejor tener los datos almacenados en un orden de clasificación (es decir, un árbol binario).

Disfrute,

Robert C. Cartaino

Answer 5

Esto nos lleva a un par de preguntas interesantes. Es un árbol de búsqueda aún más rápido teniendo en cuenta lo siguiente?

1. La incorporación del tiempo de configuración tanto para la tabla hash y el BST?
2. Si el algoritmo de hash produce una lista ordenada de palabras. Técnicamente, se podría crear una tabla hash que utiliza un algoritmo que hace. En cuyo caso el la velocidad del BST vs la tabla hash tendría que bajar a la cantidad de tiempo que se necesita para llenar la tabla hash en el orden de clasificación.

Answer 6

También puedes ver las consideraciones relacionadas de Lista Saltar vs. Árbol Binario: Lista Saltar vs Binary Tree