La suppression d'un élément à partir d'un arbre kd de deux dimensions

Question

Je voudrais étendre une classe pour être en mesure kd-tree (2D) pour supprimer des nœuds (points). Cette suppression doit être effectuée sans avoir à reconstruire une grande partie de l'arbre. L'algorithme décrit dans ces , sur la diapositive 13 semble être ce que je suis après. Cependant, je suis mal à suivre la description de « findmin () » se trouve sur la diapositive 7, qui est utilisé dans l'algorithme de suppression de nœud.

Questions

1. Que signifie le « i » sur la seconde dernière ligne? (Peut-être que cela est une erreur par l'auteur, car il n'est pas référencé ailleurs?)

2. Qu'est-ce exactement "whichAxis"? Est-ce la profondeur de l'hyperplan de division que nous voulons le plus proche?

3. Qu'est-ce que "minimum ()", ce qui réduit? Je pensais que ce serait la distance par rapport à l'axe, mais il me semble que l'auteur est de minimiser les points, ce qui n'a pas de sens pour moi.

Answer 1

(1) I pense i est une faute de frappe; Je n'ai pas quelque chose comme ça dans ma mise en œuvre de celui-ci, et il semble fonctionner très bien (derniers mots célèbres ..).

(2) whichAxis est le plan que vous recherchez le minimum. Donc, dans les données en deux dimensions, ce sera soit x ou y. Par exemple. pour les points (20,40) et (40,20), l'un est le minimum en x et y dans l'autre. Lorsque vous démarrez la recherche d'un nœud de remplacement, vous devez savoir quel plan fractionnement vous devez effectuer la recherche.

(3) La diapositive est écrit un peu étrange. Vous voulez trouver la valeur minimale dans le plan approprié. Peut-être cela clarifiera un peu (c #). Ma mise en œuvre est un ensemble de données en utilisant et abscisses comme x ordonnées et y. minAxis est juste un bool, comme je n'ai jamais deux avions.

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

... où gauche et droite sont les valeurs minimales récursive recherchées des arbres enfants gauche et à droite du nœud que nous sommes. Je peux afficher les fonctions si elle le rend plus clair: -)

Answer 2

Si vous voulez supprimer un nodeA dans un arbre kd donné

(1) si nodeA est un noeud feuille, il suffit de le faire à null

(2) si nodeA est pas un noeud feuille

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)

Remarque:

si vous mettez le nodeB est égal à nodeA sous nodeA.right, vous devez choisir 2

si vous mettez le nodeB est égal à nodeA sous nodeA.left, vous devez choisir 1

Après cela, remplacez nodeA avec nodeB et supprimer nodeB.