algorithm - programar - para que sirve un arbol binario

Tabla Hash vs Árbol binario equilibrado (11)

¿Qué factores debo tener en cuenta cuando necesito elegir entre una tabla hash o un árbol binario equilibrado para implementar un conjunto o una matriz asociativa?

En mi experiencia, los hastables son siempre más rápidos porque los árboles sufren demasiados efectos de caché.

Para ver algunos datos reales, puede consultar la página de referencia de mi biblioteca TommyDS http://tommyds.sourceforge.net/

Aquí puede ver el rendimiento de las bibliotecas de hashtable, tree y trie más comunes disponibles.

Esta pregunta no puede ser respondida, en general, me temo.

El problema es que hay muchos tipos de tablas hash y árboles binarios balanceados, y sus rendimientos varían ampliamente.

Entonces, la respuesta ingenua es: depende de la funcionalidad que necesita. Use una tabla hash si no necesita ordenar y un árbol binario balanceado de lo contrario.

Para una respuesta más elaborada, consideremos algunas alternativas.

Tabla hash (ver la entrada de Wikipedia para algunos conceptos básicos)

No todas las tablas hash usan una lista vinculada como un depósito. Una alternativa popular es usar un cubo "mejor", por ejemplo un árbol binario, u otra tabla hash (con otra función hash), ...
Algunas tablas hash no usan cubetas en absoluto: consulte el direccionamiento abierto (vienen con otros problemas, obviamente)
Hay algo llamado re-hashing lineal (es una calidad de detalle de la implementación), que evita el peligro de "parar el mundo y rehacer". Básicamente, durante la fase de migración, solo se inserta en la tabla "nueva" y también se mueve una entrada "antigua" a la tabla "nueva". Por supuesto, la fase de migración significa doble búsqueda, etc.

Árbol binario

El reequilibrio es costoso, puede considerar una lista saltada (también mejor para accesos de subprocesos múltiples) o un árbol de separación.
Un buen asignador puede "agrupar" nodos en la memoria (mejor comportamiento de almacenamiento en caché), aunque esto no alivia el problema de búsqueda de puntero.
B-Tree y variantes también ofrecen "embalaje"

No olvidemos que O (1) es una complejidad asintótica. Para algunos elementos, el coeficiente suele ser más importante (rendimiento). Lo cual es especialmente cierto si tu función hash es lenta ...

Finalmente, para los conjuntos, también puede considerar estructuras de datos probabilísticos, como Bloom Filters .

Las tablas hash son búsquedas más rápidas:

Necesita una clave que genere una distribución pareja (de lo contrario perderá mucho y tendrá que depender de algo más que hash, como una búsqueda lineal).
Hash puede usar mucho espacio vacío. Puede reservar 256 entradas pero solo necesita 8 (hasta ahora).

Árboles binarios:

Determinista O (log n) Creo ...
No necesita espacio adicional como las tablas hash
Debe mantenerse ordenado. Agregar un elemento en el medio significa mover el resto.

Las tablas hash son generalmente mejores si no hay necesidad de mantener los datos en ningún tipo de secuencia. Los árboles binarios son mejores si los datos deben mantenerse ordenados.

Para agregar a las otras grandes respuestas anteriores, diría:

Use una tabla hash si la cantidad de datos no cambiará (por ejemplo, almacenar constantes); pero, si la cantidad de datos cambiará, use un árbol. Esto se debe al hecho de que, en una tabla hash, una vez que se ha alcanzado el factor de carga, la tabla hash debe cambiar de tamaño. La operación de cambio de tamaño puede ser muy lenta.

Si solo necesita acceder a elementos individuales, las tablas son mejores. Si necesita un rango de elementos, simplemente no tiene otra opción que árboles binarios.

Si tiene muchas instancias ligeramente diferentes de conjuntos, probablemente querrá que compartan estructura. Esto es fácil con árboles (si son inmutables o copy-on-write). No estoy seguro de lo bien que puedes hacerlo con hashtables; es al menos menos obvio.

Un árbol de búsqueda binario requiere una relación de orden total entre las claves. Una tabla hash solo requiere una relación de equivalencia o identidad con una función hash consistente.

Si hay disponible una relación de orden total, una matriz ordenada tiene un rendimiento de búsqueda comparable a los árboles binarios, el peor desempeño de inserción en el orden de las tablas hash, y menos complejidad y uso de memoria que ambos.

La complejidad de inserción del peor de los casos para una tabla hash se puede dejar en O (1) / O (log K) (con K la cantidad de elementos con el mismo hash) si es aceptable aumentar la complejidad de búsqueda del peor caso a O ( K) o O (log K) si los elementos pueden ser ordenados.

Los invariantes para árboles y tablas hash son caros de restaurar si las claves cambian, pero menos de O (n log N) para matrices ordenadas.

Estos son factores a tener en cuenta al decidir qué implementación usar:

Disponibilidad de una relación de orden total.
Disponibilidad de una buena función hash para la relación de equivalencia.
Conocimiento a priori de la cantidad de elementos.
Conocimiento sobre la tasa de inserciones, eliminaciones y búsquedas.
Complejidad relativa de las funciones de comparación y hash.

Un punto a tener en cuenta es sobre el elemento transversal, mínimo y máximo. Las tablas hash no admiten ningún tipo de recorrido ordenado ni acceso a los artículos mínimos o máximos. Si estas capacidades son importantes, el árbol binario es una mejor opción.

Un punto que no creo que se haya abordado es que los árboles son mucho mejores para las estructuras de datos persistentes . Es decir, estructuras inmutables. Una tabla hash estándar (es decir, una que usa una única matriz de listas vinculadas) no se puede modificar sin modificar toda la tabla. Una situación en la que esto es relevante es si dos funciones simultáneas tienen una copia de una tabla hash, y una de ellas cambia la tabla (si la tabla es mutable, ese cambio también será visible para el otro). Otra situación sería algo como lo siguiente:

def bar(table): # some intern stuck this line of code in table["hello"] = "world" return table["the answer"] def foo(x, y, table): z = bar(table) if "hello" in table: raise Exception("failed catastrophically!") return x + y + z important_result = foo(1, 2, { "the answer": 5, "this table": "doesn''t contain hello", "so it should": "be ok" }) # catastrophic failure occurs

Con una tabla mutable, no podemos garantizar que la tabla que recibe una llamada de función permanecerá esa tabla a lo largo de su ejecución, porque otras llamadas a función podrían modificarla.

Entonces, la mutabilidad a veces no es algo agradable. Ahora, una forma de evitar esto sería mantener la tabla inmutable, y hacer que las actualizaciones devuelvan una nueva tabla sin modificar la anterior. Pero con una tabla hash esto a menudo sería una costosa operación O ( n ), ya que todo el arreglo subyacente necesitaría ser copiado. Por otro lado, con un árbol equilibrado, se puede generar un nuevo árbol con la única necesidad de crear nodos O ( log n ) (el resto del árbol es idéntico).

Esto significa que un árbol eficiente puede ser muy conveniente cuando se desean mapas inmutables.

Un punto valioso en una arquitectura moderna: una tabla hash usualmente, si su factor de carga es bajo, tiene menos lecturas de memoria que un árbol binario. Dado que el acceso a la memoria suele ser bastante costoso en comparación con la grabación de ciclos de la CPU, la tabla Hash suele ser más rápida.

En el siguiente árbol binario se supone que es autoequilibrado, como un árbol negro rojo, un árbol AVL o como un ataque .

Por otro lado, si necesita reajustar todo en la tabla hash cuando decide ampliarlo, puede ser una operación costosa (amortizada). Los árboles binarios no tienen esta limitación.

Los árboles binarios son más fáciles de implementar en lenguajes puramente funcionales.

Los árboles binarios tienen un orden de clasificación natural y una forma natural de recorrer el árbol para todos los elementos.

Cuando el factor de carga en la tabla hash es bajo, puede estar desperdiciando una gran cantidad de espacio en la memoria, pero con dos punteros, los árboles binarios tienden a ocupar más espacio.

Las tablas Hash son casi O (1) (dependiendo de cómo maneje el factor de carga) vs. Bin árboles O (lg n).

Los árboles tienden a ser el "actor promedio". No hay nada que hagan particularmente bien, pero luego nada de lo que hacen es particularmente malo.