Letztes ÜbungsBlatt: 2d-tree oder 2d-trie?

Drudge
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 13. Apr 2004 20:17

Letztes ÜbungsBlatt: 2d-tree oder 2d-trie?

Beitrag von Drudge »

Hab da mal ne Verständnisfrage:
Bei der 12.1 b) ist angeblich ein kd-Trie gegeben. Dieser teilt die Ebene, die er beschreibt jeweils horizontal und dann vertikal. Klingt für mich irgendwie nach einem kd-Tree. Ja was denn nun? Und wenn das Übungsblatt korrekt ist, worin liegt denn dann der Unterschied zwischen den beiden.

Ich dachte der kd-Trie basiert darauf, dass abwechselnd auf den Schlüssel operiert wird und nicht die Flächen gesplittet werden. (In der Übung vom letzten Jahr war übrigens das gleiche Problem.)

Wäre nett, wenn mich jemand auflären könnte, weil ich langsam nicht mehr durchblicke.

fG
Drudge

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Der Trie spaltet das Gebiet unabhängig von den enthaltenen Daten immer in der Mitte. Der Tree hingegen spaltet abwechselnd horizontal oder vertikal, aber jeweils an der Position eines bestimmten eingefügten Punktes. Dadurch ist die Splittung i. A. z. B. nicht mehr symmetrisch und hängt außerdem davon ab, in welcher Reihenfolge du die Punkte zur Splittung heranziehst.
In der Übung ist Trie schon richtig.

Drudge
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 13. Apr 2004 20:17

Beitrag von Drudge »

Danke für die Antwort. Auf diese Weise habe ich die Übung auch gelöst, aber irgendwie versteh ich nicht, wieso dass irgendwie in keinem Zusammenhang mit dem Splitten der Schlüssel zu tun hat. (ich seh ihn jedenfalls nicht mehr :P )

Bei der Vorgehensweise mit den Schlüsseln hat man ja vom MSB aus jeweils der Splitreihenfolge entsprechend die Bits zu einem neuen Schlüssel zusammen gefügt. Irgendwie müsste dieser Schlüssel in dem 2d-Trie (in der Baumschreibweise) wiedererkennbar sein, aber irgendwie kam da bei mir nur Murks heraus.

Woher weiß man beim 2d-Trie welche Verzweigung man mit 1 oder 0 gehen muss.
Irgendwie müssen die beiden Herangehensweisen doch etwas miteinander zu tun haben. (beides scheint ja gültig zu sein? das eine aus der übung und das andere wie in den folien?!?!)

Benutzeravatar
mnoll
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 17. Jul 2006 23:03

Beitrag von mnoll »

Ich würde mir nur merken das der kD-Tree eingesetzt wird wenn Punktdaten eingefügt werden sollen und du nach k Dimensionen splitten sollst und der kD-Trie wenn Flächen bzw Raumdaten gespeichert werden sollen die nach k Dimensionen gesplittet werden.

Drudge
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 13. Apr 2004 20:17

Beitrag von Drudge »

okay, danke... so werd ich es wohl machen müssen. :P

Antworten

Zurück zu „Archiv“