c++ - que - nodos internos de un arbol

C++-implementación del árbol de intervalos

Question

¿Alguien sabe alguna buena implementación del interval tree en C ++?

Obviamente, algo impulsado por la plantilla, mejor en estilo de boost .

Y otra pregunta: si alguien lo prueba, ¿una implementación básica del árbol de intervalos basada en std::vector con ordenación puede vencer al árbol de intervalos genérico (con operaciones O (lg)) en la práctica?

Answer 1

Boost-como? Boost ICL !

La biblioteca Boost Interval Container

Answer 2

Cargué la implementación simple de Interval Tree en github: https://github.com/coolsoftware/ITree

Mira la clase en itree.h.

Answer 3

Parece que hay uno en el kit de herramientas NCBI C ++ .

Sin embargo, el jurado todavía está deliberando sobre si es "bueno" (e incluso si está basado en plantillas, todavía soy algo nuevo en C ++, así que no estoy del todo seguro de que lo sea, pero sospecho que sí).

Answer 4

Tenía exactamente la misma necesidad. No pude encontrar ninguna implementación adecuada (simple, moderna, portátil), así que utilicé una implementación de Python por Brent Pedersen como guía y escribí una versión barebones de C ++ . El IntervalTree se comporta como un contenedor STL estándar, con algunas advertencias debido a su simplicidad (sin iteradores, por ejemplo). Lo usa así ("T" es un tipo arbitrario):

vector<Interval<T> > intervals;
// ... make intervals!
IntervalTree<T> tree(intervals);

Y lo consultas de esta manera:

vector<Interval<T> > results;
tree.findContained(start, stop, results);
// results now contains Intervals which are fully contained in the query interval
results.clear();
tree.findOverlapping(start, stop, results);
// results now contains Intervals which overlap the query interval

Answer 5

si no te importa traducir la implementación de ac # a c ++, ve a http://code.google.com/p/intervaltree/ .based en un árbol de auto equilibrio avl.