Welche Datenstruktur für Baum? (z.B. Octree, KD-tree)

[Sternkucker]

Cooles Tutorial. Das Programmier-Level ist halt ziemlich hoch und deutlich über meinem angesiedelt.
Kannst du mir einen Lesetip für das erwähnte "dynamische" geben? Hat das mit Pointern zu tun?

Beim Lesen des Octree ist mir aufgefallen: Im Grunde wird doch dabei der Raum in Würfel eingeteilt. Sagen wir, 10x10x10 = 1000 Würfel als Unterteilung des Gesamtraumes.

• Nun könnte ich doch eine Liste erstellen: Würfel 1 enthält Punkte 1, 2, 3,...
• Noch eine Liste: Würfel 1 grenzt an Würfel 2, 3, ... (gesamt 26)
• Man durchsuche den Ausgangswürfel und die umliegenden nach dem nächstliegenden Punkt, und weite die Suche aus falls nötig

So muss man zur Laufzeit im Idealfall nur 26 + 1 von gesamt 1000 Würfeln durchsuchen, das wäre ein Speedup von 37. Die Berechnungen, die zum Aufbau der Struktur anfallen, können im Vorfeld ablaufen, dafür steht genügend Zeit zur Verfügung.

Ist das Verfahren brauchbar? Wieviel schlechter ist es als ein Octree? Das könnte ich mit meinen Fähigkeiten wahrscheinlich gut umsetzen.