Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
Linear Time Complexity

Functions with linear time complexity, noted $O(O(n)\,$, 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 k-d tree algorithms, due to the nature of the tree, but some functions that may use arrays underneath may be able to reach it.