Algorithmen und Datenstrukturen · Senior · Frage 33 von 75
Welche Struktur findet alle Intervalle, die einen Punkt überlappen, in O(log n + k)?
- 1Ein Trie der Intervallgrenzen
- 2Ein Intervallbaum
- 3Eine Hashtabelle mit dem Start als Schlüssel
Antwort zeigen
Richtige Antwort: Ein Intervallbaum
Erklärung
Ein Intervallbaum ist ein balancierter BST, geordnet nach Start, in dem jeder Knoten auch das maximale Ende seines Teilbaums speichert, sodass ganze Zweige übersprungen werden können. Kalender und Genomwerkzeuge nutzen ihn.