Spatial C++ Library
Generic MultiDimensional Containers and Spatial Operations

Functions with linear time complexity, noted , will return their output in an amount of time proportional to the number of element in the tree.
It's a very hard target to reach for most kd tree algorithms, due to the nature of the tree, but some functions that may use arrays underneath may be able to reach it.