Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Oct 16, 2024

HERE IS MY CODE OF 2D TREE IMPLEMENTATION FORM THE PRINCETON https://www.cs.princeton.edu/courses/archive/fall14/cos226/assignments/kdtree.html package a05; import java.util.List; import java.util.ArrayList; import edu.princeton.cs.algs4.Point2D; import edu.princeton.cs.algs4.Queue; import edu.princeton.cs.algs4.RectHV; import

HERE IS MY CODE OF 2D TREE IMPLEMENTATION FORM THE PRINCETON

https://www.cs.princeton.edu/courses/archive/fall14/cos226/assignments/kdtree.html

package a05;

import java.util.List; import java.util.ArrayList;

import edu.princeton.cs.algs4.Point2D; import edu.princeton.cs.algs4.Queue; import edu.princeton.cs.algs4.RectHV; import edu.princeton.cs.algs4.StdOut;

class KdTreeST {

private Node root; private int size;

private class Node { private final Point2D p; private final RectHV r; private Node left; private Node right; public Value val;

public Node(Point2D point, RectHV rect) { if (point == null || rect == null) { throw new NullPointerException(); }

this.p = point; this.r = rect;

} }

public KdTreeST() { this.root = null; this.size = 0; } // construct an empty symbol table of points

public boolean isEmpty() { return this.size == 0; } // is the symbol table empty?

public int size() { return this.size; } // number of points

// associate the value val with point p public void put(Point2D p, Value val) { if (p == null || val == null) { throw new NullPointerException(); } if (root == null) { root = new Node(p, new RectHV(0, 0, 1, 1)); size++; return; } put(root, p, val, true); }

// Helper method private void put(Node node, Point2D p, Value val, boolean isVert) { if (node.p.equals(p)) { node.val = val; } // Updates value at point

RectHV childRect = node.r; Node childNode;

if (isVert) { if (p.x() < node.p.x()) { childNode = node.left; childRect = new RectHV(childRect.xmin(), childRect.ymin(), node.p.x(), childRect.ymax()); } else { childNode = node.right; childRect = new RectHV(node.p.x(), childRect.ymin(), childRect.xmax(), childRect.ymax()); } } else { if (p.x() < node.p.x()) { childNode = node.left; childRect = new RectHV(childRect.xmin(), childRect.ymin(), childRect.xmax(), node.p.y()); } else { childNode = node.right; childRect = new RectHV(childRect.xmin(), node.p.y(), childRect.xmax(), childRect.ymax()); } }

if (childNode == null) { childNode = new Node (p, childRect); size++; } else { put(childNode, p, val, !isVert); } }

public Value get(Point2D p) { return get(root, p, true); }

// value associated with point p private Value get(Node node, Point2D p, boolean useX) { if (node == null) { // point not found return null; }

if (p.equals(node.p)) { // found the point return node.val; }

double cmp = (useX ? p.x() - node.p.x() : p.y() - node.p.y());

if (cmp < 0) { // go left return get(node.left, p, !useX); } else { // go right return get(node.right, p, !useX); } }

public boolean contains(Point2D p) { return contains(root, p, true); }

private boolean contains(Node x, Point2D p, boolean useX) { if (x == null) { return false; } if (x.p.equals(p)) { return true; } double cmp; if (useX) { cmp = p.x() - x.p.x(); } else { cmp = p.y() - x.p.y(); } if (cmp < 0) { return contains(x.left, p, !useX); } else { return contains(x.right, p, !useX); } }

// all points in the symbol table public Iterable points() { List pointList = new ArrayList<>(); inorder(root, pointList); return pointList; }

private void inorder(Node x, List pointList) { if (x == null) { return; } inorder(x.left, pointList); pointList.add(x.p); inorder(x.right, pointList); }

public Iterable range(RectHV rect) { Queue pointsInRange = new Queue(); range(root, rect, pointsInRange); return pointsInRange; }

private void range(Node node, RectHV rect, Queue pointsInRange) { if (node == null) { return; } if (rect.contains(node.p)) { pointsInRange.enqueue(node.p); } if (node.left != null && rect.intersects(node.left.r)) { range(node.left, rect, pointsInRange); } if (node.right != null && rect.intersects(node.right.r)) { range(node.right, rect, pointsInRange); } } public Point2D nearest(Point2D p) { if (p == null) { throw new NullPointerException(); }

if (isEmpty()) { return null; }

return nearest(root, p, root.p, true); }

private Point2D nearest(Node node, Point2D p, Point2D closest, boolean useX) { if (node == null) { return closest; }

// If this node is closer than the current closest node, update the closest node if (node.p.distanceSquaredTo(p) < closest.distanceSquaredTo(p)) { closest = node.p; }

// Check whether to visit left or right subtree Node firstNode = node.left; Node secondNode = node.right;

if ((useX && (p.x() >= node.p.x())) || (!useX && (p.y() >= node.p.y()))) { firstNode = node.right; secondNode = node.left; }

// Check the closest node in the first subtree closest = nearest(firstNode, p, closest, !useX);

// If the other subtree could still contain a closer point, check it if (secondNode != null) { if (useX) { if ((p.x() - node.p.x()) * (p.x() - node.p.x()) < closest.distanceSquaredTo(p)) { closest = nearest(secondNode, p, closest, !useX); } } else { if ((p.y() - node.p.y()) * (p.y() - node.p.y()) < closest.distanceSquaredTo(p)) { closest = nearest(secondNode, p, closest, !useX); } } }

return closest; }

public static void main(String[] args) {

KdTreeST st = new KdTreeST(); Point2D p1 = new Point2D(0.5, 0.5); Point2D p2 = new Point2D(0.25, 0.25); Point2D p3 = new Point2D(0.75, 0.75); Point2D p4 = new Point2D(0.1, 0.1); Point2D p5 = new Point2D(0.9, 0.9);

st.put(p1, 1); st.put(p2, 2); st.put(p3, 3); st.put(p4, 4);

// Test get() StdOut.println("Value at point p1: " + st.get(p1)); StdOut.println("Value at point p2: " + st.get(p2)); StdOut.println("Value at point p3: " + st.get(p3)); StdOut.println("Value at point p4: " + st.get(p4)); StdOut.println("Value at non-existent point p5: " + st.get(p5));

// Test contains() StdOut.println("Contains point p1? " + st.contains(p1)); StdOut.println("Contains point p2? " + st.contains(p2)); StdOut.println("Contains point p3? " + st.contains(p3)); StdOut.println("Contains point p4? " + st.contains(p4)); StdOut.println("Contains point p5? " + st.contains(p5));

// Test range() RectHV rect = new RectHV(0.0, 0.0, 0.6, 0.6); Iterable range = st.range(rect); StdOut.println("Points in range " + rect.toString() + ":"); for (Point2D p : range) { StdOut.println(p.toString()); }

}

HERE IS THE OUT PUT OF MY TEST CLIENT, IT IS WRONG: Value at point p1: null Value at point p2: null Value at point p3: null Value at point p4: null Value at non-existent point p5: null Contains point p1? true Contains point p2? false Contains point p3? false Contains point p4? false Contains point p5? false Points in range [0.0, 0.6] x [0.0, 0.6]: (0.5, 0.5)

HERE IS A TEST RESULT FROM A WEBSITE PROVIDED BY MY TUTOR WHICH I DONT HAVE ACCESS TO:

= = = = = = = = = = RUNNING TESTS FOR PointST = = = = = = = = = = =

JUnit version 4.12

.....E...E..E..E......E.E.E.E..E..E.E...E

Time: 0.065

There were 12 failures:

1) contains_ExistingKeys(a05.KdTreeST_Test)

java.lang.AssertionError: The method contains should return true for all points of the KdTreeST.

at org.junit.Assert.fail(Assert.java:88)

at org.junit.Assert.assertTrue(Assert.java:41)

at a05.KdTreeST_Test.contains_ExistingKeys(KdTreeST_Test.java:163)

at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)

at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)

at java.base/java.lang.reflect.Method.invoke(Method.java:566)

at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)

at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)

at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:52)

at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)

at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:26)

at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)

at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)

at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)

at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)

at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)

at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)

at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)

at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)

at org.junit.runners.ParentRunner.run(ParentRunner.java:363)

at org.junit.runners.Suite.runChild(Suite.java:128)

at org.junit.runners.Suite.runChild(Suite.java:27)

at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)

at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)

at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)

at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)

at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)

at org.junit.runners.ParentRunner.run(ParentRunner.java:363)

at org.junit.runner.JUnitCore.run(JUnitCore.java:137)

at org.junit.runner.JUnitCore.run(JUnitCore.java:115)

at org.junit.runner.JUnitCore.runMain(JUnitCore.java:77)

at org.junit.runner.JUnitCore.main(JUnitCore.java:36)

2) nearest_anyPoint(a05.KdTreeST_Test)

java.lang.AssertionError: expected:<(2.0, 2.0)> but was:<(0.0, 0.0)>

at org.junit.Assert.fail(Assert.java:88)

at org.junit.Assert.failNotEquals(Assert.java:834)

at org.junit.Assert.assertEquals(Assert.java:118)

at org.junit.Assert.assertEquals(Assert.java:144)

at a05.KdTreeST_Test.nearest_anyPoint(KdTreeST_Test.java:249)