Stefan Röttger

← Balancierter Aufwand | ● | kd-Tree Strategy →

Eine Untergruppe von Baumstrukturen, stellen diejenigen dar, welche geometrische Eigenschaften zur Ordnung der Elemente heranziehen.

Viele dieser geometrischen Algorithmen gehen auf das Prinzip des sogenannten Binary Space Partitioning zurĂĽck:

• Ein Punkt+Normalenvektor definieren eine Ebene
• Diese Ebene teilt den Raum in zwei sog. Halbräume
• FĂĽr jeden der zwei Halbräume definiert man weitere Unterteilungsebenen
  • die wiederum Unterteilungsebenen enthalten können
    • so dass eine Binärbaum-Struktur entsteht
• Die Knoten des Baums enthalten jeweils den Ortsvektor eines zu speichernden Datums
• Diese Baumstruktur ermöglicht eine effiziente Baumsuche anhand des Ortsvektors im Raum

Suchkomplexität O(log n)

Zum Vergleich: Suchkomplexität in Listenstruktur O(n)

• Vorteil: Unter der Annahme, dass die Punkte gleichmäßig und zufällig verteilt sind, ist ein BSP Baum automatisch balanciert. D.h. es ist äuĂźerst unwahrscheinlich, dass der Baum zu einer linearen Liste degeneriert und damit nicht effizienter als eine Liste arbeitet.

Unterschiedliche Strategien bei der Wahl der Unterteilungsebenen:

• beliebige Orientierung: BSP Tree
• achsenparallel: k-d-Tree

← Balancierter Aufwand | ● | kd-Tree Strategy →