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:
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.
Aufbau der Klasse k-d-Tree:
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