Creating a KDTree that inserts and visualizes logically

Question

So I was tasked with this homework assignment of constructing a KdTree that has nodes that are type Point2D. First starting on the insert method to make sure nodes were being placed accordingly by x-axis, then constructing the draw() method that would work in unison with it.

I've done that, and finished some of the other methods while I wasn't pulling my hair out from trying to figure out the first two methods, but here is the my problem..

My construction works for every test, visual & performance wise, but I still don't think it's right.

package algs32.kdtree;
import algs12.Point2D;
import algs13.Queue;
import stdlib.*;

public class KdTree {

    private static class KNode {
        private KNode left, right;
        private boolean vertical;
        private Point2D key;

        public KNode(final Point2D key, final boolean v) {
            this.key = key;
            vertical = v;
        }
    }
    private static final RectHV BOUNDRY = new RectHV(0, 0, 1, 1);
    private KNode root;
    private int size;

    public KdTree() {}

    public int size() { return size; }

    public boolean isEmpty() { return size == 0; }


    public void insert(Point2D p) { root = insert(root, p, true); }

    private KNode insert(KNode node, final Point2D p, final boolean vertical) {
        if (p == null) { throw new IllegalArgumentException(); }
        if (node == null) {
            size++;
            node = new KNode(p, vertical);
            return node;
        }
        if (p.equals(node.key)) { return node; }
        if (node.vertical && p.x() < node.key.x() || !node.vertical && p.y() < node.key.y()) {
            node.left = insert(node.left, p, !node.vertical);
        }
        else {
            node.right = insert(node.right, p, !node.vertical);
        }
        return node;
    }

    public void draw() { draw (root, BOUNDRY); }

    private void draw (KNode node, RectHV area) {
        if (node==null) return;

        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.setPenRadius(.007);
        node.key.draw();

        StdDraw.setPenRadius(.002);
        if (node.vertical) {
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(node.key.x(), area.ymin(), node.key.x(), area.ymax());
        } else {
            StdDraw.setPenColor(StdDraw.BLUE);
            StdDraw.line(area.xmin(), node.key.y(), area.xmax(), node.key.y());
        }
        draw(node.left, LR(area, node));
        draw(node.right, RR(area, node));
    }

    private static RectHV LR(RectHV area, KNode node) {
        if (node.vertical) {
            RectHV newarea = new RectHV(area.xmin(), area.ymin(), node.key.x(), area.ymax());
            return area;
        } else {// BR for horizontal division
            RectHV newarea = new RectHV(area.xmin(), area.ymin(), area.xmax(), node.key.y());
            return area;
        }
    }

    private static RectHV RR(RectHV area, KNode node) {
        if (node.vertical) {
            RectHV newarea = new RectHV(node.key.x(), area.ymin(), area.xmax(), area.ymax());
            return newarea;
        } else {// TR for horizontal division
            RectHV newarea = new RectHV(area.xmin(), node.key.y(), area.xmax(), area.ymax());
            return area;
        }
    }

Graph

Here is a visualization of my code. The point numbers are the order there were inserted. As you can see, Point 1 is the root, (inserted first), Point 2 goes to the left because it has a smaller x coordinate, Point 3 to the right etc.

Then we get to point 4, 5, 6, & 7. Point 4 is vertical because its depth is even, point 5 should be as well. It's x point is smaller than point 1, so it goes to the left, its x point is bigger than point 2, so it goes to the right, becoming point 3s' right child, which should make its depth even, thus vertical. Same problem for the right subtree.

Any extra explanation would be very much welcome.

Creating a KDTree that inserts and visualizes logically

Answers (1)

Related Questions