kdtree icon indicating copy to clipboard operation
kdtree copied to clipboard

FindLargest, FindSmallest are O(n)

Open minkezhang opened this issue 3 years ago • 0 comments

FindLargest, FindSmallest are used when removing a node from the k-d tree. These functions do not take into account the axis of the currently expanded node

https://github.com/kyroy/kdtree/blob/70830f883f1d7bdae54d5032c6d4473349e0cfa4/kdtree.go#L357-L368

Given we are calling node.Remove recursively, this seems to suggest our actual runtime complexity to be O(nlogn), whereas general BST remove should take O(n).

As per Wikipedia, if we are okay with O(nlogn) complexity, we can alternatively just rebuild the node.

Alternatively, we can tombstone the node instead, which optimizes Remove for a slightly larger lookup time.

minkezhang avatar Oct 23 '21 22:10 minkezhang