Encontrando la implementación del algoritmo del árbol de intervalos C++

Estoy tratando de encontrar una implementación eficiente del árbol de intervalos de C++ (en su mayoría basada en árboles negros rojos) sin una licencia viral o restrictiva. ¿Alguna sugerencia para una implementación limpia, liviana e independiente? Para el caso de uso que tengo en mente, el conjunto de intervalos se conoce desde el principio (habría, digamos, un millón) y quiero ser capaz de obtener rápidamente una lista de intervalos que se superponen a un intervalo determinado. Por lo tanto, el árbol una vez construido no cambiará, solo necesita consultas rápidas.Encontrando la implementación del algoritmo del árbol de intervalos C++

Fuente

2008-10-17 Anonymous

La biblioteca estándar de C++ ofrece árboles rojos/negros std::map, std::multimap, std::set y std::multiset.

verdad, no se me ocurre ninguna manera de manejar esto con más eficiencia que para mantener un std::map de pares de iterador, y pasando esos pares de iterador a upper_bound() y lower_bound(). Querrá que los pares de iteradores se mantengan en un mapa para que pueda centrarse fácilmente en los pares que probablemente estén en el intervalo (si el iterador de inicio en el "intervalo de candidato" aparece después del final del intervalo dado) estás mirando, entonces puedes omitir el chequeo de eso, y todos los pares de iteradores posteriores).

Fuente

2008-10-17 18:31:22

¿Podría explicar esto un poco más sobre cómo se puede implementar el mapa/conjunto como árboles de intervalo? – Kyuubi

@Kyuubi: sugerí implementar un árbol de intervalos con 'std :: map' /' std :: set' (es decir, comenzando con 'std :: map' /' std :: set' y terminando con un árbol de intervalos ; ** NO ** comenzando con un árbol de intervalos e implementando un 'std :: map',' std :: set'). –

@Kyuubi Al irme de la memoria, creo que la idea era simplemente que tuvieras (1) una colección de cosas, (2) una lista de intervalos en esa colección que estabas viendo, (3) definiste los intervalos con ' begin' y 'end' iterators. Entonces, usando un 'std :: map', podría simplemente hacer que el iterador' begin' sea la clave, y el iterador 'end' correspondiente sea el valor. Con esto, no puede encontrar todos los intervalos que desea en una toma, pero puede reducir los intervalos que necesita para filtrar. –

He escrito una implementación de árbol de intervalos basada en plantilla en C++, https://github.com/ekg/intervaltree. Licencia de MIT Disfrutar.

Fuente

2011-11-17 14:02:00

Tenga en cuenta que esta implementación no puede alterar el árbol una vez que se ha construido, es decir, que construye árboles de intervalos estáticos. Mire http://web.mit.edu/~emin/www.old/source_code/cpp_trees/index.html para árboles 'dinámicos'. – logion

También hay una implementación de C# del árbol Intervalo en this link. Es bastante fácil traducir a C++ para los necesitados

Fuente

2012-07-24 23:34:37 cos

Encontrando la implementación del algoritmo del árbol de intervalos C++

Respuesta

Cuestiones relacionadas