search2007.01.23 18:19

from :

Spatial Data Structures

K-D Trees, PR Quadtrees

K-Dimensional Trees work with "k" dimensions not just 1 dimension as BSTs do
Point Regional (PR) Quadtrees have 2k branches at each node given data in a k-dimensional space
Multi-dimensional queries

Range queries


Geographic Information Systems (GIS)
Computer Graphics


K-D Trees: a Generalization of BSTs

Binary Search Trees search using 1 key

Some data naturally contain multiple dimensions

Given k-dimensional data, a K-D tree indexes dimension 0 of the data at level 0, dimension 1 at level 1, etc.

Figure 13.8 (b) from book


Definition: the discriminator is the search key at each level i

calculation of discriminator : i mod k

Given 3-dimensional data indexed by (x,y,z),

y is the discriminator if the level number of the k-d tree is 10 since 10 mod 3 = 1


K-D Trees ….

At ith level of the tree, discriminator indexes the tree exactly as for a BST: select i mod kth coordinate of data item and compare it with i mod kth coordinate of value stored at node of K-D tree.

If (data value < node value)



    take-right-branch // >= case

For 2-D space, K-D tree subdivides space into rectangles. The direction of subdivision alternates among the dimensions:


Figure 13.8 (a) from book


K-D Tree Find Operation

Simple modification of BST search.

Must determine correct discriminator at each level (= level number mod k) to find out what coordinate of key to use for comparison at that level

KDNode* KD::Kdfindhelp(KDNode* rt, ELEM val, int lev, int K) const


   //lev: current level (mod K); K: number of dimensions

   //dkey(val, i) returns the key value of val for dimension i

   if (rt == NULL)

      return NULL; // Empty tree

   else if (val == rt->value)

      return rt; // Found it

   else if (dkey(val, lev) < dkey(rt->value, lev))

      return Kdfindhelp(rt->left, val, (lev+1) % K, K);


      return Kdfindhelp(rt->right, val, (lev+1) % K, K);


Example: find (55, 80) in

Figure 13.8 (b) from book


Deleting Nodes in a K-D Tree

Deletion similar to BST but slightly harder.

Step 1: find node to be deleted

Step 2: two cases must be handled

No children - replace ptr to node by NULL

Has children - replace node by minimum node in right subtree using KDfindmin (harder to find than in a BST!)

If no right subtree exists, then first move left subtree to become right subtree and proceed with usual delete procedure using KDfindmin

Special note: node found by KDfindmin may occur in middle of tree. Recursive call to the delete routine must be used to replace it (careful!)



Must search both left and right subtrees to find minimum value for a given discriminator

KDNode* KD::KDfindmin(KDNode* rt, int discrim, int level, int K)


    // discrim: discriminator key used for minimum search

    // level: current level(mod K); K: # of levels in key

    KDNode *temp1, *temp2;

    if (rt == NULL)

      return NULL;

    temp1 = KDfindmin(rt->left, discrim, (level+1)%K, K)

    if (discrim != level)


       //Min val could be on l/r side

       temp2=KDfindmin(rt->right, discrim, (level+1)%K,K);

       if((temp1 == NULL) || ((temp2 != NULL) && (dkey(temp2->value,discrim) <


           temp1 = temp2;   //in line above, rt subtree has smaller key value


    // temp1 has the smallest value in children (if any)

    if ((temp1 == NULL) || (dkey(rt->value,discrim) <


          return rt;


         return temp1;


Now delete C(70, 10) from

Figure 13.8 (b) from book


K-D Tree Range Query

Problem: find all k-dimensional points within distance 'D' of point P

Must search through K-D tree using Euclidean distance formula

If any coordinate in the K-D tree is more than distance 'D' away from point P's corresponding coordinate, then no need to search one of the subtrees below that node.

Example: if D=10, y-coordinate of node is being examined and is 13 less than the y-coordinate of P, then no search needed of left subtree below that node

void KDRegionSearch(KDNode* rt, ELEM val, int D, int level, int K)


    // val: search key; D: search radius;

    // level: current level (mod K); K: # of dimensions

    // Check if record at rt is in circle

    if(InCircle(key(val), D, key(rt->value)))

       printout(rt->value);//Do appropriate action with node

    if(dkey(rt->value,level)>(dkey(val,level)-D)      //Go left

       KDRegionSearch(rt->left, val, D, (level+1)%K,K);

    if(dkey(rt->value,level)<(dkey(val,level)+D))     //Go right

       KDRegionSearch(rt->right, val, D, (level+1) % K, K);


Function 'InCircle' uses Euclidean distance to test if point is within distance D of query point

Posted by myditto

티스토리 툴바