Comparación y selección de ventajas y desventajas de árboles binarios y tablas hash
La respuesta a esta pregunta no se puede explicar claramente en una o dos frases, porque la base para la selección es definitivamente diferente en diferentes situaciones. Primero revisemos estas dos estructuras de datos:
Las tablas hash utilizan una función hash para asignar un índice a los datos de entrada en la ranura correspondiente de la tabla hash. Supongamos que el tamaño de una tabla hash es 100 y los datos que ingresamos son de 0 a 99, entonces necesitamos almacenar los datos de entrada en la tabla hash. Teóricamente, la complejidad temporal de las operaciones de búsqueda e inserción de tablas hash es O (1).
Los árboles binarios insertan y guardan datos según el principio de que el subárbol derecho es más grande que el nodo raíz y el subárbol izquierdo es más pequeño que el nodo raíz. Si el árbol está equilibrado, entonces la complejidad temporal de las operaciones de inserción y búsqueda para cada elemento es O(log(n)), donde n es el número de nodos en el árbol y log(n) suele ser la profundidad del árbol. . Por supuesto, para situaciones desequilibradas, se requieren árboles de estructura de datos más complejos (árboles rojo-negro, etc.).
La conclusión anterior parece ser que las tablas hash son mejores que los árboles binarios, pero no siempre es así. Las tablas hash tienen las siguientes desventajas destacadas:
Por otro lado, analizamos los árboles binarios:
Si conoce el tamaño de los datos de entrada de antemano y tiene suficiente espacio para almacenar los tabla hash y no es necesario ordenar los datos, entonces una tabla hash siempre es buena. Porque las tablas hash solo requieren un tiempo constante durante las operaciones de inserción, búsqueda y eliminación.
Por otro lado, si los datos están creciendo y no se conoce el tamaño de los datos de antemano, entonces un árbol binario es un compromiso.