search

ubilabs / kd-tree-javascript

JavaScript k-d Tree Implementation
MIT License
638 stars 108 forks source link

Improper node placement #28

Open digdan opened 2 years ago

digdan commented 2 years ago

Using a large dataset ( > 500 ) and removing nodes at random will cause the KDTree to not be segmented correctly. This will cause nodes to not be found correctly.

  1. Create a set of random 2d points
  2. Find the single nearest point within a random 2d point.
  3. Remove the single nearest point.
  4. Repeat from step 2 until you have no more points.

Expected outcome. We are able to remove all records from the tree.

Actual: There are records left, as the tree has made some nodes "unreachable" by not placing them correctly due to the remove function.

Let me know if you want a proof of bug.

digdan commented 2 years ago

To follow up. I have discovered this issue happens when trying to remove a node with the same value in any of the dimensions as another node in the tree.