Eliminar un elemento de un árbol kd de dos dimensiones

Question

Me gustaría ampliar una clase kd-tree (2D) para poder eliminar nodos (puntos).Esta eliminación debe realizarse sin tener que reconstruir grandes secciones del árbol.El algoritmo descrito en estos diapositivas, en la diapositiva 13 parece ser lo que busco.Sin embargo, tengo problemas para seguir la descripción de "findmin()" que se encuentra en la diapositiva 7, que se utiliza en el algoritmo de eliminación de nodos.

Preguntas

1. ¿Qué significa la "i" en la penúltima línea?(¿Quizás esto sea un error del autor, ya que no se hace referencia a él en otra parte?)

2. ¿Qué es exactamente "cuál eje"?¿Es la profundidad del hiperplano de división a la que queremos acercarnos?

3. ¿Qué es "mínimo()", minimizando?Pensé que esta sería la distancia al eje, pero me parece que el autor está minimizando los puntos, lo cual no tiene sentido para mí.

Answer 1

(1) yo pensar i es un error tipográfico;No tengo nada de eso en mi implementación y parece funcionar bien (últimas palabras famosas...).

(2) cualEje es el avión en el que estás buscando el mínimo.Entonces, en datos bidimensionales, será x o y.P.ej.para los puntos (20,40) y (40,20), uno es el mínimo en x y el otro en y.Cuando comience a buscar un nodo de reemplazo, debe saber en qué plano de división debe buscar.

(3) La diapositiva está escrita de forma un poco extraña.Quiere encontrar el valor mínimo en el plano apropiado.Quizás esto aclare un poco (c#).Mi implementación es para un conjunto de datos usando este y norte como x e y.minAxis es solo un bool, ya que solo tengo dos aviones.

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

...dónde izquierda y bien son los valores mínimos buscados recursivamente en los árboles secundarios izquierdo y derecho del nodo en el que nos encontramos.Puedo publicar la función completa si queda más claro :-)

Answer 2

Si desea eliminar un nodoA en un kd-árbol dado

(1) si nodoA es un nodo hoja, sólo lo hacen en null

(2) si nodoA no es un nodo hoja

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:

si pones el enodoB es igual nodoA bajo nodeA.right, usted debe elegir 2

si pones el enodoB es igual nodoA bajo nodeA.left, usted debe elegir 1

Después de eso, reemplace nodoA con enodoB y eliminar enodoB.