Ich versuche eine effiziente C ++ - Intervallbaumimplementierung zu finden (meistens basierend auf rot-schwarzen Bäumen) ohne eine virale oder restriktive Lizenz. Irgendwelche Hinweise auf eine saubere, einfache eigenständige Implementierung? Für den Anwendungsfall denke ich, die Menge der Intervalle ist von Anfang an bekannt (es würde sagen, eine Million) und ich möchte in der Lage sein, schnell eine Liste von Intervallen zu erhalten, die ein gegebenes Intervall überlappen. Der einmal erstellte Baum wird sich also nicht ändern - er braucht nur schnelle Abfragen.
Ich habe eine vorlagenbasierte Intervallbaum-Implementierung in C ++ Ссылка geschrieben. MIT-Lizenz. Viel Spaß.
Die C ++ - Standardbibliothek bietet rot / schwarze Bäume std::map , std::multimap , std::set und std::multiset .
Wirklich, ich kann mir keinen besseren Weg vorstellen, dies effizienter zu handhaben, als ein std::map von Iteratorpaaren zu behalten und diese Iteratorpaare an upper_bound() und lower_bound() weiterzuleiten. Sie möchten, dass die Iteratorpaare selbst in einer Map gespeichert werden, damit Sie leicht feststellen können, welche Paare wahrscheinlich im Intervall liegen (wenn der Iterator im "Kandidatenintervall" nach dem Ende des angegebenen Intervalls beginnt) Wenn Sie sich das anschauen, können Sie das - und alle späteren - Iteratorpaare überspringen.
Es gibt auch eine C # -Implementierung der Interval-Struktur unter diesem Link . Es ist einfach genug, in C ++ für die Bedürftigen zu übersetzen
Tags und Links algorithm c++ red-black-tree interval-tree