CODEWITHSUNDEEP
algorithmdata-structureskdtree
Kasper Holdum
Kasper Holdum

Reputation: 13373

KdTree Node Removal

I've been trying to implement a KdTree from scratch. Having successfully implemented add-, find nearest neighbour- and find nodes in range methods I am now stuck on removal of nodes.

The method described on wikipedia is vague and rather useless. Instead I am using these slides as starting point. However, the description of the remove method on slide 13 confuses me:

KDNode remove ( KDNode t , Point p , int cd ) {
if ( t == null ) return null;
else if (p.cd < t.data) t.left = remove (t.left , p , cd +1);
else if (p.cd > t.data) t.right = remove (t.right , p , cd +1);
else {
  if (t.right == null && t.left == null ) return null ;
  if (t.right != null )
    t.data = findmin(t.right , cd , cd +1);
  else {
    t.data = findmin (t.left , cd , cd +1);
    t.left = null;
}

t.right = remove (t.right , t . data , cd +1);
return t ;
}}

Both replacing t.left with null and t.right with remove(t.right, ...) makes no sense.

Is this correct, and while we're at it is there anything else wrong with this method? It should be noted that opposite the method described in these slide, I put equal nodes to the left, instead of the right. Is the method still valid?

Upvotes: 2

Views: 3149

Answers (1)

phkahler
phkahler

Reputation: 5767

When you remove a node that is not a leaf, you must replace it with a leaf node from one of the sub-trees. That means the leaf nodes parent needs to get a NULL pointer and the leaf node itself needs to get its pointers set to those values in the node being replaced.

You need to replace the node because neither child node uses the correct splitting axis, so subtrees are not valid if they change level. A minimum right value or the max left value will still partition the points an the same axis and so get used for the replacement.

Upvotes: 2

Related Questions