búsqueda binaria vs árbol de búsqueda binaria

Question

¿Cuál es la ventaja de un árbol de búsqueda binaria 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)) (corremos búsqueda binaria para encontrar dónde insertar el elemento)
eliminación: O (log (n)) (corremos búsqueda binaria para encontrar el elemento a borrar)

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

Búsqueda binaria tre Es 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 para el árbol binario . El único beneficio de BST que puedo ver es que soporta otros tipos de recorridos como el finde, pre-pedido, orden posterior.

Answer 1

Su análisis es erróneo, tanto la inserción y deleción es O (n) para una matriz ordenada, ya que hay que mover físicamente los datos para hacer espacio para la inserción o comprimir para tapar el elemento eliminado.

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

Answer 2

no hay mucho de un beneficio en consultar cualquiera de ellos.

Pero construir una el árbol ordenado es mucho más rápido que construir una matriz ordenada, cuando agrega elementos uno a la vez. Por lo tanto, no tiene sentido convertirlo a una matriz cuando hayas terminado.

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 el rendimiento en gran medida. Una matriz en la que realice una búsqueda binaria no permite que se utilicen dichos trucos.