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

101

¿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.

Devoto
fuente
para tablas hash, ¿cuáles son los tiempos de ejecución para find () insert () y remove ()? theta (1) theta (1) y theta (1) ¿verdad?
Dedicado el
8
Casi siempre, sí. Si se encuentra con muchas colisiones, esos tiempos podrían aumentar hasta O (n).
Christian Mann
1
Estos tiempos también dependen de su función hash. Si por alguna extraña razón no es O (1), obviamente sus operaciones tendrán un límite mínimo de cualquier eficiencia a la que se ejecute su función hash.
Christian Mann
Yo diría que las mayores ventajas de BST es que está en una estructura de datos ordenada. Detalle de caso de uso ya enumerado aquí .
Yuantao
Posible duplicado de árboles binarios frente a listas vinculadas frente a tablas hash
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Respuestas:

93

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.

Christian Mann
fuente
33
No es cierto que todo el rango de salidas de la función hash tenga que existir en la matriz. Los valores hash se pueden modificar simplemente por la longitud de la matriz para permitir una matriz más pequeña. Por supuesto, es posible que no se conozca el número final de elementos que se agregan, por lo que la tabla hash aún puede asignar más espacio del necesario. Sin embargo, los árboles de búsqueda binarios pueden desperdiciar tanta memoria o más. Las implementaciones vinculadas necesitan espacio para al menos dos punteros adicionales por elemento (tres si se usa un puntero principal), y las BST basadas en matrices pueden desperdiciar mucha memoria para las porciones sin completar del árbol.
Solaraeus
4
@Solaraeus: Los BST basados ​​en matrices son los mejores para comparar con las tablas hash y no son más derrochadores que las tablas hash. También puede expandir una BST con poco más que una copia de memoria, en comparación con volver a calcular la tabla completa.
Guvante
125

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)

Alex
fuente
11
¡Los BST realizan búsquedas de rango de manera eficiente! Para mí, esta es la mejor respuesta en términos de enfoque práctico y algorítmico.
ady
4
wow, esto realmente explica por qué los árboles están tan asociados con las bases de datos; sus beneficios son más visibles cuando necesita realizar un filtrado basado en claves. con mapas hash, debe recorrer todas las claves para resolver "encontrar todos los elementos con clave entre 1000 y 3290"
Dmitry
77

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.

NealB
fuente
3
atravesar en cualquier orden probablemente no tendría ningún sentido en una tabla hash.
FrustratedWithFormsDesigner
2
@FrustratedWithFormsDesigner. Ver Tabla de hash lineal ordenada
NealB
Gracias por el enlace, ¡es una idea que se cruza! No creo que haya visto o usado una implementación de eso (al menos sin saberlo).
FrustratedWithFormsDesigner
1
Enlace de Wayback Machine para el artículo: web.archive.org/web/20100323091632/http://www.concentric.net/…
rahulroy9202
51

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).

DOY RESPUESTAS MALGAS
fuente
3
BSTs are much easier to implement in (pure) functional languages compared to hash-tables- ¿De Verdad? ¡Quiero aprender un lenguaje funcional ahora!
nawfal
1
La tabla hash debe ser persistente en un lenguaje funcional. Esto a menudo complica las implementaciones.
DOY RESPUESTAS
Para elaborar, si crea estructuras de datos de presidente en lenguajes funcionales, todo lo que realmente termina haciendo es escribir el mismo código que haría en ensamblador, excepto que en cada operación transforma explícitamente su matriz de memoria / registros, o habla con un servidor para fingir Para hacer eso. Estoy a favor de ser consciente de su estado, pero es isomórfico al enfoque imperativo si se hace correctamente (no puede copiar de manera realista una gran cantidad de datos en cada transformación en la vida real, debe hacer trampa).
Dmitry
27

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.

Chris Dodd
fuente
BST encuentra la coincidencia más cercana, solo si la coincidencia exacta no existe, ¿verdad? ¿Qué pasa si encuentra una coincidencia exacta en la raíz misma?
desarrollador747
2
@ developer747: Entonces los siguientes más cercanos abajo y arriba son la hoja más a la derecha del subárbol izquierdo y la hoja más a la izquierda del subárbol derecho.
Chris Dodd
16

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.

jamesnvc
fuente
3
Para llevar este punto a casa, un caso degenerado es cuando la colección contiene muchas copias de solo 1 clave. en el BST, insertar es O (log n), en una tabla Hash, insertar es O (n)
SingleNegationElimination
2
Cuando una tabla hash contiene muchas copias de solo 1 clave, insertar es (todavía) O (1), no O (n). El problema de las tablas hash es cuando hay muchas claves diferentes con el mismo hash. Esto se puede evitar mediante un esquema de hash dinámico que cambia a una función de hash diferente cuando hay muchas colisiones.
Chris Dodd
Tenga en cuenta que un árbol desequilibrado puede degenerar en una lista y también tener una búsqueda O (n).
awiebe
9

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.

FrustratedWithFormsDiseñador
fuente
8

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.

Pascal Cuoq
fuente
6

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.

Blagovest Buyukliev
fuente
6

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.

Guy Kahlon
fuente
5

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.

Balaji
fuente
Si está buscando operaciones "findPredecessor" y "findSuccessor", entonces HashTable es una mala elección para la estructura de datos en primer lugar.
AKDesai
1

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.

IamIC
fuente
1

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.

sreeprasad
fuente
1

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.

ssD
fuente
Los índices de las bases de datos son de ambos tipos, hash y árboles B +. Cuando desee hacer una comparación como mayor o menor que, entonces el índice de árboles B + es útil; de lo contrario, el índice hash es útil para la búsqueda. También piense en cuándo los datos no son comparables y si desea crear un índice, entonces db creará un índice hash y no un índice de árbol B +. @ssD
Sukhmeet Singh
1

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.

mightyWOZ
fuente
0

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 ;-)

rajya vardhan
fuente
Creo que el OP pidió ventajas de BST sobre el hash.
Sniper
0

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!

Vamsavardhana Vijay
fuente
0

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.

Calmarius
fuente