¿Cuál es el beneficio de un árbol de búsqueda binario a través de una matriz ordenada con búsqueda binaria? Sólo con el análisis matemático no veo una diferencia, así que yo supongo que debe haber una diferencia en la implementación de bajo nivel de sobrecarga. Análisis del caso promedio tiempo de ejecución es la que se muestra a continuación.

Matriz ordenada con el binario de búsqueda

búsqueda: O(log(n))

inserción: O(log(n)) (tenemos que ejecutar una búsqueda binaria para encontrar dónde insertar el elemento)

eliminación: O(log(n)) (nos ejecutar binarios de búsqueda para encontrar el elemento a eliminar)

Árbol de búsqueda binario

búsqueda: O(log(n))

inserción: O(log(n))

eliminación: O(log(n))

Binario de búsqueda, los árboles tienen un peor caso de O(n) para las operaciones de la lista anterior (si el árbol no está equilibrada), así que parece que en realidad podría ser peor que la matriz ordenada con el binario de búsqueda.

También, no estoy suponiendo que tenemos para ordenar la matriz de antemano (la cual tendría un costo de O(nlog(n)), podemos insertar elementos uno por uno en la matriz, así como lo haría para el árbol binario. La única ventaja de la BST puedo ver es que es compatible con otros tipos de recorridos como el finde, preorder, postorder.

  • inserción y eliminación de búsqueda binaria matriz es O(n) y sólo en la búsqueda es O(log(n)).
  • Si lo era, digamos, de una lista enlazada en lugar de una matriz, a continuación, inserción/deleción tendrá O(log n). Pero no así para una matriz.
  • otro mal comentario, cualquier tipo de búsqueda en una lista enlazada es O(n).
  • Estás en lo correcto. Lo siento @john2011. No estoy seguro de cómo me lo perdí.
  • Sólo para la integridad causa de la Bhaskar se refiere a la inserción/deleción en una lista enlazada, que es O(1). La búsqueda es O(n), como usted bien estado.
InformationsquelleAutor john | 2011-05-11

3 Comentarios

  1. 29

    Su análisis es incorrecto, tanto en la inserción y el borrado es O(n) para una matriz ordenada, porque tienes que físicamente mover los datos para hacer espacio para la inserción o comprimirlo para cubrir el elemento eliminado.

    Ah, y el peor de los casos para desequilibrado árboles de búsqueda binaria es O(n), O(logn).

    • Tenga cuidado al sacar conclusiones de esto, sin embargo, dado que el movimiento de los trozos de memoria en RAM es uno de los más optimizado las operaciones (en los ordenadores modernos).
    • No importa, el acceso aún es lineal.
    • Poco se hace por lo suficientemente pequeño como matrices, que caben en la memoria caché.
  2. 7

    No hay mucho de un beneficio en consultar cualquiera de los dos.

    Pero la construcción de de un criterio de árbol es mucho más rápido que la construcción de una matriz ordenada, cuando vas a añadir elementos de una en una. Así que no hay ningún punto en la conversión de una matriz cuando hayas terminado.

    • Si usted no tiene para apoyar la inserción o deleción (por ejemplo, construir un conjunto de datos de una vez hasta el frente), un conjunto ordenado va a ser más rápido por un muy importante factor constante de árboles de búsqueda binaria. Usted realmente no tiene ninguna sobrecarga de espacio con la matriz, y sus cachés, trabajan mucho mejor cuando sus datos es compacto y no tener que perseguir a los punteros de todo.
    • Sí, eso es bastante más de lo que me dijo el lol.
    • Excepto que no es lo que dijo, Mehrdad. Usted dijo que no habría ningún beneficio consultar cualquiera de las dos y, además, que no habría ningún punto de convertir a un array, mientras Rob Neuhaus dijo exactamente lo contrario: que una matriz ordenada tendría un constante factor de ventaja sobre el árbol. Rob es correcta.
    • Su comentario, literalmente, empezó con «si usted no tiene para apoyar la inserción»; mi respuesta hizo que la conclusión opuesta, porque fue, literalmente, sobre el caso contrario, «cuando vas a añadir elementos de uno en un tiempo»…
    • Estás de nuevo falta el punto. Ambos Rob Neuhaus y yo no estábamos comentando la segunda parte de su reclamo, sólo la primera, es decir, «no Hay mucho de un beneficio en la consulta de cualquiera de los dos.» No es un constante factor de beneficio para la consulta de una matriz ordenada. Su declaración en contrario está equivocado. Estoy de acuerdo con tu segunda afirmación, pero quería corregir su primera reclamación. ¿Usted no está de acuerdo de que hay un constante factor de beneficio para la consulta de una matriz ordenada?
    • ¿Se nota el toda la pregunta era hora de complejidad? Cuando usted está preocupado por el tiempo de complejidad, factores constantes son insignificantes. Ese es todo el punto. Un factor constante, el beneficio es, por tanto, , literalmente, el tipo de cosa que me gustaría clasificar en «no mucho beneficio» cuando alguien me pregunta sobre el tiempo de la complejidad…
    • Por supuesto, yo vi toda la cuestión. La pregunta de los estados a un interés en el «bajo nivel de implementación de gastos». Estoy de acuerdo en que para la consulta de esto sólo puede ser un factor constante. Surge la pregunta de si «un muy importante factor constante», como dice Rob es la misma afirmación como «no hay mucha diferencia.» Me gustaría estar en desacuerdo que una «muy significativo factor constante» deben ser clasificados bajo «no mucho beneficio» cuando ya hemos acordado que el big-O es el mismo. Una «muy significativo factor constante» es muy literalmente un beneficio significativo en programas reales. Se trata de dos diferentes afirmaciones.

  3. 2

    Tenga en cuenta también que hay algoritmos estándar para el mantenimiento equilibrado de búsqueda binaria de los árboles. Que deshacerse de las deficiencias en árboles binarios y mantener todos los otros puntos fuertes. Son complicados, aunque, por lo que usted debe aprender acerca de los árboles binarios de primera.

    Más allá de eso, el big-O puede ser el mismo, pero las constantes y no siempre. Con árboles binarios si se almacenan los datos correctamente, usted puede conseguir un muy buen uso de la caché en múltiples niveles. El resultado es que si usted está haciendo un montón de consultas, la mayor parte de su obra permanece en el interior de caché de CPU que acelera en gran medida las cosas. Esto es particularmente cierto si usted es cuidadoso en la forma de estructura de árbol. Ver http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx para un ejemplo de cómo el inteligente diseño del árbol se puede mejorar el rendimiento en gran medida. Una matriz que hacer una búsqueda binaria de no permitir que ninguna de tales trucos para ser utilizado.

    • ¿Puede por favor explicar como árbol binario nodos puede poner dentro de una caché? Utiliza punteros a un no-secuencial de la memoria lo que significa que aquí no hay ninguna localidad espacial y la memoria caché de datos se pierde. También, a partir de su enlace, y cito – «tenemos una lista estática de los registros, y queremos encontrar el registro con una clave determinada. Tradicionalmente, este problema se resuelve con una matriz y búsqueda binaria, o de un árbol de búsqueda binario. Ambos de estos enfoques presentan pésimo comportamiento de la caché.», que dice que se equivocaron. Especificar qué tipo de corrección en With binary trees if you store the data correctly que quieres decir.

Dejar respuesta

Please enter your comment!
Please enter your name here