Class KdTree

05Lab-Kd Tree/KdTree.java:15–191

import java.util.ArrayList;

public class KdTree {
    private Node root;
    private int n;

    // construct an empty set of points
    public KdTree() {
        root = null;
        n = 0;
    }

    // is the set empty?
    public boolean isEmpty() {
        return root == null;
    }

    // number of points in the set
    public int size() {
        return n;
    }

    // add the point to the set (if it is not already in the set)
    public void insert(Point2D p) {
        if (p == null) throw new IllegalArgumentException();
        if (contains(p)) return;
        root = put(root, p, true, 0, 0, 1, 1);
        n++;
    }

    private Node put(Node x, Point2D p, boolean isXPartition, double xmin, double ymin, double xmax,
                     double ymax) {
        if (x == null) return new Node(p, new RectHV(xmin, ymin, xmax, ymax));
        int cmp = isXPartition ? Double.compare(p.x(), x.p.x())
                               : Double.compare(p.y(), x.p.y());

        if (cmp < 0) {
            if (isXPartition) xmax = x.p.x();
            else ymax = x.p.y();
            x.left = put(x.left, p, !isXPartition, xmin, ymin, xmax, ymax);
        }
        else {
            if (isXPartition) xmin = x.p.x();
            else ymin = x.p.y();
            x.right = put(x.right, p, !isXPartition, xmin, ymin, xmax, ymax);
        }
        return x;
    }

    // does the set contain point p?
    public boolean contains(Point2D p) {
        if (p == null) throw new IllegalArgumentException();
        return get(root, p, true) != null;
    }

    private Point2D get(Node x, Point2D p, boolean isXPartition) {
        if (p == null) throw new IllegalArgumentException();
        if (x == null) return null;
        if (p.compareTo(x.p) == 0) return x.p;
        int cmp = isXPartition ? Double.compare(p.x(), x.p.x())