Using a binary search tree to implement a set of points [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

My assignment asks me to implement a point set API class using a binary search tree, using java.util.TreeSet. the PointSet API outline is shown below:

public class PointSET {
    public PointSET() {}                               // construct an empty set of points
    public boolean isEmpty() {}                        // is the set empty?
    public int size() {}                               // number of points in the set
    public void insert(Point2D p) {}                   // add the point p to the set (if it is not already in the set)
    public boolean contains(Point2D p) {}              // does the set contain the point p?
    public Collection<Point2D> range(RectHV rect) {}   // all points in the set that are inside the rectangle
    public Point2D nearest(Point2D p) {}               // a nearest neighbor in the set to p; null if set is empty
}

• The Point2 object is a simple point with x and y coordinates and a few other methods to calculate distances between two points.
• The RectHV object represents a rectangle used in a range search for points within the rectangle.

I guess I'm unsure of how to implement this API class in a BST. We've learned about BST's in class, but only in a broad sense; what they are and the postorder/preorder/inorder ways to search through them.

I'm also confused as to what an API is in and of itself. What makes this an API as opposed to something that is not an API?

What does "implementing" the API involve? and how do I use java.util.TreeSet to do it?

I would appreciate any help.

Answer 1

You can think of an application programming interface (API) as a contract. It specifies the way objects interact with each other.

In order to illustrate what an API is, consider the interface Dictionary:

public interface Dictionary {
    List<String> loadWords();
}

The interface Dictionary establish the contract (API) that all dictionary implementations have to follow. Two examples of dictionaries implementation could be:

public class TextFileDictionary implements Dictionary {
    public List<String> loadWords() {
        // load words from a text file and return them
        return words;
    }
}

public class DatabaseDictionary implements Dictionary {
    public List<String> loadWords() {
        // load words from database and return them
        return words;
    }
}

Let's take now your PointSET class as an example. As you can see, it has a bunch of methods that define the behavior of an object of the type PointSET.

public class PointSET {

    // private ... <- your data structure goes here.

    public PointSET() {}
    public boolean isEmpty() {}
    public int size() {}
    public void insert(Point2D p) {}
    public boolean contains(Point2D p) {}
    public Collection<Point2D> range(RectHV rect) {}
    public Point2D nearest(Point2D p) {}
}

As @alexBrand pointed out, a good starting point is to define your data structure. In your case, the obvious choice is a BST. Then, in order to be coherent with the provided API, you are going to have to manipulate your data structure(s) to implement the expected behavior of PointSET.