KD-트리

수치해석 컴퓨터 그래픽스 게임 개발 마지막 수정: 2026-08-28 04:12:40

1. 개요[편집]

반은 버리고 시작한다. 문제는 나머지 반도 가끔 봐야 한다는 것.

KD-트리(k-d tree, k-dimensional tree)는 $k$ 차원 공간의 점 집합을 축에 수직인 초평면으로 재귀 이분해 만든 이진 트리로, 각 내부 노드가 「분할 축 $a$ + 분할 좌표 $s$ 」 한 쌍을 들고 왼쪽 부분트리에 $x_a < s$ 인 점을, 오른쪽에 $x_a \ge s$ 인 점을 담는다. 존 벤틀리가 1975년에 제안했고¹, 반세기가 지난 지금도 저차원 최근접 이웃 탐색의 기본값이다.

핵심 아이디어는 이진 탐색의 다차원 일반화다. 1차원에서 정렬된 배열을 반씩 잘라 들어가듯, $k$ 차원에서는 “축 하나를 골라 그 축으로만 반을 자른다”를 축을 돌려가며 반복한다. 자르는 면이 축에 수직이라는 제약 덕분에 점과 분할면 사이 거리가 좌표 뺄셈 한 번이 되고, 이 싸구려 거리 계산이 곧 가지치기의 근거가 된다. 공간 분할 자료구조 전반에서 KD-트리의 위치가 궁금하다면 그쪽 문서가 조감도를 준다 — 여기서는 자료구조 자체와 가지치기가 언제 먹히고 언제 안 먹히는지를 판다.

2. 구축 — 중앙값으로 자른다[편집]

균형 잡힌 KD-트리는 매 노드에서 중앙값으로 자른다. 그러면 높이가 $\lceil \log_2 n \rceil$ 로 고정되고 최악 케이스 퇴화가 사라진다.

분할 축을 고르는 방식은 둘이다.

방식	규칙	성격
라운드로빈	깊이 $d$ 에서 축 $d \bmod k$	구현이 가장 싸다. 축을 저장할 필요조차 없다
최대 분산(최대 스프레드)	그 노드 점들의 좌표 범위나 분산이 가장 큰 축	셀이 길쭉해지는 것을 막는다. 스케일이 다른 데이터에서 필수

라운드로빈은 모든 축의 스케일이 비슷할 때만 정당하다. 좌표 하나가 미터고 다른 하나가 밀리미터면 라운드로빈 트리의 셀은 종잇장처럼 납작해지고, 가지치기 조건이 그 얇은 축에서 거의 항상 실패한다. 실무 구현(FLANN, scikit-learn, nanoflann)이 최대 스프레드를 기본으로 두는 이유다.

비용은 흔히 오해된다. 노드마다 정렬해서 중앙값을 뽑으면 $O(n \log^2 n)$ 이지만, 정렬 대신 선택(selection) 을 쓰면 한 레벨의 총 비용이 기대 $O(n)$ 이라 전체가 $O(n \log n)$ 이다. C++이라면 std::nth_element(인트로셀렉트) 한 줄이고, 이게 KD-트리 구축 코드가 짧은 이유다. 저장 공간은 $O(n)$ 이며, 완전 이진 트리 모양을 유지하면 자식 포인터 없이 배열 인덱스 $2i{+}1, 2i{+}2$ 로 표현할 수 있다 — 힙과 같은 트릭이고, 캐시 지역성이 눈에 띄게 좋아진다.

리프에 점을 하나씩 두는 것보다 리프당 8~32개 정도를 묶어 두고 그 안은 전수 비교하는 편이 거의 항상 빠르다. 트리 깊이가 얕아져 분기 예측 실패와 포인터 추적이 줄고, 마지막 몇 개는 어차피 SIMD로 훑는 게 이득이기 때문이다.

3. 최근접 질의 — 내려갔다가 되돌아온다[편집]

질의점 $q$ 의 최근접 이웃을 찾는 절차는 두 국면이다.

하강. 루트에서 시작해 각 노드에서 $q_a < s$ 면 왼쪽, 아니면 오른쪽으로 내려간다. 리프에 닿으면 그 안의 점들과 거리를 재서 현재 최선 $(p^\star, r = \lVert q - p^\star \rVert)$ 를 잡는다. 이건 “질의점이 속한 칸”을 찾는 것이라 $O(\log n)$ 에 끝나지만, 여기서 나온 답은 진짜 최근접이 아닐 수 있다 — 칸 경계 바로 건너편에 더 가까운 점이 있을 수 있으니까.
되돌아오기(백트래킹). 재귀를 빠져나오며 각 노드에서 묻는다. 지금까지의 최선 반경 $r$ 짜리 공이 형제 쪽 반공간을 침범하는가? 침범하지 않으면 형제 부분트리를 통째로 건너뛴다.

가지치기 조건이 전부다.

\lvert q_a - s \rvert \;\ge\; r \quad\Longrightarrow\quad \text{형제 부분트리 전체를 버린다}

증명은 한 줄이다. 형제 쪽 점 $p$ 는 정의상 $p_a$ 가 분할면 반대편에 있으므로 $\lVert q - p \rVert \ge \lvert q_a - p_a \rvert \ge \lvert q_a - s \rvert \ge r$ 이고, 이미 손에 든 최선보다 가까울 수 없다. 축 정렬 분할의 값어치가 여기 전부 들어 있다 — 한 좌표의 차이만으로 유클리드 거리의 하계가 나온다. 실제 구현은 제곱근을 피해 $(q_a - s)^2 \ge r^2$ 로 비교한다.

이웃 $m$ 개를 찾는 $m$ -NN 질의도 똑같다(관례상 이 개수를 $k$ 로 쓰지만, 여기서는 차원의 $k$ 와 겹치니 $m$ 으로 적는다). 최선 하나 대신 크기 $m$ 짜리 최대힙(우선순위 큐)을 들고 다니고, $r$ 자리에 힙의 최댓값을 넣으면 된다. 반경 질의는 더 간단해서 $r$ 이 아예 상수로 고정된다.

[0,1]²에 점 600개로 중앙값 분할 kd-트리를 짓고, 질의점을 옮기며 k-NN 탐색을 한 노드씩 진행한다. 되돌아오는 길에 현재 k번째 최선반경이 분할 초평면까지 닿지 않으면 그 형제 서브트리를 통째로 버리는데, k=3에서 질의 1회당 평균 21.9개 노드만 열어 전수탐색 600개의 3.65 %로 끝난다. 매 질의를 전수탐색과 대조한 일치 횟수를 화면에 띄우고, 오른쪽 곡선은 같은 코드의 방문 비율이 d=16에서 100 %로 무너지는 것을 계산한다.

4. 가지치기는 차원 앞에서 무너진다[편집]

프리드먼·벤틀리·핑켈(1977)의 고전적 결과는 $k$ 가 고정이고 점이 균등 분포일 때 질의 비용이 기대 $O(\log n)$ 이라는 것이다. 문제는 저 “고정”에 숨은 상수가 $k$ 에 대해 지수적이라는 점이다.

직관은 이렇다. 최근접 이웃까지의 거리 $r$ 은 점 밀도로 정해지는데, $n$ 개 점이 단위 정육면체에 퍼져 있으면 $r \sim n^{-1/k}$ 다. 한편 리프당 점 몇 개를 담는 트리의 리프 셀도 한 변이 대략 같은 $n^{-1/k}$ 규모인 상자다. 질의공 $B(q,r)$ 이 몇 개의 셀과 겹치는가 가 방문 노드 수를 결정하는데, 차원이 오르면 상자의 이웃 개수 자체가 $3^k$ 로 늘고 $r$ 은 좀처럼 줄지 않아 공이 사실상 모든 이웃 셀을 건드린다. 결과적으로 $\lvert q_a - s \rvert \ge r$ 이 성립하는 축이 거의 없어지고, 가지치기는 하나도 안 되며 트리는 전수탐색을 포인터를 따라가며 하는 느린 방법으로 전락한다.

경험칙은 유명하다. $n \gg 2^k$ 이어야 KD-트리가 전수탐색을 이긴다.² $k=20$ 이면 $n$ 이 백만 개여도 $2^{20}$ 과 같은 자릿수라 이미 위태롭고, 512차원 임베딩에서 KD-트리를 쓰겠다는 것은 산술적으로 농담이다. 이것이 차원의 저주가 자료구조에 나타나는 얼굴이다 — 거리들이 서로 비슷해지면 “반대편은 볼 필요 없다”는 논거 자체가 사라진다.

탈출로는 셋이다.

근사를 받아들인다. 베이스와 로우(1997)의 BBF(Best-Bin-First)는 백트래킹 순서를 재귀 순서가 아니라 분할면까지 거리가 가까운 순으로 바꾸고(우선순위 큐), 방문 노드 수가 정해진 예산을 넘으면 그냥 멈춘다. 답이 진짜 최근접이라는 보장은 버리지만, SIFT 서술자 매칭에서 실용적 정확도를 유지한 채 수십 배 빨라진다.
트리를 여러 그루 심는다. 실파-아난과 하틀리(2008)의 랜덤화 KD-포레스트는 분산이 큰 상위 몇 개 축 중 하나를 무작위로 골라 서로 다른 트리를 여러 그루 만들고, 공유 우선순위 큐로 동시에 훑는다. 한 트리가 놓친 이웃을 다른 트리가 잡아주는 구조다. FLANN이 이 방식과 계층적 $k$ -평균 트리 중 데이터에 맞는 쪽을 자동으로 고른다.
다른 자료구조로 간다. 축 정렬을 포기하고 초구로 자르는 볼 트리(Omohundro 1989)나, 무작위 기준점까지의 거리로 자르는 VP-트리(Yianilos 1993)는 축이 의미 없는 데이터·비유클리드 거리에서 낫다. 진짜 고차원이면 해시나 그래프 기반으로 갈아타야 하고, 그 지도는 최근접 이웃 탐색 문서에 있다.

5. 최근접 말고도 — 범위 질의[편집]

KD-트리는 직교 범위 질의(축 정렬 상자 안의 점 다 내놔)도 처리한다. 노드의 셀이 질의 상자에 완전히 포함되면 부분트리를 통째로 보고하고, 전혀 겹치지 않으면 통째로 버리고, 걸치면 재귀한다. 최악 비용은 잘 알려져 있다.

O\!\left(n^{1-1/k} + m\right) \qquad (m = \text{보고된 점 수})

2차원이면 $O(\sqrt n + m)$ 이다. $\log$ 가 아니라 $\sqrt n$ 이라는 게 포인트고, 이 지수 $1-1/k$ 역시 차원이 커지면 $1$ 로 붙어 전수탐색이 된다. 순수 범위 보고만 필요하고 저장 공간이 아깝지 않다면 범위 트리( $O(\log^k n + m)$ )가 이론적으로 낫지만, 상수와 메모리 때문에 실무에서는 대개 KD-트리가 이긴다.

6. 이름만 같은 사촌 — 레이 트레이싱의 KD-트리[편집]

레이 트레이싱 문헌의 “kd-tree”는 점이 아니라 삼각형을 담는다. 그래서 성질이 꽤 다르다.

삼각형은 분할면에 걸친다. 점 KD-트리에서는 각 점이 정확히 한 노드에 속하지만, 여기서는 걸친 프리미티브가 양쪽 자식에 중복 등록된다. 트리 크기가 $n$ 을 넘어 커질 수 있다는 뜻이다.
분할 위치를 중앙값이 아니라 표면적 휴리스틱(SAH)으로 고른다. 자식 볼륨의 표면적이 광선이 그 자식을 때릴 확률에 비례한다는 가정 아래 기대 순회 비용을 최소화하는 지점에서 자르며, 후보 위치는 프리미티브 경계상자의 면들이다. 결과적으로 빈 공간을 통째로 잘라내는 분할이 선호된다.
그래서 “중앙값 = 균형”이라는 점 KD-트리의 미덕이 여기서는 오히려 나쁜 트리를 만든다. 광선 순회에서는 균형이 아니라 기대 비용이 목적함수다.

정적 장면에서 SAH KD-트리는 여전히 최상급 광선 순회 성능을 내지만, 물체가 움직이면 매 프레임 다시 지어야 해서 오늘날 실시간 렌더링·게임 물리의 표준은 경계 볼륨 계층(BVH) 쪽으로 넘어갔다.³

7. 시뮬레이션에서의 KD-트리 — 그리고 격자가 이기는 경우[편집]

입자 시뮬레이션의 이웃 탐색은 KD-트리의 대표 응용으로 소개되곤 하는데, 현장의 사실은 좀 더 미묘하다.

SPH·분자동역학의 컷오프 이웃 탐색은 대개 균일 셀 격자가 KD-트리보다 빠르다. 반경 $h$ 가 고정이고 셀 변을 $h$ 로 잡으면 이웃 후보가 인접 27칸으로 끝나 질의당 사실상 $O(1)$ 이고, 셀 인덱스는 나눗셈 세 번이다. 트리를 매 스텝 다시 짓는 비용도 없다. 밀도가 극단적으로 불균일한 천체물리 계산(적응형 SPH, 중력 트리코드)에서야 트리가 값을 한다.
점군 정합의 대응 탐색은 KD-트리의 확실한 영역이다. ICP는 목표 점군이 반복 내내 고정이므로 트리를 한 번만 $O(m \log m)$ 에 짓고 매 반복 $n$ 번 질의하면 되며, 컷오프 반경이 미리 정해져 있지 않아 격자를 쓰기 곤란하다. 정합 라이브러리(PCL, Open3D)의 기본값이 KD-트리인 이유다.
$k$ -NN 회귀·분류, 다양체 학습의 이웃 그래프도 저차원(또는 주성분 분석으로 먼저 줄인 뒤)이면 KD-트리로 짓는 게 표준이다.

판단 기준은 간단하다. 반경이 고정이고 밀도가 고르면 격자, 반경이 질의마다 다르거나 밀도가 불균일하면 트리.

8. 구현할 때 밟는 지뢰[편집]

분할 축을 노드에 저장하지 않고 깊이로 유추해 놓고 나중에 최대 스프레드로 바꾸면 조용히 틀린다. 처음부터 축을 저장해라. 어차피 1바이트다.
중복 좌표. 같은 $x_a$ 값을 가진 점이 많으면 < s / >= s 분할이 한쪽으로 쏠려 트리가 선형으로 퇴화한다. 중앙값 인덱스를 기준으로 배열을 자르는(값이 아니라 순위로 자르는) 구현이면 안전하다.
가지치기에 제곱근을 넣는다. 거리 비교는 전부 제곱거리로 해라. sqrt는 마지막 한 번이면 충분하다.
질의점이 데이터셋에 들어 있는 경우. 자기 자신이 최근접으로 나온다. $k$ -NN 그래프를 지을 때 $k{+}1$ 개를 뽑아 자기를 빼는 게 국룰이고, 이걸 잊으면 이웃 그래프가 통째로 한 칸씩 밀린다.
동적 점군. KD-트리는 삽입·삭제에 약하다. 점이 움직이면 균형이 깨지므로, 게임처럼 매 프레임 갱신이 필요하면 트리를 다시 짓거나 애초에 BVH·격자로 가는 게 맞다.

9. 관련 문서[편집]

Bentley, J. L. (1975). “Multidimensional binary search trees used for associative searching.” CACM 18(9). 원 논문의 주 관심사는 최근접 이웃이 아니라 연관 검색(부분 매치 질의)이었다. 세상이 기억하는 용도는 저자가 부제로도 안 넣은 쪽이라는, 알고리즘 논문의 흔한 운명. ↩
$n \gg 2^k$ 를 곧이곧대로 읽으면 $k=30$ 에 필요한 점이 10억 개다. 그런데 실제 데이터는 대개 «내재 차원»이 명목 차원보다 훨씬 낮아서, 512차원 벡터가 사실은 20차원 다양체 위에 놓여 있으면 KD-트리가 예상보다 오래 버티기도 한다. 물론 그 사실을 미리 알 방법은 없고, 그래서 다들 그냥 벤치마크를 돌린다. ↩
두 자료구조의 차이를 한 문장으로 줄이면 “KD-트리는 공간을 나누고 BVH는 객체를 나눈다”다. 공간을 나누면 프리미티브가 걸쳐 중복되고, 객체를 나누면 볼륨이 겹친다. 세상에 공짜는 없다. ↩