Löscht ein Element aus einem kd-Baum von zwei Dimensionen

Question

Ich mag eine kd-Baum (2D) Klasse erweitern zu können Knoten (Punkte) entfernen. Diese Entfernung sollte, ohne dass durchgeführt werden große Teile des Baumes neu zu erstellen. Der Algorithmus in dieser Dias rel="nofollow , auf Folie 13 scheint zu sein, was ich bin nach. Allerdings bin ich Probleme nach der Beschreibung von „findmin ()“ auf dem Objektträger gefunden 7, die in dem Knoten Entfernung Algorithmus verwendet wird.

Fragen

1. Was bedeutet das „i“ in der zweiten Zeile bedeuten dauern? (Vielleicht ist das ein Fehler vom Autor selbst, da es nicht an anderer Stelle verwiesen wird?)

2. Was genau ist "whichAxis"? Ist es die Tiefe der Spaltung Hyperebene wollen wir am nächsten bekommen?

3. Was ist "Minimum ()", zu minimieren? Ich dachte, dies wäre der Abstand zur Achse sein, aber es scheint mir, wie der Autor die Punkte wird minimiert, die keinen Sinn für mich macht.

Answer 1

(1) I denkt i ist ein Tippfehler; Ich habe nicht so etwas in meiner Umsetzung, und es scheint gut zu funktionieren (berühmte letzte Worte ..).

(2) whichAxis ist die Ebene, die Sie für die minimalen sind in. So in zweidimensionalen Daten, es entweder x oder y sein wird. Z.B. für die Punkte (20,40) und (40,20), ist einer der minimale in x und der andere in y. Wenn Sie die Suche nach einem Ersatz-Knoten beginnen, sollten Sie wissen, welche Teilungsebene Sie in suchen.

(3) Der Schlitten seltsam ein wenig geschrieben wird. Sie wollen den Minimalwert in der entsprechenden Ebene zu finden. Vielleicht wird dies ein wenig (c #) klären. Meine Implementierung ist für einen Datensatz mit Ostwerte und Koordinaten X als x und y. minAxis ist nur ein Bool, wie ich immer nur zwei Ebenen haben.

bool winner = minAxis ? (left.Easting < right.Easting) : (left.Northing < right.Northing);
return winner ? left : right;

... wobei links und rechts sind rekursiv die Mindestwerte für von den linken und rechten Kind Bäume des Knotens gesucht wir sind. Ich kann die Post volle Funktion, wenn es deutlicher macht: -)

Answer 2

Wenn Sie eine nodeA in einem bestimmten kd-Baum löschen

(1), wenn nodeA einen Blattknoten ist, nur um es null machen

(2), wenn nodeA ist kein Blattknoten

Assume nodeA split by x , you have two choice

1. find the largest nodeB (whose X is the largest) in left   
2. find the minimum nodeB (whoes X is the minimum) in right  (This pdf prefer it)

Hinweis:

, wenn Sie die nodeB setzen nodeA unter nodeA.right entspricht, sollten Sie 2

, wenn Sie die nodeB setzen nodeA unter nodeA.left entspricht, sollten Sie wählen, 1

Danach ersetzen nodeA mit nodeB und löschen nodeB.