FindLargest, FindSmallest are O(n)

[minkezhang]

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

kdtree/kdtree.go

Lines 357 to 368 in 70830f8

	func (n *node) FindLargest(axis int, largest *node) *node {
	if largest == nil || n.Dimension(axis) > largest.Dimension(axis) {
	largest = n
	}
	if n.Left != nil {
	largest = n.Left.FindLargest(axis, largest)
	}
	if n.Right != nil {
	largest = n.Right.FindLargest(axis, largest)
	}
	return largest
	}

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.