kdtree
kdtree copied to clipboard
FindLargest, FindSmallest are O(n)
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.