¿Cuáles son las diferencias entre árboles de segmento, árboles de intervalo, árboles indexados binarios y árboles de rango?

¿Cuáles son las diferencias entre árboles de segmento, árboles de intervalo, árboles indexados binarios y árboles de rango en términos de:

• Idea clave / definición
• Aplicaciones
• Rendimiento / pedido en dimensiones más altas / consumo de espacio

Por favor, no solo dé definiciones.

Todas estas estructuras de datos se utilizan para resolver diferentes problemas:

• El árbol de segmentos almacena intervalos y está optimizado para consultas sobre " cuál de estos intervalos contiene un punto dado ".
• El árbol de intervalos también almacena intervalos, pero está optimizado para consultas de " cuál de estos intervalos se superponen con un intervalo dado ". También se puede usar para consultas de puntos, similar al árbol de segmentos.
• El árbol de rango almacena puntos y está optimizado para las consultas " qué puntos se encuentran dentro de un intervalo dado ".
• El árbol indexado binario almacena el recuento de elementos por índice y está optimizado para " cuántos elementos hay entre las consultas de índice myn ".

Rendimiento / consumo de espacio para una dimensión:

• Árbol de segmentos : tiempo de preprocesamiento O (n logn), tiempo de consulta O (k + logn), espacio O (n logn)
• Árbol de intervalo : tiempo de preprocesamiento O (n logn), tiempo de consulta O (k + logn), espacio O (n)
• Árbol de rango : tiempo de preprocesamiento O (n logn), tiempo de consulta O (k + logn), espacio O (n)
• Árbol indexado binario : tiempo de preprocesamiento O (n log), tiempo de consulta O (log), espacio O (n)

(k es el número de resultados informados).

Todas las estructuras de datos pueden ser dinámicas, en el sentido de que el escenario de uso incluye tanto cambios de datos como consultas:

• Árbol de segmentos : el intervalo se puede agregar / eliminar en tiempo O (log) (ver aquí )
• Árbol de intervalos: el intervalo se puede agregar / eliminar en tiempo O (log)
• Árbol de rango : se pueden agregar / eliminar nuevos puntos en tiempo O (log) (ver aquí )
• Árbol indexado binario : el recuento de elementos por índice se puede aumentar en tiempo O (log)

Dimensiones superiores (d> 1):

• Árbol de segmentos - O (n (logn) ^ d) tiempo de preprocesamiento, O (k + (logn) ^ d) tiempo de consulta, O (n (logn) ^ (d-1)) espacio
• Árbol de intervalo : tiempo de preprocesamiento O (n logn), tiempo de consulta O (k + (logn) ^ d), espacio O (n logn)
• Árbol de rango - O (n (logn) ^ d) tiempo de preprocesamiento, O (k + (logn) ^ d) tiempo de consulta, O (n (logn) ^ (d-1))) espacio
• Árbol indexado binario - O (n (logn) ^ d) tiempo de preprocesamiento, O ((logn) ^ d) tiempo de consulta, O (n (logn) ^ d) espacio

No es que pueda agregar nada a la respuesta de Lior , pero parece que podría funcionar con una buena mesa.

Una dimensión

k es la cantidad de resultados reportados

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |        n logn |     n logn |         n logn |    n logn |
|Query         |        k+logn |     k+logn |         k+logn |      logn |
|Space         |        n logn |          n |              n |         n |
|              |               |            |                |           |
|Insert/Delete |          logn |       logn |           logn |      logn |

Dimensiones superiores

d > 1

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |     n(logn)^d |     n logn |      n(logn)^d | n(logn)^d |
|Query         |    k+(logn)^d | k+(logn)^d |     k+(logn)^d |  (logn)^d |
|Space         | n(logn)^(d-1) |     n logn | n(logn)^(d-1)) | n(logn)^d |

Estas tablas se crean en Github Formatted Markdown: consulte este Gist si desea que las tablas tengan un buen formato.