programas - programacion basica c++

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

Question

Esta pregunta ya tiene una respuesta aquí:

• C ++ - implementación del árbol de intervalos 5 respuestas

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.

Answer 1

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

Realmente, no puedo pensar en ninguna forma de manejar esto de manera más eficiente que mantener un std::map of iterator pairs, y pasar esos pares de iteradores 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).

Answer 2

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

Answer 3

También hay una implementación C # del árbol Interval en este enlace . Es bastante fácil de traducir a C ++ para aquellos en necesidad