Welche Datenstruktur zum Finden eines Punktes in einer Liste von Bereichen?

Question

Ich versuche, die richtige Datenstruktur für diesen Anwendungsfall zu finden, aber habe anscheinend nicht die richtige Terminologie für die Suche.

Ich habe viele Kopien der folgenden Struktur:

struct Item { 
    var start: Int 
    var end: Int 
    var type: Int 
} 

Die in Item dargestellten Bereiche sind nicht überlappend und angrenzend.

Ich muß in der Lage sein:

• Abfrage, die ItemInt Index bei einem gegebenen vorliegen
• Weg vorwärts/rückwärts von dem entfernt Item

der Sammlung von Item Willen regelmäßig aktualisiert werden, entweder als vollständiger Wiederaufbau oder durch Anhängen an das Ende. Mid-collection-Einsätze sind wahrscheinlich selten genug, um einen Neuaufbau von Grund auf zu rechtfertigen.

Kann mir bitte jemand auf eine geeignete Struktur oder vielleicht die richtige Terminologie hinweisen, damit ich mich weiter erforsche?

Answer 1

Wenn die Elemente nicht überlappend und zusammenhängend sind, benötigen Sie das Ende nicht (wie es beim nächsten Start vorausgesetzt wird), und Sie können einfach jede Datenstruktur verwenden, die Sie für sortierte Daten verwenden würden, z. Bäume oder Listen.

Im allgemeinen Fall (= mit Überlappungen) würden Sie wahrscheinlich eine interval tree verwenden.