I understand how it works. But the question is why it works. This data structure is based on string metrics, it can use the Levenstein distance metric, for example. Here's the article talking about this: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

My question is this. The author of the article says: "Call the resultant distance d. Because we know the triangle inequality holds, all our results must have at most distance d+n and at least distance d-n from test."

I don't understand why the search segment is [d-n, d+n].

I'd really appreciate if someone explained.

I know that from the triangle inequality we have:

Combining the last 2, we get c\geqslant|a+b|.

But I don't understand what to associate a,b,c with. And why does the author say that we need to search in the segment [d-N,d-N] instead of [|d-N|,d+N].