Segment-Baum
Der
Segment-Baum erlaubt es, die Intervalle zu finden, die eine Query-Koordinate
enthalten.
Beispiel:
Der
Segment-Baum hierzu:
Die
Intervalle werden dynamisch eingetragen. Die Anfangs- und Endkoordinaten sind
statisch. Man sucht das Grundintervall einer Koordinate und durchläuft den Ast
bis zur Wurzel. Dabei werden alle Intervalleinträge registriert. Z.B. findet
man für die Koordinate 5,3 nacheinander die Intervalle b, c und a.
Range-Baum
Der
Range-Baum erlaubt es, alle Koordinaten zu finden, die in einem Intervall liegen.
Beispiel:
Der
Range-Baum hierzu:
Intervall-Baum
Der
Intervall-Baum erlaubt es, zu einer Koordinate alle Intervalle zu finden, in denen
sie liegt.
Es
werden die Punkte zwischen den Koordinaten erzeugt und in den Knoten alle
Intervalle Stab(p) gespeichert, die von p aufgespießt werden.
Beispiel:
Als
Hilfskoordinaten werden eingefügt:
1,5 3 5 6,5 7,5 8,5 9,5 10,5 14 18,5
Der
Intervall-Baum hierzu:
