sentences:  For constant dimension query time, average complexity is "O"(log "N")  in the case of randomly distributed points, worst case complexity is "O"("kN"^(1-1/"k"))
  Alternatively the R-tree data structure was designed to support nearest neighbor search in dynamic context, as it has efficient algorithms for insertions and deletions such as the R* tree.R-trees can yield nearest neighbors not only for Euclidean distance, but can also be used with other distances.In the case of general metric space, the branch-and-bound approach is known as the metric tree approach.