공간 검색 구조(spatial search structures)는 기하학적 데이터가 아닌 기호 데이터, 예컨대 사람 이름 목록처럼 방대한 양의 데이터를 빠르게 처리해야 하는 문제를 해결하기 위해 1960~70년대 컴퓨터 과학에서 탄생한 아이디어에 그 뿌리를 두고 있습니다.
정렬과 이진 탐색: 구조를 활용한 계산량 절감
이름 목록을 알파벳 순으로 미리 정렬한 뒤 배열에 저장해 두면, 순차 탐색(sequential search)에 필요한 평균 n/2번의 연산 대신 이진 탐색(binary search) 알고리즘을 통해 단 log₂n번의 연산만으로 새로운 이름이 목록에 이미 존재하는지 확인할 수 있습니다.
이것은 목록 안에 존재하는 구조, 즉 알파벳 순서를 추출해 내고, 이후 이름을 조회하는 연산에서 그 구조를 적극적으로 활용함으로써 계산량을 획기적으로 줄이는 좋은 예입니다. 핵심은 데이터에 내재된 구조를 찾아내 이를 탐색에 재활용한다는 발상입니다.
동적 자료구조의 필요성과 이진 탐색 트리
그러나 정렬된 상태를 유지하면서 이름의 추가와 삭제를 함께 지원해야 한다면 이야기가 달라집니다. 정적인 배열로는 부족하며, 포인터를 활용하는 동적 자료구조(dynamic data structure)가 필요합니다. 이러한 자료구조의 가장 대표적인 예가 바로 이진 탐색 트리(binary search tree)입니다.
실수 직선 위에 놓인 정수 집합 A = {1, 2, 5, 6, 7, 9}를 이진 탐색 트리로 표현한다고 가정해 봅시다. 어떤 수, 즉 어떤 점이 트리에 이미 존재하는지 판단하려면 해당 점을 트리에 삽입하는 경로를 따라가며, 그 점이 속한 중첩된 구간(nested intervals)의 수열에 대응되는 경로를 추적하면 됩니다.
균형 잡힌(balanced) 트리라면 이 과정은 최대 O(log n) 단계 안에 끝납니다. 사실상 우리는 배열이 아닌 트리를 이용해 이진 탐색을 수행한 셈입니다. 더 중요한 점은, 트리 자체가 탐색이 진행될 순서를 결정하기 때문에 탐색 알고리즘의 일부를 트리 구조 안에 인코딩할 수 있다는 사실입니다.
분할 트리(Partitioning Tree): 다차원으로의 일반화
이제 분할 트리(Partitioning Trees)로 시선을 돌려봅시다. 분할 트리는 이진 탐색 트리를 1보다 큰 차원, 즉 다차원 공간으로 일반화한 것으로 이해할 수 있습니다(1차원에서는 사실상 동일한 개념입니다).
흥미롭게도 분할 트리를 구축하는 과정은 퀵 정렬(Quick Sort)의 기하학적 버전이라고 상상할 수 있습니다. 반면 삽입과 삭제 같은 변경 연산은 병합 정렬(Merge Sort)에서 정렬된 리스트를 병합하듯, 트리끼리 병합하는 방식으로 수행됩니다.
점이 아닌 초평면(hyperplane)
여기서 한 가지 중요한 차이가 등장합니다. 점(point)은 1차원을 제외한 그 어떤 차원에서도 공간을 나눌 수 없습니다. 따라서 다차원 공간을 세분화하려면 점 대신 초평면(hyperplane)을 사용해야 합니다.
초평면은 차원에 관계없이 항상 하나의 영역을 두 개의 반공간(half space)으로 분할합니다. 바로 이 성질 덕분에 BSP 트리는 임의의 차원에서 공간을 일관되게 이분할하며, 체계적인 공간 검색 구조를 구축할 수 있는 것입니다.