java-algorithms-implementation icon indicating copy to clipboard operation
java-algorithms-implementation copied to clipboard

Fix KdTree Remove() removes the wrong element under edge condition.

Open chard234 opened this issue 5 years ago • 0 comments

By submitting this pull request I confirm I've read and complied with the below requirements.

  • [x] I have read the Contribution guidelines and I am confident that my PR reflects them.
  • [x] I have followed the coding guidelines for this project.
  • [x] My code follows the skeleton code structure.
  • [x] This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.

The remove() function in the KdTree can remove the wrong element. This is caused by the lesser child being compared on the container wise, not element wise. The container comparison is only done on either x, y, or z attributes, not all of them. Here is an example which results in the remove() function removing the wrong element.

XYZPoint p1 = new XYZPoint(2, 0, 1); 
XYZPoint p2 = new XYZPoint(1, 0, 1);
XYZPoint p3 = new XYZPoint(3, 0, 1);
    	
ArrayList<XYZPoint> points = new ArrayList<XYZPoint>();
points.add(p1);
points.add(p2);
points.add(p3);
    	
KdTree<XYZPoint> kd = new KdTree<XYZPoint>(points);
    	
//Resulting tree:
//Depth 0: k=3 depth=0 id=(2.0, 0.0, 1.0)
//Depth 1: k=3 depth=1 id=(1.0, 0.0, 1.0)	k=3 depth=1 id=(3.0, 0.0, 1.0)
    	
kd.remove(p3);
    	
//Resulting tree:
//Depth 0: k=3 depth=0 id=(2.0, 0.0, 1.0)
//Depth 1: null					k=3 depth=1 id=(3.0, 0.0, 1.0)

The wrong element is removed because at depth 1 the container equivalence will only check the y attribute. As they are the same the lesser is removed even though the greater is the actual element to remove.

chard234 avatar May 29 '19 10:05 chard234