Datenstruktur + Algorithmus zum Speichern von nicht überlappenden Intervallen

Question

Ich habe mich gefragt, ob jemand von euch von einer platzsparenden Möglichkeit wusste, nicht überlappende Intervalle zu speichern. Mein Endziel ist es, dies zu verwenden, um virtuellen Adressraum zuzuweisen (ich schreibe ein Betriebssystem zum Spaß) und wollte wissen, ob man die Regionen von freiem Speicherplatz in besser als O (n) Raumkomplexität und O (n) -Suche speichern könnte Komplexität.

Eine probabilistische Datenstruktur könnte funktionieren, weil ich immer die Seitentabelle durchgehen kann, um herauszufinden, ob der Adressraum verfügbar ist.

Danke.

Answer 1

R-Trees kann dafür verwendet werden. Sie werden auch für 2D- (und wahrscheinlich N-dimensionale) Strukturen verwendet, können aber auch 1D-Elemente verwalten, die Sie benötigen.

Answer 2

Werfen Sie einen Blick auf R Trees.