Prüfungsfrage 06 – k-d-Baum Algorithmus, Datenstruktur

 

Es wird ein zweidimensionaler k-d-Baum aufgebaut, bei dem in jedem Knoten (innere Knoten und Blätter) jeweils ein Punkt gespeichert ist. Die Punkte einer aus n Punkten bestehenden Punktwolke werden dazu zufällig permutiert und dann nacheinander in den Baum eingefügt.
Welche maximale Tiefe kann der Baum dabei erreichen?
Bei welcher geometrischen Lage der Punkte wird die maximale Tiefe des Baums erreicht?

Lösung

Die maximale Tiefe wäre n:

inginf-k-d-baum-tiefe-a

Die geometrische Lage der Punkte müsste für die maximale Tiefe so aussehen, dass der jeweils eingefügte Punkt stets unten rechts (oder auch in andere Diagonalrichtungen) von den vorher eingezeichneten Trennlinien liegt.

inginf-k-d-baum-tiefe-lage

Aufbau der Klasse k-d-Tree:

inginf-k-d-baum-aufbau-klasse

Einfügen in einen k-d-Baum

Für den ersten Punkt: Erzeuge Blatt

Neuen Punkt einfügen:(vs: Startknoten, xp: x-Wert des Punktes; xv: x-Wert des Knotens)

Prozedur Einfügen(vs)
Wenn Tiefe gerade:
Wenn xp < xv
		Wenn linker Teilbaum existiert
			Einfügen(xv.links)
		Sonst
			Erzeuge neues Blatt(links)
Wenn xp > xv
		Wenn rechter Teilbaum existiert
			Einfügen(xv.rechts)
		Sonst
			Erzeuge neues Blatt(rechts)
Sonst: Selbes mit xp und yv