KD Tree

ref: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf

KD tree is useful when try to find a nearest neighbor in space quickly.

KD tree has the following feature:
(1) each level has a "cutting dimension"
(2) cycle through the dimensions as you walk down the tree ( in 2d: x-y-x-y ... )
(3) each node containts a point P ( in 2d: (x,y) )
(4) to find (x',y'), only need to compare coord from the cutting dim. 
   if lesser, go left subtree,  
   if equal or greater, go right subtree.

cutting dimension cd is related to tree level L by:   
cd = L%dim,  where dim is the dimension of the problem

-----------------------
insert algorithm:
-----------------------
recursion is needed for insert，

insert(Point x, KDNode t, int cd)  // insert point x in KD Tree with root node t, with cutting dimension of node t cd.
{
  if (t == NULL) t = new KDNode(x)
  else if ( x == t.data) return error  // duplicate value
  else if ( x[cd] < t.data[cd]
    t.left = insert(x, t.left, (cd+1)%dim
  else 
    t.right = insert(x, t.right, (cd+1)%dim)
  return t
}


-----------------------
find min algorithm
-----------------------
find the point with smallest value in dth dim.

idea:
recursively traverse the tree,
(1) if cd == d, then minimum can't be in the right subtree, we recurse on the left subtree if it's not null.  
    when left subtree is null, then minimum should be current node
(2) if cd != d, minimum could be in either subtree, so we need to recurse on both subtree and also compare to current node


Point findmin(KDNode t, int d, int cd)
{
  if (t == NULL) return NULL
  
  if (cd == d) { 
     if (t.left == NULL) return t.data
     else return findmin(t.left, d, (cd+1)%dim)
  } else {
     return min(findmin(t.left, d, (cd+1)%dim), find min(t.right, d, (cd+1)%dim), t.data)
  }
}


--------------------------
delete algorithm
--------------------------
general idea: 

assume we want to delete node A,  the cutting dimension of A is cd.
then if A's right subtree is not empty, we find the minimum node in cd in right subtree, and put it in place of 
A, then delete that node in right subtree.

if A's right subtree is empty, we need to find the minimum node in cd in left subtree, put it in place of A, then delete 
that node in left subtree, then move left subtree to right subtree.

The code is as bellow:

Point delete(Point x, KDNode t, int cd)
{
  if (t == NULL) return error
  next_cd = (cd + 1)%dim
  
  if (x == t.data) {  // this is the node
     if (t.right != NULL) {
        t.data = findmin(t.right, cd, next_cd)
        t.right = delete(x, t, next_cd)
     
     } else if (t.left != NULL) {
        t.data = findmin(t.left, cd, next_cd)
        t.right = delete(t.left, t, next_cd)
        t.left = NULL
      
     } else {
        t = NULL;  // just remove t
     }
   
  } else if (x[cd] < t.data[cd]) { // need to delete in left subtree
    
    t.left = delete(x, t.left, next_cd)
  } else {  // need to delete in right subtree
    t.right = delete(x, t.right, next_cd)
  }
  
  return t
}


---------------------------
NN search
------------------------
general idea:
traverse the KD tree, keep cloest point C found so far,  prune subtrees once their bounding 
box say they could not contain closer points.  Also search subtree that is more promising first.

the code is as bellow:

best, best_dist are global var

void NN(Point Q, kdNode t, int cd, Rect BB)  // BB is bounding box
{
   if (t == NULL || distance(Q, BB) > best_dist) return
   
   dist = distance(Q, t.data)
   if (dist < best_dist) {
     best = t.data
     best_dist = dist
   }
   
   next_cd = (cd + 1)%dim
   
   // visit subtree
   if (Q[cd] < t.data[cd]) { // we search left tree first
     NN(Q, t.left, next_cd, BB.trimLeft(cd, t.data) )  // BB of left subtree
     NN(Q, t.right, next_cd, BB.trimRight(cd, t.data))
   } else {  // we search right tree first
     NN(Q, t.right, next_cd, BB.trimRight(cd, t.data))
     NN(Q, t.left, next_cd, BB.trimLeft(cd, t.data) ) 
   }

}