Programming Assignment 5 Checklist: Kd-Trees

Frequently Asked Questions

I'm nervous about writing recursive search tree code. How do I even start on KdTreeST.java? As mentioned in lecture, you should use the BST class as a guide. The trickiest part is understanding how the put method works. You do not need to worry about code that involves storing the subtree sizes (since this is used only for ordered symbol table operations).

What should I look out for when I write my recursive geometric BST code? The most common error, by far, is to not rely on your base cases. For example, compare the following two get methods:

private Value get(Node x, Key key) {
  if (x == null) return null;

  int cmp = key.compareTo(x.key);
  if      (cmp < 0)    return get(key, x.left);
  else if (cmp > 0)    return get(key, x.right);
  else                 return x.value  
}
private Value badGet(Node x, Key key) {
  if (x == null) return null;

  int cmp = key.compareTo(x.key);
  if      (cmp < 0)    
     if (x.left == null)   return null;
     else                  return badGet(key, x.left);
  else if (cmp > 0)
     if (x.right == null)  return null;
     else                  return badGet(key, x.right);
  else                 return x.value  
}
In the latter method, extraneous null checks are made that would otherwise be caught by the base case. You should never check any base case before recurring. Trust in the base case.

Seems easy, so I just need to check null in my base case and I'm safe? No! There may be other interesting base cases than simply null checking. Think about when you quit a range search or a nearest neighbor search -- those things should be done as base cases, not as if statements made before a recursive call. Code that does this will be penalized. It's hard to read and hard to debug.

What makes KdTree a hard assignment? How do I make the best use of my time? Debugging performance errors is very hard on this assignment. It is very important that you understand and implement the crucial optimizations listed in the assignment text, namely:

Do not start range search or nearest neighbor until you understand these rules. This kd-tree worksheet is a good way to test your understanding.

Is a point on the boundary of a rectangle considered inside it? Do two rectangle intersect if they have just one point in common? Yes and yes (which is consistent with the implementation of RectHV.java).

Can I use the distanceTo() method in Point2D and RectHV? No, you may use only the subset of the methods listed. You should be able to accomplish the same result by using distanceSquaredTo() instead of distanceTo().

What should I do if a point has the same x-coordinate as the point in a node when inserting or searching in a 2d-tree? Go to the right subtree as specified on the assignment page under Search and insert.

What should I do if a point is inserted twice in the data structure? The data structure represents a symbol table, so you should have at most one value associated with each point.

Why is the method named insert() instead of put()? Good question. We will rename it put() next semester.

How should I scale the coordinate system when drawing? Don't, please keep the default range of 0 to 1.

How should I set the size and color of the points and rectangles when drawing? Use StdDraw.setPenColor(StdDraw.BLACK) and StdDraw.setPenRadius(.01) before drawing the points; use StdDraw.setPenColor(StdDraw.RED) or StdDraw.setPenColor(StdDraw.BLUE) and StdDraw.setPenRadius() before drawing the splitting lines.

What should range() return if there are no points in the range? It should return an Iterable<Point2D> object with zero points.

How much memory does a Point2D object use? For simplicity, assume that each Point2D object uses 32 bytes—in reality, it uses a bit more because of the Comparator instance variables.

How much memory does a RectHV object use? You should look at the code and analyze its memory usage.

I run out of memory when running some of the large sample files. What should I do? Be sure to ask Java for additional memory, e.g., java -Xmx1600m RangeSearchVisualizer input1M.txt.

Testing

Testing. A good way to test KdTree is to perform the same sequence of operations on both the PointST and KdTreeST data types and identify any discrepancies. The sample clients RangeSearchVisualizer.java and NearestNeighborVisualizer.java take this approach.

Sample input files.   The directory kdtree contains some sample input files in the specified format.

The result of calling draw() on the points in circle10.txt should look like the following:

If nearest() is called with p = (.81, .30) the number of nodes visited in order to find that F is nearest is 5.

Starting with circle10k.txt if nearest is called with p = (.81, .30) the number of nodes visited in order to find that K is nearest is 6.

Possible Progress Steps

These are purely suggestions for how you might make progress on KdTreeST.java. You do not have to follow these steps.

  1. Complete the KdTree worksheet. Here is a set of practice problems for the core kd-tree methods. Here are the answers.

  2. Node data type. There are several reasonable ways to represent a node in a 2d-tree. One approach is to include the point, a link to the left/bottom subtree, a link to the right/top subtree, and an axis-aligned rectangle corresponding to the node.
    private class Node {
       private Point2D p;      // the point
       private Value value;    // the symbol table maps the point to this value
       private RectHV rect;    // the axis-aligned rectangle corresponding to this node
       private Node lb;        // the left/bottom subtree
       private Node rt;        // the right/top subtree
    }
    
    Since we don't need to implement the rank and select operations, there is no need to store the subtree size.

  3. Writing KdTreeST. Start by writing isEmpty() and size(). These should be very easy. From there, write a simplified version of insert() which does everything except set up the RectHV for each node. Write the get() and contains() method, and use these to test that insert() was implemented properly. Note that insert() and get() are best implemented by using private helper methods analogous to those found on page 399 of the book or by looking at BST.java. We recommend using orientation as an argument to these helper methods.

    Now add the code to insert() which sets up the RectHV for each Node. Next, write draw(), and use this to test these rectangles. Finish up KdTree with the nearest and range methods. Finally, test your implementation using our interactive client programs as well as any other tests you'd like to conduct.

Optimizations

These are many ways to improve performance of your 2d-tree. Here are some ideas.