---
title: "가운데가 아니라 중앙값에서 자른다"
description: "쿼드트리는 공간의 한가운데를 자르고 KD 트리(k-d tree)는 점들의 중앙값을 자릅니다. 트리 모양이 분포에서 풀려나는 대신 무엇을 내주는지, 가지치기가 실제로 몇 개를 걷어 내는지 실측으로 봅니다."
author: "유니얼"
pubDate: 2026-09-18
category: "programming/algorithm/spatial"
tags: ["최적화", "자료구조"]
canonical: https://blog.unialgames.com/posts/algo-kd-tree/
---
쿼드트리는 넘친 칸을 넷으로 나눕니다. 그런데 **어디를 자르는지**는 한 번도 고른 적이 없습니다.
언제나 그 칸의 한가운데입니다. 안에 점이 어떻게 들어 있든 상관하지 않습니다.

대개는 문제가 안 됩니다. 문제는 점들이 경계 근처에 몰려 있을 때입니다.
한가운데로 갈랐는데 넷 중 한 칸에 전부 들어가면, 아무것도 나눠지지 않은 채 깊이만 하나 늘어납니다.

똑같은 점 1,000개를 세 가지로 뿌리고 쿼드트리를 지어 봤습니다. 정원은 넷입니다.

| 분포 | 노드 | 깊이 |
| --- | --- | --- |
| 고르게 흩뿌림 | 697 | 6 |
| 절반은 덩어리, 절반은 성기게 | 765 | 9 |
| 전부 다섯 덩어리에 뭉침 | 917 | 11 |

점 개수는 같은데 노드가 697에서 917로, 깊이가 6에서 11로 벌어집니다.
**트리 모양이 데이터 분포를 그대로 닮습니다.**

더 밀어붙이면 확실해집니다. 점 **두 개**만 놓고, 둘 사이 간격만 좁혀 봤습니다.

| 두 점 사이 간격 | 쿼드트리 깊이 | 쿼드트리 노드 |
| --- | --- | --- |
| 1.0 | 10 | 41 |
| 0.1 | 14 | 57 |
| 0.01 | 17 | 69 |

점 두 개를 갈라놓는 데 노드 69개를 씁니다. 한가운데로만 자르니 둘 사이에 경계가 걸릴 때까지
계속 반씩 좁혀 들어가는 것입니다. 깊이 제한이 필요한 이유가 이것이었습니다.

## 점들의 중앙값에서 자른다

고칠 곳은 한 군데입니다. **자르는 자리를 공간이 아니라 점들이 정하게 하면** 됩니다.

한 축을 고르고, 그 축 값으로 점들을 줄 세우고, **가운데 점을 지나도록** 자릅니다.
그러면 왼쪽과 오른쪽에 언제나 정확히 절반씩 들어갑니다. 점이 어디에 몰려 있든 상관없습니다.
다음 단계에서는 축을 바꿔서 같은 일을 합니다. x, y, x, y 로 번갈아 갑니다.

이것이 **KD 트리(k-d tree, k-dimensional tree)** 입니다. k 는 차원 수입니다. 2차원이면 2D 트리입니다.

쿼드트리와 갈리는 지점이 셋입니다.

- 자르는 자리를 **데이터가 정합니다**. 공간의 한가운데가 아니라 점들의 중앙값입니다
- 한 번에 **한 축만** 자릅니다. 그래서 자식이 넷이 아니라 **둘**입니다
- 자른 뒤 양쪽 개수가 **항상 같습니다**. 트리가 한쪽으로 자랄 수가 없습니다

<x-kd>
<script type="application/json">
{
  "label": "중앙값에서 자르기",
  "size": 16,
  "leaf": 2,
  "points": [[6.2, 7.0], [8.1, 4.5], [8.0, 14.2], [5.8, 4.4], [14.0, 11.0], [12.2, 14.0], [15.0, 5.2], [0.8, 11.4], [10.3, 6.4], [13.8, 12.4], [9.0, 9.6], [6.8, 3.4], [5.0, 11.3], [7.9, 8.3], [10.2, 14.3], [2.5, 2.1]],
  "query": [3, 3],
  "note": "자른 선의 자리가 점들을 따라 움직입니다. 왼쪽과 오른쪽 개수는 늘 같습니다"
}
</script>
</x-kd>

점 16개를 잎 2개짜리로 담으면 칸 8개, 깊이 3이 나옵니다.
**계산으로 미리 알 수 있는 값**입니다. 매번 반으로 가르니 깊이는 log₂(16/2) = 3입니다.
어떤 분포를 넣어도 이 값이 나옵니다.

## 어느 축으로 자를까

축을 번갈아 가는 것은 가장 단순한 규칙일 뿐 최선은 아닙니다.
가로로 긴 띠 모양으로 점이 늘어서 있으면 어떻게 될까요.
세로로 자르는 것은 쓸모가 있지만, 가로로 자르는 것은 얇은 띠를 더 얇게 만들 뿐입니다.

그래서 **지금 칸에서 더 넓은 축을 고르는** 규칙을 씁니다. 매번 두 축의 폭을 재서 긴 쪽을 자릅니다.

점 1,000개로 재 봤습니다. 각 점마다 가장 가까운 다섯을 500번 찾고,
**실제로 거리를 잰 횟수와 들여다본 노드 수를 더한 값**입니다.

| 분포 | 축 번갈아 | 넓은 축 고르기 |
| --- | --- | --- |
| 절반은 덩어리, 절반은 성기게 | 15,212 | 14,720 |
| 가로로 긴 띠 | 21,697 | 14,391 |

고른 분포에서는 3퍼센트 남짓입니다. 띠에서는 **34퍼센트**가 줄어듭니다.
축을 재는 값은 그 칸의 점들을 한 번 훑는 것이라 거의 공짜입니다. 넓은 축을 고르는 쪽이 낫습니다.

축을 고르는 규칙은 이것 말고도 있습니다. 중앙값 대신 **분산이 가장 큰 축**을 고르거나,
자른 뒤 양쪽 넓이가 얼마나 균형이 맞는지까지 따지는 방법도 씁니다.
다만 그런 것들은 짓는 값이 오르니, 넓은 축부터 써 보고 모자랄 때 올리는 편이 낫습니다.

## 가장 가까운 것을 찾는다

여기가 KD 트리의 핵심입니다. 트리를 어떻게 지었든 **찾는 방법을 모르면 쓸모가 없습니다.**

가장 가까운 점 하나를 찾는다고 해 보겠습니다. 두 단계입니다.

첫째, **내려갑니다.** 각 노드에서 찾는 자리의 좌표를 경계와 견줍니다.
경계보다 작으면 왼쪽, 크면 오른쪽입니다. 비교 한 번에 남은 점의 절반이 걸러집니다.
바닥에 닿으면 그 칸의 점들과 실제로 거리를 재서 **일단 하나를 쥡니다.**

이때 쥔 것이 정답이라는 보장은 없습니다. 바로 옆 칸에 더 가까운 점이 있을 수 있습니다.
자르는 선이 두 점 사이를 지나갔을 뿐이니까요.

둘째, **올라오면서 반대쪽을 볼지 정합니다.** 이때 재는 것이 딱 하나입니다.
찾는 자리에서 **경계선까지의 거리**와, 지금 쥐고 있는 **최선의 거리**를 견줍니다.

- 경계까지의 거리가 **더 멀면**, 반대쪽에는 더 가까운 점이 있을 수가 없습니다. 통째로 건너뜁니다
- 경계까지의 거리가 **더 가까우면**, 반대쪽에도 가능성이 있습니다. 내려가서 확인합니다

이것이 **가지치기(pruning)** 입니다. 찾는 자리를 중심으로 최선의 거리만큼 원을 그렸다고 생각하면 쉽습니다.
**그 원이 경계를 넘어가지 않으면 반대쪽은 볼 필요가 없습니다.**

<x-kd>
<script type="application/json">
{
  "label": "가장 가까운 것 찾기",
  "size": 16,
  "leaf": 2,
  "mode": 1,
  "points": [[6.2, 7.0], [8.1, 4.5], [8.0, 14.2], [5.8, 4.4], [14.0, 11.0], [12.2, 14.0], [15.0, 5.2], [0.8, 11.4], [10.3, 6.4], [13.8, 12.4], [9.0, 9.6], [6.8, 3.4], [5.0, 11.3], [7.9, 8.3], [10.2, 14.3], [2.5, 2.1]],
  "query": [3, 3],
  "note": "점선 원이 지금 쥔 최선입니다. 원이 경계를 안 넘으면 그쪽은 통째로 건너뜁니다"
}
</script>
</x-kd>

16개 중 **2개만** 실제로 거리를 쟀습니다. 나머지 14개는 좌표를 들여다보지도 않았습니다.
경계까지의 거리 세 번을 재고 통째로 걷어 냈습니다.

거리를 견줄 때는 **제곱근을 씌우지 않습니다.** 제곱한 값끼리 견주면 대소 관계가 같고
제곱근은 비싼 연산입니다. 경계까지의 거리도 좌표 차이를 제곱해서 견줍니다.
가장 가까운 것을 찾는 코드에서 `Mathf.Sqrt` 가 보이면 대개 지울 수 있습니다.

## 훑는 순서가 구조보다 크다

위 방식은 왼쪽을 다 보고 오른쪽을 보는 **깊이 우선**입니다. 다른 방법이 있습니다.
각 노드에 **그 안에 든 점들의 실제 경계 상자**를 달아 두고,
찾는 자리에서 가까운 상자부터 우선순위 큐로 꺼내는 것입니다.

같은 트리, 같은 질의로 둘을 재 봤습니다.

| 훑는 순서 | 잎 2 | 잎 4 | 잎 8 |
| --- | --- | --- | --- |
| 깊이 우선, 자르는 면까지의 거리로 가지치기 | 24,180 | 21,462 | 22,038 |
| 최선 우선, 실제 경계 상자로 가지치기 | 14,640 | 14,720 | 16,980 |

**구조는 그대로인데 3분의 1이 줄었습니다.** 이유는 둘입니다.
가까운 쪽부터 꺼내니 좋은 최선을 일찍 쥐게 되고, 자르는 면이 아니라 점들의 실제 경계 상자를 쓰니
빈 공간만큼 거리가 더 나와서 가지치기가 자주 걸립니다.

## 잎에 몇 개를 담을까

잎마다 점 하나씩 담는 것이 교과서 그림입니다. 실제로는 몇 개씩 담습니다.
잎을 키우면 트리가 얕아져서 노드를 덜 훑는 대신, 잎에 닿을 때마다 재야 할 점이 늘어납니다.

점 1,000개, 넓은 축, 최선 우선으로 잎 크기만 바꿔 봤습니다.

| 잎 크기 | 노드 | 깊이 | 거리 잰 횟수 | 들여다본 노드 | 합 |
| --- | --- | --- | --- | --- | --- |
| 1 | 1,999 | 10 | 2,500 | 13,512 | 16,012 |
| 2 | 1,023 | 9 | 4,072 | 10,568 | **14,640** |
| 4 | 511 | 8 | 6,466 | 8,254 | **14,720** |
| 8 | 255 | 7 | 10,502 | 6,478 | 16,980 |
| 16 | 127 | 6 | 16,822 | 5,072 | 21,894 |
| 32 | 63 | 5 | 28,258 | 3,963 | 32,221 |

두 열이 정확히 반대로 움직입니다. 잎을 키우면 거리 잰 횟수는 늘고 들여다본 노드는 줍니다.
합이 가장 작은 자리는 **2에서 4 사이**입니다.

다만 이 표는 둘을 그냥 더한 값입니다. 실제로는 거리 계산이 노드를 따라가는 것보다 쌉니다.
연속된 메모리를 순서대로 읽기 때문입니다. 노드를 타고 가는 쪽은 포인터를 따라 여기저기 뛰어야 합니다.
그래서 **실측 시간으로 재면 최적점이 오른쪽으로 밀립니다.** 8이나 16이 나오는 구현이 흔합니다.

## 그래서 쿼드트리보다 빠른가

정직하게 말하면 **거의 같습니다.** 같은 조건으로 붙여 봤습니다.
쿼드트리는 정원 4, KD 트리는 잎 4에 넓은 축, 둘 다 최선 우선입니다.

| 분포 | 쿼드트리 노드 | 쿼드트리 깊이 | 쿼드트리 합 | KD 노드 | KD 깊이 | KD 합 |
| --- | --- | --- | --- | --- | --- | --- |
| 고르게 흩뿌림 | 697 | 6 | **14,354** | 511 | 8 | 14,826 |
| 절반은 덩어리 | 765 | 9 | **14,615** | 511 | 8 | 14,720 |
| 전부 뭉침 | 917 | 11 | 17,004 | 511 | 8 | **15,066** |

찾는 값은 세 번 다 5퍼센트 안쪽입니다. 고른 분포에서는 쿼드트리가 조금 낫고, 뭉친 분포에서만 KD가 앞섭니다.
**속도를 기대하고 KD 트리로 바꾸는 것은 대개 헛수고입니다.**

눈여겨볼 곳은 다른 열입니다. KD 트리의 노드와 깊이가 **세 줄 모두 511과 8**입니다.
쿼드트리는 697에서 917로, 6에서 11로 움직입니다.
KD 트리는 데이터가 어떻게 생겼든 **메모리도 깊이도 미리 정해집니다.** 이게 값어치입니다.

- 최악을 알아야 하는 자리에서 유리합니다. 노드 수가 점 개수로 정해지니 배열 하나로 잡아 둘 수 있습니다
- 재귀 깊이가 log 로 묶여 있어서 스택이 터질 걱정이 없습니다
- 차원이 오르면 갈립니다. 쿼드트리 계열은 한 노드의 자식이 2ᵏ 개입니다. 3차원이면 여덟, 4차원이면 열여섯입니다.
  KD 트리는 차원이 몇이든 **둘**입니다. 3차원을 넘어가면 사실상 선택지가 없습니다

## 짓는 값을 앞에서 치른다

공짜는 아닙니다. 중앙값을 찾으려면 매번 정렬해야 합니다.

점 개수를 늘려 가며 짓는 시간만 재 봤습니다. 같은 기계, 같은 언어입니다.

| 점 개수 | 쿼드트리 | KD 트리 |
| --- | --- | --- |
| 1,000 | 2.2ms | 3.1ms |
| 10,000 | 25.2ms | 44.7ms |
| 100,000 | 382.4ms | 954.1ms |

**2.5배쯤 비쌉니다.** 쿼드트리는 점을 하나씩 떨어뜨리기만 하면 되는데
KD 트리는 단계마다 정렬을 거칩니다. 매 단계 전체를 한 번씩 훑으니 log 배가 붙습니다.

정렬 대신 **선택 알고리즘(nth element)** 으로 중앙값만 뽑으면 정렬 없이 갈라낼 수 있습니다.
C# 표준 라이브러리에는 없어서 직접 써야 하지만, 큰 데이터라면 값어치가 있습니다.

더 중요한 것은 **고칠 수가 없다**는 점입니다.

- 점 하나를 넣으면 그 자리의 중앙값이 더 이상 중앙값이 아닙니다
- 몇 번 넣고 빼면 양쪽 개수가 어긋나고, **항상 반반**이라는 전제가 무너집니다
- 균형을 되찾으려면 그 아래를 다시 지어야 합니다

쿼드트리는 넘친 칸만 쪼개면 되니 국소적으로 고칠 수 있었습니다. KD 트리는 그게 안 됩니다.
그래서 **움직이지 않는 점 집합**에 씁니다. 지형지물, 스폰 지점, 커버 지점, 웨이포인트처럼
한 번 놓으면 그대로인 것들입니다. 굽는 단계에서 한 번 짓고 런타임에는 읽기만 합니다.

움직이는 것을 굳이 담아야 한다면 **매 프레임 통째로 다시 짓는 쪽**이 고치는 것보다 낫습니다.
위 표를 보면 1만 개를 44.7ms 에 짓습니다. 프레임마다 하기에는 무겁고, 몇 초에 한 번이라면 할 만합니다.

## 게임 밖에서 더 많이 보인다

KD 트리는 게임 안에서보다 밖에서 더 자주 쓰입니다. 공통점은 **점이 안 움직인다**는 것입니다.

- **포톤 매핑.** 굽는 동안 빛 알갱이를 수백만 개 뿌려 놓고, 각 지점에서 가까운 것들을 모읍니다.
  다 뿌린 뒤에 한 번 짓고 그 뒤로는 찾기만 합니다
- **색 양자화.** 이미지의 색을 256개로 줄일 때, 색 공간을 중앙값으로 갈라 가는 방법을 씁니다.
  이름이 아예 중앙값 자르기(median cut)입니다
- **가장 가까운 이웃 분류.** 특징 벡터가 수십 차원이라 쿼드트리 계열은 아예 못 씁니다
- **점군 정합.** 라이다나 스캔으로 얻은 점 수백만 개를 서로 맞출 때, 한쪽을 KD 트리로 짓고 반대쪽을 질의합니다

다만 차원이 많이 올라가면 KD 트리도 무너집니다. 20차원쯤 되면 원이 거의 모든 경계를 넘어가서
가지치기가 걸리지 않고, 결국 전부 훑는 것과 비슷해집니다. 차원의 저주라고 부르는 현상입니다.
그때는 정확한 답을 포기하고 **근사 최근접(ANN)** 쪽으로 갑니다.

게임 안에서 KD 트리를 쓴다면 물체가 아니라 **점**을 담는다는 것을 기억하세요.
크기가 있는 물체는 경계선에 걸치고, 걸친 것을 양쪽에 넣기 시작하면 절반씩 갈린다는 전제가 깨집니다.
크기가 있는 것은 물체를 상자로 묶어 올라가는 구조 쪽이 맞습니다.

## 정리

KD 트리는 **자르는 자리를 데이터에 물어보는** 트리입니다.

- 공간의 한가운데가 아니라 **점들의 중앙값**에서 자릅니다. 그래서 양쪽이 항상 반반입니다
- 축은 번갈아 가는 것보다 **넓은 쪽을 고르는** 편이 낫습니다. 띠 모양에서 34퍼센트 차이가 났습니다
- 찾을 때는 내려가서 하나 쥐고, 올라오며 **경계까지의 거리와 지금 최선**을 견줘 반대쪽을 걷어 냅니다
- **훑는 순서가 구조보다 컸습니다.** 최선 우선과 실제 경계 상자로 바꾸니 3분의 1이 줄었습니다
- 잎에는 여러 개를 담습니다. 더한 값의 최적점은 2에서 4, 실측 시간으로는 더 오른쪽입니다
- 쿼드트리보다 **빠르지 않습니다.** 대신 노드 수와 깊이가 분포와 상관없이 고정됩니다
- 짓는 값이 2.5배고 국소적으로 못 고칩니다. **안 움직이는 점 집합** 전용입니다