k-d 트리 최근접 이웃 탐색 계산기

평면(또는 공간)의 점들을 축을 번갈아 가며 갈라 쌓는 이진 트리입니다. 깊이 0에서는 x 좌표의 중앙값으로 좌우를 나누고, 깊이 1에서는 y 좌표로, 깊이 2에서는 다시 x로 나눕니다. 노드 하나가 점 하나이면서 그 점을 지나는 분할선이기도 합니다. 중앙값으로 가르므로 트리 높이가 log₂n으로 눌립니다.

분할선까지의 거리를 지금까지 찾은 최선 거리와 견줍니다. 질의점에서 분할선까지의 거리가 최선보다 멀면, 반대편의 어떤 점이든 적어도 분할선을 넘어야 하므로 최선보다 가까울 수 없습니다. 그러면 그 가지를 통째로 버립니다. 반대로 분할선이 최선보다 가까우면 반대편에 더 가까운 점이 있을 수 있으므로 반드시 봐야 합니다.

가끔 틀린 답이 나옵니다. 이것이 k-d 트리 구현에서 가장 흔한 버그이고, 무서운 점은 대부분의 입력에서는 맞는 답이 나온다는 것입니다. 질의점이 분할선 가까이 있을 때만 어긋나므로 몇 번 돌려 보고 「잘 되네」 하고 넘어가기 쉽습니다. 이 계산기는 답을 낼 때마다 전수 탐색과 대조한 결과를 함께 보여 줍니다.

2차원에서 점이 고르게 흩어져 있으면 평균 O(log n)입니다. 점 400개에서 대개 스무 개 안팎만 보고 끝납니다. 다만 최악의 경우는 여전히 O(n)이고, 점이 한 직선 위에 몰려 있거나 질의점이 아주 멀리 있으면 이득이 크게 줄어듭니다. 예제의 「한 줄로 몰린 점」으로 확인할 수 있습니다.

차원이 올라가면 가지치기가 듣지 않는 현상입니다. 차원 d에서는 반대편을 확인해야 하는 축이 d개로 늘어 대부분의 가지가 살아남고, 결국 거의 모든 점을 보게 됩니다. 점 개수가 2^d보다 훨씬 많지 않으면 전수 탐색보다 나을 것이 없다는 것이 경험칙이라, 수백 차원인 임베딩 벡터 검색에는 쓰지 않고 근사 최근접(HNSW·LSH)으로 갑니다.

가르는 방식이 다릅니다. k-d 트리는 «점 하나»를 골라 그 점을 지나는 선으로 한 번에 둘로 나누고 축을 번갈아 씁니다. 쿼드트리는 «구역 한가운데»를 기준으로 한 번에 넷으로 나눕니다. k-d 트리는 점 분포에 맞춰 균형이 잡히고, 쿼드트리는 좌표만 보면 어느 칸인지 알 수 있어 삽입·삭제가 쉽습니다.

전송되지 않습니다. 트리를 쌓고 탐색하는 일이 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.