포인트 쿼드트리(Point Quadtree)는 2차원 점(point) 데이터를 표현하기 위해 이진 트리(binary tree)를 변형한 자료구조입니다. 모든 쿼드트리(quadtree)가 가지는 공통적인 특징을 포인트 쿼드트리 역시 그대로 공유합니다.
포인트 쿼드트리의 특징과 성능
포인트 쿼드트리는 2차원으로 정렬된 데이터 포인트를 비교할 때 매우 효율적이며, 일반적으로 O(log n)의 시간 복잡도로 연산을 수행합니다.
다만 포인트 쿼드트리는 자료구조의 완전성을 위해 언급할 가치가 있을 뿐, 일반화된 이진 탐색 도구로서는 k-d 트리(k-d tree)가 더 우수한 성능을 보입니다. 따라서 실무에서 범용적인 검색이 필요하다면 k-d 트리를 먼저 고려하는 것이 좋습니다.
포인트 쿼드트리의 구축 방법
포인트 쿼드트리는 다음과 같은 과정을 통해 구축됩니다.
- 삽입할 다음 점이 주어지면, 해당 점이 속한 셀(cell)을 계산하여 트리에 추가합니다.
- 새로운 점은 그 점을 지나는 수직선과 수평선에 의해 셀이 네 개의 사분면(quadrant)으로 나뉘도록 추가됩니다.
이 과정에서 각 셀은 직사각형 형태를 가지지만, 반드시 정사각형일 필요는 없습니다. 또한 트리의 각 노드에는 입력된 점 중 하나가 저장됩니다.
삽입 순서가 트리 균형에 미치는 영향
평면의 분할 방식이 점의 삽입 순서에 따라 결정되기 때문에, 트리의 높이는 삽입 순서에 민감하게 의존합니다. 잘못된 순서로 점을 삽입하면 입력 점의 개수에 비례하는 선형(linear) 높이의 트리가 만들어질 수 있으며, 이 경우 트리는 사실상 연결 리스트(linked list)와 같은 형태로 성능이 크게 저하됩니다.
반면 점 집합(point-set)이 고정되어 있다면, 사전 처리(pre-processing)를 통해 균형 잡힌 높이의 트리를 미리 구성할 수 있습니다.
포인트 쿼드트리의 노드 구조
포인트 쿼드트리의 노드는 일반적인 이진 트리의 노드와 유사하지만, 결정적인 차이가 있습니다. 이진 트리가 '왼쪽(left)'과 '오른쪽(right)' 두 개의 포인터를 사용하는 것과 달리, 포인트 쿼드트리의 노드는 네 개의 포인터(각 사분면마다 하나씩)를 사용합니다. 또한 키(key)는 보통 x 좌표와 y 좌표 두 부분으로 나뉘어 저장됩니다.
따라서 포인트 쿼드트리의 노드는 다음 정보들로 구성됩니다.
- 네 개의 포인터: quad['NW'], quad['NE'], quad['SW'], quad['SE']
- NW(North West, 북서), NE(North East, 북동), SW(South West, 남서), SE(South East, 남동) — 각각 하나의 사분면을 가리킵니다.
- point(점): 다음 요소들을 포함합니다.
- key(키): 일반적으로 x, y 좌표로 표현됩니다.
- value(값): 이름(name)과 같은 부가 데이터를 저장합니다.
이처럼 포인트 쿼드트리는 2차원 공간 데이터를 체계적으로 분할하고 관리할 수 있는 강력한 자료구조이지만, 삽입 순서 관리와 k-d 트리와의 비교를 통해 상황에 맞게 선택하는 것이 중요합니다.