읽고 나면 진짜 쉬워지는 자료 구조 - 9. 공간 트리

트리 기반 자료 구조와 공간 분할의 개념을 기반으로 최근접 이웃 탐색을 더 향상시키기

🔖 9.1 쿼드 트리

격자의 한계

• 많은 격자 상자를 사용하면 상당한 메모리가 필요하고 많은 상자 탐색 필요

• 격자를 거칠게(?) 분할하면 상자에 들어가는 점이 많아져 단순 선형 스캔과 비슷한 결과가 나타남

• 이에 대해 데이터에 따라 공간을 동적으로 분할하면 좋음 -> 균일 쿼드 트리

균일 쿼드 트리

• 트리의 분기 구조를 격자에 도입하며, 트리의 각 노드는 공간의 각 영역을 나타냄

• 할당된 공간을 점점 더 작은 하위 영역으로 재귀적으로 분할하는 방식으로 미술처럼 쿼드 트리 만들기

• 노드에 점을 추가하는 것은 새로운 점의 위치를 찾기 위해 트리를 탐색하는 것으로 이루어진다.

점 제거하기

• 점을 삽입하는 것과 비슷하지만 더 복잡한 과정을 따른다.

• 격자와 마찬가지로 임의로 가까운 점을 추가하거나 중복된 점을 삽입할 수 있다.

• wrapper 함수는 점이 트리 경계 안에 있는지 확인 후, 재귀적인 제거 함수 호출

균일 쿼드 트리에 대한 탐색

• 균일 쿼드 트리에서는 루트 노드에서 탐색을 시작한다.

• 그리고 현재 후보보다 더 가까이 있는 점이 포함될 수 있는지를 먼저 확인한다.

• 책에서 든 예시처럼, 게으른 이웃이 어디로 공을 던져야 가장 짧은 거리로 우리집 마당에 공을 넘겨줄 수 있는지 물어보는 것이다.

🔖 k-d 트리

k-d 트리의 구조

• k-d 트리는 쿼드 트리와 비슷한 개념을 기반으로 구축된다.

• 쿼드 트리의 공간 분할과 이진 탐색 트리의 2개 자식으로 뻗어나가는 특성을 결합해 두 자료 구조의 장점을 모두 취하는 공간 자료구조다.

• k-d 트리는 한 차원을 선택해서 해당 차원을 기준으로 데이터를 분할한다.

• 유연한 구조로 인해 노드의 공간 경계를 다룰 때는 더 주의해야 한다.

• 복잡성으로 인해 각 k-d 트리 노드는 상당한 양의 정보를 저장한다.

꼭 들어맞는 공간 경계

• 엄격한 경계를 사용하면 k-d 트리를 데이터에 더 잘 적용시킬 수 있다.

• 엄격한 경계를 통해 얻은 영역이 훨씬 작기 때문에 가지치기를 더 강력하게 할 수 있다.

• 따라서 목표점과 경계 사이의 최소 거리가 더 커질 가능성이 높다.

k-d 트리 만들기

• 이진 탐색 트리 생성과 비슷한 재귀 과정을 거치지만 차이가 있다.

• 처음에는 모든 데이터 점에서 시작하고, 분할할 차원과 값을 선택해 두 하위 집합으로 데이터 점들을 나눈다.

• 중복 데이터가 있을 때 무한 재귀가 발생하는 것을 피하기 위해 마지막 두 검사 중 하나는 사용한다.

• 주된 차이는 k-d 트리의 경우 각 레벨에서 분할할 차원을 하나만 선택한다는 것이다.

k-d 트리의 연산

• 기본 연산은 점의 삽입, 제거, 탐색이며 쿼드 트리와 같은 방법을 쓴다.

• 모든 연산은 맨 위에서 시작하고, 분할 값을 사용해 적절한 가지로 이동한다.

• 주된 차이는 사분면 중 어느 쪽을 탐색할지 선택하는 대신, 두 자식 중 하나를 선택한다는 점이다.

🔖 9.3 쿼드 트리와 k-d 트리가 중요한 이유

핵심 정리

• 쿼드 트리를 사용하면 한 번에 여러 차원을 분할함으로써 지역적인 영역의 데이터 점의 밀도에 맞게 격자 해상도를 조절할 수 있다.

• k-d 트리는 최근접 이웃 탐색 문제를 해결하기 위해 이진 트리의 핵심 아이디어를 본받은 개념이다.

• 각 노드에서 하나의 차원을 선택해 분할하는 방식을 써서, 다차원 데이터를 표현하는 트리에서 브랜칭 팩터가 커지는 문제를 해결한다.

• 또한 k-d 트리는 데이터 구조에 적응해 더 많은 가지치기를 제공하기에 자료구조에 더 유연히 대응할 수 있다.