Intervallbaum-Algorithmus, der das Zusammenführen von Intervallen ohne Überlappung unterstützt

Question

Ich suche nach einem Intervallbaumalgorithmus ähnlich dem Rot-Schwarz-Intervallbaum in CLR, der jedoch das Zusammenführen von Intervallen standardmäßig unterstützt, so dass es nie überlappende Intervalle gibt.

Mit anderen Worten, wenn Sie einen Baum mit zwei Intervallen [2,3] und [5,6] hätten und das Intervall [4,4] hinzugefügt hätten, wäre das Ergebnis ein Baum mit nur einem Intervall [2, 6].

Dank

Update: die Verwendung Fall, den ich habe, ist, transitiven Abschluss der Berechnung berücksichtigen. Intervallsätze werden verwendet, um die Nachfolgesätze zu speichern, da sie found to be quite compact sind. Aber wenn Sie Intervall-Sets nur als verkettete Liste darstellen, habe ich festgestellt, dass sie in einigen Situationen ziemlich groß werden können und damit auch die Zeit, die für die Suche nach dem Einfügepunkt benötigt wird. Daher mein Interesse an Intervallbäumen. Es kann auch eine Menge an Verschmelzen eines Baums mit einem anderen (d. H. Eine Satz-ODER-Operation) geben. Wenn beide Bäume groß sind, kann es besser sein, einen neuen Baum zu erzeugen, indem Zwischenreihen beider Bäume statt wiederholter Einfügungen jedes Intervalls verwendet werden.

Answer 1

Das Problem, das ich sehe, ist, dass das Einfügen eines großen Intervalls einen großen Teil des Baumes auslöschen kann, was es schwierig macht, die rot-schwarzen Invarianten wiederherzustellen.

Ich denke, es wäre einfacher, einen Splay-Baum zu verwenden, wie folgt. Zur Vereinfachung enthält jeder Baum zwei Sentinels, ein Intervall A links von allen anderen Intervallen und ein Intervall Z auf der rechten Seite. Fügen Sie beim Einfügen eines Intervalls I den Vorgänger I in den Stamm des Baums ein H. Der Baum sieht aus wie

H 
/\ 
... X 
    /\ 
    ... ... 

Jetzt X lösen und spreizen I ‚s J an der Wurzel Nachfolger zu sein.

H  J 
/ /\ 
...  ... ... 

An dieser Stelle alle Intervalle, die I überlappen sind in J ‚s linken Unterbaum. Trennen Sie diesen Unterbaum und fügen Sie alle Knoten in die freie Liste ein. Erweitern Sie ggf. I. Machen I die Eltern von H und J

 I 
    /\ 
    H J 
/ \ 
...  ... 

und weiter auf unsere fröhliche Art und Weise. Diese Operation ist O (log n) amortisiert, wobei n die Anzahl der Baumknoten ist (dies kann durch Untersuchen der Splay-Tree-Potential-Funktion und Durchführen von viel Algebra bewiesen werden).

---

I sollte hinzufügen, dass es ein natürlicher rekursiven Baum-zu-Baum merge durch die Wurzel eines Baums eingefügt und dann die linken und rechte Teilbäume zu verschmelzen. Ich weiß nicht, wie ich es aus der Hand analysieren soll.