A exclusão de um elemento a partir de uma kd-tree de duas dimensões

Question

Eu gostaria de estender uma kd-tree (2D) de classe para ser capaz de remover os nós (pontos).Esta remoção deve ser realizada sem ter que reconstruir grande parte da árvore.O algoritmo descrito nestes slides, no slide 13 parece ser o que eu sou depois.No entanto, eu sou problemas a seguir a descrição de "findmin()" encontrados no slide 7, que é utilizado na remoção do nó de algoritmo.

Perguntas

1. O que faz o "eu" significa na segunda para a última linha?(Talvez este seja um erro do autor, como ele não é referenciado em outro lugar?)

2. O que exatamente é "whichAxis"?É a profundidade da divisão de hiperplano queremos chegar o mais próximo?

3. O que é o "mínimo()", minimizando?Eu pensei que esta seria a distância até o eixo, mas parece-me que o autor é minimizar os pontos, o que não faz sentido para mim.

Answer 1

(1) eu acho que eu é um erro de digitação;Eu não tenho nada assim na minha implementação de ti, e parece funcionar bem (famosas últimas palavras..).

(2) whichAxis é o avião que você está procurando o mínimo.Assim, em duas dimensões de dados, ele vai ser x ou y.E. g.para os pontos (20,40) e (40,20), é um mínimo em x e outra em y.Quando você começar a procurar um substituto nó, você deve saber que a divisão de avião, você tem que pesquisar.

(3) A apresentação está escrito um pouco estranha.Você deseja encontrar o valor mínimo adequado de avião.Talvez esclarecer um pouco (c#).Minha implementação é um conjunto de dados usando este e northings como x e y.minAxis é apenas um bool, como eu só tenho sempre dois planos.

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

...onde esquerda e direito são os valores mínimos recursivamente procurado para a esquerda e para a direita criança árvores do nó em que estamos.Eu posso postar a função total se torna mais clara :-)

Answer 2

Se você quiser excluir uma nodea em uma determinada KD-Tree

(1) Se nodea for um nó de folha, basta chegar a NULL

(2) Se Nodea não for um nó foliar

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)

Observação:

Se você colocar o nodeb é igual a nodea sob nodea. direito, você deve escolher 2

Se você colocar o nodeb é igual a nodea sob nodea.left, você deve escolher 1

Depois disso, substitua o NodeA pelo NodeB e exclua o NodeB.