algorithm - intervalos - segment tree
¿Cuáles son las diferencias entre árboles de segmento, árboles de intervalo, árboles indexados binarios y árboles de rango? (2)
¿Cuáles son las diferencias entre árboles de segmento, árboles de intervalo, árboles indexados binarios y árboles de rango en términos de:
- Idea / definición clave
- Aplicaciones
- Rendimiento / orden en dimensiones superiores / consumo de espacio
Por favor no solo dé definiciones.
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 informados
Dimensiones más altas
d > 1
Estas tablas se crean en Markdown Markted Markdown: consulte Gist si desea el texto sin formato.
Todas estas estructuras de datos se utilizan para resolver diferentes problemas:
- El árbol de segmentos almacena intervalos y se optimiza para consultas de " qué de estos intervalos contiene un punto dado ".
- El árbol de intervalos también almacena los intervalos, pero está optimizado para las consultas " cuál de estos intervalos se superponen con un intervalo determinado ". También se puede usar para consultas de puntos, de forma similar al árbol de segmentos.
- El árbol de rangos almacena puntos y se optimiza para las consultas de " qué puntos entran dentro de un intervalo determinado ".
- El árbol binario indexado almacena elementos-conteo por índice, y optimizado para " cuántos elementos hay entre las consultas index my ".
Rendimiento / consumo de espacio para una dimensión:
- Árbol de segmentos - O (n logn) tiempo de preprocesamiento, O (k + logn) tiempo de consulta, O (n logn) espacio
- Árbol de intervalo - O (n logn) tiempo de preprocesamiento, O (k + logn) tiempo de consulta, O (n) espacio
- Árbol de rango - O (n logn) tiempo de preprocesamiento, O (k + logn) tiempo de consulta, O (n) espacio
- Árbol indexado binario - O (n logn) tiempo de preprocesamiento, O (logn) tiempo de consulta, O (n) espacio
(k es la cantidad 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 el tiempo O (logn) (ver here )
- Árbol de intervalo: el intervalo se puede agregar / eliminar en el tiempo O (logn)
- Árbol de rango : nuevos puntos se pueden agregar / eliminar en el tiempo O (logn) (ver here )
- Árbol binario indexado : el recuento de elementos por índice se puede aumentar en el tiempo O (logn)
Dimensiones más altas (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 - O (n logn) tiempo de preprocesamiento, O (k + (logn) ^ d) tiempo de consulta, O (n logn) espacio
- Árbol de rango - O (n (logn) ^ d) tiempo de preprocesamiento, O (k + (logn) ^ d) tiempo de consulta, O (n (logn) ^ (d-1))) espacio
- Árbol binario indexado - O (n (logn) ^ d) tiempo de preprocesamiento, O ((logn) ^ d) tiempo de consulta, O (n (logn) ^ d) espacio