포인트 쿼드트리는 2차원 포인트 데이터를 나타내기 위해 구현된 이진 트리의 적응입니다. 모든 쿼드트리의 기능은 포인트 쿼드트리에서 공유됩니다.
일반적으로 O(log n) 시간에 실행되는 2차원의 정렬된 데이터 포인트를 비교하는 데 매우 효율적입니다. 포인트 쿼드트리는 완전성에 대해 언급할 가치가 있지만 k-d 트리는 일반화된 이진 검색을 위한 도구로서 이를 능가합니다.
포인트 쿼드트리는 다음과 같이 구성됩니다.
삽입할 다음 포인트가 주어지면 그것이 있는 셀을 계산하고 트리에 추가합니다.
새 점이 포함된 셀이 점을 통과하는 수직선과 수평선에 의해 사분면으로 분할되도록 새 점이 추가됩니다. 결과적으로 셀은 직사각형이지만 반드시 정사각형은 아닙니다.
이 트리에서 각 노드는 입력 포인트 중 하나로 구성됩니다.
평면의 분할은 점-삽입 순서에 따라 결정되기 때문에 트리의 높이는 삽입 순서에 민감하고 종속적입니다. 잘못된 순서로 삽입하면 입력 포인트 수에서 선형 높이 트리가 생성될 수 있습니다(이 시점에서 연결 목록이 됨).
포인트셋이 정적인 경우 전처리를 통해 균형 잡힌 높이의 트리를 구축할 수 있습니다.
포인트 쿼드트리의 노드 구조
포인트 쿼드트리의 노드는 이진 트리의 노드와 동일하지만 주요 차이점은 다음과 같이 2개("왼쪽" 및 "오른쪽") 대신 4개의 포인터(각 포인터는 각 사분면에 사용됨)와 연결된다는 것입니다. 일반 이진 트리에서. 또한 키는 일반적으로 x 및 y 좌표를 참조하여 두 부분으로 나뉩니다.
따라서 노드는 다음 정보로 구성됩니다.
- 4개의 포인터:쿼드['NW'], 쿼드['NE'], 쿼드['SW'] 및 쿼드['SE']입니다.
- NW-북서쪽, NE-북동쪽, SW-남서쪽, SE-남동쪽
- 포인트; 다음으로 구성됩니다.
- 키; 일반적으로 x, y 좌표로 표시
- 값; 이름과 같은