arrays - recursiva - búsqueda binaria vs árbol de búsqueda binaria

busqueda secuencial en c++

Question

¿Cuál es el beneficio de un árbol de búsqueda binario sobre una matriz ordenada con búsqueda binaria? Solo con el análisis matemático no veo una diferencia, así que supongo que debe haber una diferencia en la sobrecarga de implementación de bajo nivel. El análisis del tiempo medio de ejecución de casos se muestra a continuación.

Matriz ordenada con búsqueda binaria
búsqueda: O (log (n))
inserción: O (log (n)) (ejecutamos la búsqueda binaria para encontrar dónde insertar el elemento)
eliminación: O (log (n)) (ejecutamos búsqueda binaria para encontrar el elemento a eliminar)

Árbol binario de búsqueda
búsqueda: O (log (n))
inserción: O (log (n))
eliminación: O (log (n))

Los árboles de búsqueda binaria tienen el peor caso de O (n) para las operaciones enumeradas anteriormente (si el árbol no está equilibrado), por lo que parece que en realidad sería peor que el ordenado ordenado con búsqueda binaria.

Además, no estoy suponiendo que tengamos que ordenar la matriz de antemano (lo que costaría O (nlog (n)), insertaríamos elementos uno por uno en la matriz, tal como lo haríamos con el árbol binario. de BST que puedo ver es que admite otros tipos de recorridos como inorder, preorder, postorder.

Answer 1

No hay mucho beneficio en consultar cualquiera de los dos.

Pero construir un árbol ordenado es mucho más rápido que construir un conjunto ordenado, cuando se agregan elementos de a uno por vez. Así que no tiene sentido convertirlo en una matriz cuando hayas terminado.

Answer 2

Su análisis es incorrecto, tanto la inserción como la eliminación es O (n) para una matriz ordenada, porque tiene que mover físicamente los datos para hacer espacio para la inserción o comprimirla para cubrir el elemento eliminado.

Ah, y el peor caso para los árboles de búsqueda binaria completamente desequilibrados es O (n), no O (logn).

Answer 3

Tenga en cuenta también que existen algoritmos estándar para mantener árboles de búsqueda binarios equilibrados. Se deshacen de las deficiencias en los árboles binarios y mantienen todas las otras fortalezas. Sin embargo, son complicados, por lo que primero debes aprender sobre árboles binarios.

Más allá de eso, la gran O puede ser la misma, pero las constantes no son siempre. Con los árboles binarios si almacena los datos correctamente, puede aprovechar muy bien el almacenamiento en caché en múltiples niveles. El resultado es que si realiza muchas consultas, la mayor parte de su trabajo permanece dentro de la memoria caché de la CPU, lo que acelera mucho las cosas. Esto es particularmente cierto si tiene cuidado con la estructura de su árbol. Consulte http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx para ver un ejemplo de cómo el diseño inteligente del árbol puede mejorar enormemente el rendimiento. Una matriz en la que realice una búsqueda binaria no permite que se utilicen dichos trucos.