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

200

¿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.

Aditya
fuente
12
No es un duplicado. Esa pregunta es si los árboles de fenwick son generalizaciones de árboles de intervalos, y mi pregunta es más específica y diferente.
Aditya
77
No se ha respondido en stackoverflow.com/questions/2795989/… , la respuesta allí solo da definición.
Aditya
12
¿Cómo es demasiado amplio? "¿Cuáles son algunas diferencias entre x e y?" es tan claro y enfocado como se pone. Esta es una muy buena pregunta.
IVlad
16
Y no hay una buena respuesta para esto disponible en ningún lado. Una buena respuesta será excelente para la comunidad
Aditya el
22
La mayoría de estas estructuras de datos (excepto los árboles Fenwick) se revisan en este pdf: "Intervalo, segmento, rango y árboles de búsqueda prioritaria" (por DT Lee). O puede leerlo como un capítulo de este libro: "Manual de estructuras de datos y aplicaciones" .
Evgeny Kluev

Respuestas:

319

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
Lior Kogan
fuente
12
Realmente tengo la impresión de que los árboles de segmento <árboles de intervalo de esto. ¿Hay alguna razón para preferir un árbol de segmentos? Por ejemplo, simplicidad de implementación?
j_random_hacker
77
@j_random_hacker: los algoritmos basados ​​en árboles de segmentos tienen ventajas en ciertas variantes de alta dimensión más complejas de la consulta de intervalos. Por ejemplo, encontrar qué segmentos de línea no paralelos al eje se cruzan con una ventana 2D.
Lior Kogan
55
Gracias, estaría interesado en cualquier explicación que pueda dar sobre eso.
j_random_hacker
3
@j_random_hacker, los árboles de segmentos tienen otro uso interesante: RMQ (consultas mínimas de rango) en el tiempo O (log N) donde N es el tamaño del intervalo general.
ars-longa-vita-brevis
1
¿Por qué los árboles de segmento O (n log n) espacio? Almacenan N hojas + N / 2 + N / 4 + ... + N / 2 ^ (log N), y esta suma es O (N) si no me equivoco. También @ icc97 answer también informa el espacio O (N).
Ant
24

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.

icc97
fuente
2
¿Qué quieres decir con resultados informados?
Pratik Singhal
@ ps06756 los algoritmos de búsqueda a menudo tienen un tiempo de ejecución de log (n) donde n es el tamaño de entrada, pero puede producir resultados lineales en n que no se pueden hacer en tiempo logarítmico (no es posible generar n números en tiempo log (n)) .
oerpli
1
¿No debería tener el árbol de segmentos O(n logn) spaceen la primera tabla?
Danny_ds