What is a purely functional data structure for quickly finding the nearest neighbor in n-dimensional space?

Question

I am looking for a purely functional data structure with an API, for example:

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 variants of this, providing quick insertion, deletion and query for the nearest element in n-dimensional space. What is this data structure?

Answer 1

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

Answer 2

For n-dimensional space, there is also kd tree .