공간 검색 구조는 60년대와 70년대에 컴퓨터 과학에서 발명된 동일한 아이디어를 기반으로 하며, 기하학적 데이터(예:사람 이름 목록)와 달리 기호 데이터의 큰 집합을 빠르게 처리하는 문제를 해결합니다. 먼저 알파벳에 따라 이름 목록을 정렬하고 정렬된 목록을 배열에 저장하면 n/2가 아닌 이진 검색 알고리즘을 사용하여 log2n 작업에서 일부 새 이름이 목록에 이미 있는지 여부를 계산할 수 있다는 것이 발명되었습니다. 순차 검색의 도움으로 필요한 예상 작업. 이것은 이름 목록에 존재하는 구조(알파벳 순서)를 추출하고 후속 작업(이름 조회)에서 해당 구조를 활용하여 계산을 줄이는 좋은 예입니다.
그러나 정렬된 목록을 유지하면서 이름의 추가 및 삭제를 허용하려면 동적 데이터 구조, 즉 포인터를 구현하는 데이터 구조가 필요합니다. 이러한 데이터 구조의 가장 일반적인 예 중 하나는 이진 검색 트리입니다.
이진 탐색 트리의 경우 실제 행에 있는 A ={1, 2, 5, 6, 7, 9}와 같은 정수 집합을 나타내도록 구현됩니다. 숫자/포인트가 이미 트리에 있는지 여부를 계산하려면 트리에 포인트를 삽입하고 해당 포인트로 구성된 중첩 간격 시퀀스에 해당하는 경로를 따라갈 수 있습니다. 균형 트리의 경우 이 프로세스는 O(log n) 단계만 소비합니다. 사실 우리는 이진 검색을 수행했지만 배열이 아닌 트리를 구현하는 검색을 수행했습니다. 이제 트리 자체는 검색이 진행되는 순서를 결정하기 때문에 검색 알고리즘의 일부를 인코딩할 수 있습니다.
이것은 이제 파티셔닝 트리로 돌아가게 하며, 이진 검색 트리를 차원> 1, 즉 다차원(1D에서 본질적으로 동일함)으로 일반화한 것으로 처리됩니다. 사실, 파티셔닝 트리를 구축하는 것은 빠른 정렬의 기하학적 버전으로 상상할 수 있습니다.
병합 정렬에서 정렬된 목록을 병합하는 것과 유사한 트리 병합으로 변경(삭제 및 삽입)이 수행됩니다.
그러나 점은 1보다 큰 차원에 대해 공간을 분할하지 않으므로 분할할 점보다 초평면을 구현해야 합니다.
초평면은 차원에 관계없이 항상 영역을 두 개의 절반 공간으로 세분화하거나 분할합니다.