Eliminazione di un elemento da un kd-tree di due dimensioni

Question

Vorrei estendere una classe kd-tree (2D) per essere in grado di rimuovere i nodi (punti). Questa rimozione dovrebbe essere condotta senza dover ricostruire ampie sezioni dell'albero. L'algoritmo descritto in queste , sulla slitta 13 sembra essere quello che sono dopo. Tuttavia, sono problemi seguendo la descrizione di "findmin ()" trovato su slitta 7, che è utilizzato nell'algoritmo di rimozione nodo.

Domande

1. Che cosa significa la "i" significa sulla penultima riga? (Forse questo è un errore da parte dell'autore, in quanto non viene fatto riferimento altrove?)

2. Che cosa è esattamente "whichAxis"? È la profondità della iperpiano splitting vogliamo arrivare più vicino a?

3. Che cosa è "minimo ()", riducendo al minimo? Ho pensato questo sarebbe la distanza rispetto all'asse, ma sembra a me come l'autore è ridurre al minimo i punti, il che non ha senso per me.

Answer 1

(1) I pensare i è un errore di battitura; Io non ho niente del genere nella mia implementazione di esso, e sembra funzionare bene (le ultime parole famose ..).

(2) whichAxis è il piano che si sta cercando per il minimo. Quindi nei dati bidimensionali, sarà sia xo y. Per esempio. per i punti (20,40) e (40,20), una è il minimo in x e l'altro in y. Quando si avvia la ricerca di un nodo di sostituzione, si dovrebbe sapere che aereo divisione si deve effettuare la ricerca.

(3) La slitta è scritto un po 'strano. Si vuole trovare il valore minimo nel piano appropriato. Forse questo chiarirà un po '(c #). Mia implementazione è per un set di dati utilizzando eastings e northings come x ed y. minAxis è solo un bool, come ho sempre e solo avuto due aerei.

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

... dove sinistra e destro sono i valori minimi cercato in modo ricorsivo per da sinistra e figlio destro alberi del nodo in cui siamo. Posso postare il funzione completa se rende più chiaro: -)

Answer 2

Se si desidera eliminare un NodoA in un dato kd-tree

(1) se NodoA è un nodo foglia, basta fare a NULL

(2) se NodoA non è un nodo foglia

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)

Nota:

se si mette il nodoB uguale NodoA sotto nodeA.right, si dovrebbe scegliere 2

se si mette il nodoB uguale NodoA sotto nodeA.left, si dovrebbe scegliere 1

Dopo di che, sostituire NODEA con nodoB ed eliminare nodoB.