What is a purely functional data structure for fast nearest neighbor search on n-dimensional space?

Question

I'm looking for a purely functional data structure with an API such as:

insert  :: Vector n Int -> Struct n -> Struct n
remove  :: Vector n Int -> Struct n -> Struct n
nearest :: Vector n Int -> Struct n -> Vector n Int

Or some variation of that, providing fast insertion, removal and query for the nearest element in an n-dimensional space. What is that data-structure?

Answer 1

There is a natural generalization of quadtrees from two dimensions to n.

Answer 2

For an n-dimensional space, there is also the k-d tree.