IN JAVA, please help me write a code for a Kd tree and do all the TO DO list. Pl
ID: 3881787 • Letter: I
Question
IN JAVA, please help me write a code for a Kd tree and do all the TO DO list. Please make sure the program compiles correctly.
___________________________________________________________________________________________________________
package algs32.kdtree;
import algs12.Point2D;
import algs13.Queue;
import stdlib.*;
/* a set of points implemented as kd-tree */
public class KdTree {
private static class Node {
// TODO
}
private Node root;
/* construct an empty set of points */
public KdTree() {
// TODO -- maybe nothing to do here... in which case you can remove this and use the default constructor
}
/* is the set empty? */
public boolean isEmpty() {
// TODO
return false;
}
/* add the point p to the set (if it is not already in the set) */
public void insert(Point2D p) {
// TODO
}
/* does the set contain the point p? */
public boolean contains(Point2D target) {
// TODO
return false;
}
/* all points in the set that are inside the target rectangle */
public Iterable<Point2D> range(RectHV target) {
// TODO
return new Queue<>();
}
/* a nearest neighbor to target point; null if empty */
public Point2D nearest(Point2D target) {
// TODO
return new Point2D (0, 0);
}
/* draw all of the points to standard draw */
/* for x-node, use red line to draw the division between left/right */
/* for y-node, use blue line to draw the division between top/bottom */
/* see the writeup for examples */
public void draw() {
// TODO
}
/* some test code */
public void toGraphviz() { GraphvizBuilder.nodesToFile (root); }
private static void insert5Points (KdTree kdtree, double xoffset, double yoffset) {
kdtree.insert (new Point2D (0.7 + xoffset, 0.2 + yoffset));
kdtree.insert (new Point2D (0.5 + xoffset, 0.4 + yoffset));
kdtree.insert (new Point2D (0.2 + xoffset, 0.3 + yoffset));
kdtree.insert (new Point2D (0.4 + xoffset, 0.7 + yoffset));
kdtree.insert (new Point2D (0.9 + xoffset, 0.6 + yoffset));
}
public static void main (String[] args) {
KdTree kdtree = new KdTree ();
insert5Points (kdtree, 0.0, 0.0); // after this there should be 5 points
insert5Points (kdtree, 0.0, 0.0); // after doing it twice there should still be 5
insert5Points (kdtree, 0.1, 0.0); // this should add 5 more points
insert5Points (kdtree, 0.0, 0.1); // this should add 5 more points
// kdtree.insert (new Point2D(0.15, 0.18));
// kdtree.insert (new Point2D(0.86, 0.26));
// kdtree.insert (new Point2D(0.70, 0.11));
// kdtree.insert (new Point2D(0.16, 0.01));
// kdtree.insert (new Point2D(0.62, 0.95));
// kdtree.insert (new Point2D(0.98, 0.04));
// kdtree.insert (new Point2D(0.87, 0.79));
// kdtree.insert (new Point2D(0.83, 0.21));
// Point2D mid = new Point2D (0.5, 0.5);
// Point2D less = new Point2D (0.5, 0.4);
// Point2D more = new Point2D (0.5, 0.6);
// kdtree.insert (mid);
// kdtree.insert (less);
// kdtree.insert (more);
// StdOut.println (kdtree.contains (less));
// StdOut.println (kdtree.contains (more));
// StdOut.println (kdtree.range (new RectHV (0.5, 0.4, 0.5, 0.6)));
// StdOut.println (kdtree.nearest (less));
// StdOut.println (kdtree.nearest (more));
StdOut.println (kdtree);
kdtree.toGraphviz ();
kdtree.draw ();
}
}
Explanation / Answer
Hi There,
I have completed implemented the insert Logic and also introduced some new variables to make our life easier, which i is apparent in the program. I hope K-Dimensional tree logic is clear for you. It will be clear by the below program.
Point2D class was not given hence made my own. This logic is working fine, I have checked by debugging in my compiler.
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package kdtree;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author abhiramagopaladasa
*/
public class KdTree {
enum LEVEL {
XALIGNED, YALIGNED
}
private static class Node {
// TODO
LEVEL level;//self explanatory
Point2D point;
Node left;
Node right;
public void setPoint(Point2D point, LEVEL level) {
this.point = point;
}
public Point2D getPoint() {
return point;
}
public Node(Point2D point, Node left, Node right, LEVEL level) {
this.point = point;
this.left = left;
this.right = right;
}
Node(Point2D point) {
this.point = point;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public Node(Point2D point, LEVEL level) {
this.level = level;
this.point = point;
}
}
private Node root;
/* construct an empty set of points */
public KdTree() {
// TODO -- maybe nothing to do here... in which case you can remove this and use the default constructor
}
/* is the set empty? */
public boolean isEmpty() {
if (root == null) {
return true;
} else {
return false;
}
}
/* add the point p to the set (if it is not already in the set) */
public void insert(Point2D p) {
if (root == null) {//if root null insert in the root
root = new Node(p, LEVEL.XALIGNED);
} else {
Node n = new Node(p);//new Node is Y aligned
if (isToGoInLeft(root, n, root.level)) {//checking if new node has to go in left, here root is X aligned
insertInLeftSubTree(root, n);//if yes then insert in left subtree
} else {
insertInRightSubTree(root, n);//else insert in right sub tree
}
}
}
public void insertInRightSubTree(Node right, Node neww) {
if (right.getRight() == null) {//if this nodes right sub tree is null,, insert here itself and return
right.setRight(neww);//Setting alternate alignments below
if (right.level == LEVEL.YALIGNED) {
neww.level = LEVEL.XALIGNED;
} else {
neww.level = LEVEL.YALIGNED;
}
} else {//if not null the same procedure of checking happens thru recursion
if (isToGoInRight(right.getRight(), neww, right.level)) {//you can use isToGoInLeft also here up to you.
insertInRightSubTree(right.getRight(), neww);
} else {
insertInLeftSubTree(right.getLeft(), neww);
}
}
}
public void insertInLeftSubTree(Node left, Node neww) {
if (left.getLeft() == null) {//same logic as above
left.setLeft(neww);
if (left.level == LEVEL.XALIGNED) {
neww.level = LEVEL.YALIGNED;
} else {
neww.level = LEVEL.XALIGNED;
}
} else {
if (isToGoInLeft(left.getLeft(), neww, left.level)) {
insertInLeftSubTree(left.getLeft(), neww);
} else {
insertInRightSubTree(left, neww);
}
}
}
public boolean isToGoInLeft(Node parent, Node toBeInserted, LEVEL levelOfParent) {
if (levelOfParent == LEVEL.XALIGNED && parent.getPoint().getX() > toBeInserted.getPoint().getX()) {
return true;//if parent is left aligned according to the comparison go to the left.
} else if (levelOfParent == LEVEL.YALIGNED && parent.getPoint().getY() > toBeInserted.getPoint().getY()) {
return true;//if parent is YAligned do accordingly
} else {
return false;
}
}
public boolean isToGoInRight(Node parent, Node toBeInserted, LEVEL level) {
return !isToGoInLeft(parent, toBeInserted, level);
}
/* does the set contain the point p? */
public boolean contains(Point2D target) {
//simply get all the nodes and make an arraylist and check for the values.
return false;
}
/* all points in the set that are inside the target rectangle */
// public Iterable<Point2D> range(RectHV target) {
// // TODO
// return new Queue<>();
// }
/* a nearest neighbor to target point; null if empty */
public Point2D nearest(Point2D target) {
// TODO
return new Point2D(0, 0);
}
/* draw all of the points to standard draw */
/* for x-node, use red line to draw the division between left/right */
/* for y-node, use blue line to draw the division between top/bottom */
/* see the writeup for examples */
public void draw() {
// TODO
}
/* some test code */
public void toGraphviz() {
// GraphvizBuilder.nodesToFile(root);
}
private static void insert5Points(KdTree kdtree, double xoffset, double yoffset) {
kdtree.insert(new Point2D(0.7 + xoffset, 0.2 + yoffset));
kdtree.insert(new Point2D(0.5 + xoffset, 0.4 + yoffset));
kdtree.insert(new Point2D(0.2 + xoffset, 0.3 + yoffset));
kdtree.insert(new Point2D(0.4 + xoffset, 0.7 + yoffset));
kdtree.insert(new Point2D(0.9 + xoffset, 0.6 + yoffset));
}
public static void main(String[] args) {
KdTree kdtree = new KdTree();
insert5Points(kdtree, 0.0, 0.0); // after this there should be 5 points
insert5Points(kdtree, 0.0, 0.0); // after doing it twice there should still be 5
insert5Points(kdtree, 0.1, 0.0); // this should add 5 more points
insert5Points(kdtree, 0.0, 0.1); // this should add 5 more points
// kdtree.insert (new Point2D(0.15, 0.18));
// kdtree.insert (new Point2D(0.86, 0.26));
// kdtree.insert (new Point2D(0.70, 0.11));
// kdtree.insert (new Point2D(0.16, 0.01));
// kdtree.insert (new Point2D(0.62, 0.95));
// kdtree.insert (new Point2D(0.98, 0.04));
// kdtree.insert (new Point2D(0.87, 0.79));
// kdtree.insert (new Point2D(0.83, 0.21));
// Point2D mid = new Point2D (0.5, 0.5);
// Point2D less = new Point2D (0.5, 0.4);
// Point2D more = new Point2D (0.5, 0.6);
// kdtree.insert (mid);
// kdtree.insert (less);
// kdtree.insert (more);
// StdOut.println (kdtree.contains (less));
// StdOut.println (kdtree.contains (more));
// StdOut.println (kdtree.range (new RectHV (0.5, 0.4, 0.5, 0.6)));
// StdOut.println (kdtree.nearest (less));
// StdOut.println (kdtree.nearest (more));
// StdOut.println (kdtree);
kdtree.toGraphviz();
kdtree.draw();
}
}
There was a lot of hard work for this please rate.