java-algorithms-implementation
java-algorithms-implementation copied to clipboard
Fix KdTree Remove() removes the wrong element under edge condition.
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}]
, notUpdate README.md
orAdded 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.