Spatial C++ Library
Generic MultiDimensional Containers and Spatial Operations

Functions with logarithmic time complexity, noted will run and return their output in an amount of time that depends only on the number of elements in the tree.
When a kd tree is properly balanced, inserting a new element in the tree takes logarithmic time operation, since the tree only need to be walked down once: from the root node to the leaf, to find the position were to insert the new element.