토픽 51 / 66·확률적 자료구조

쿼드트리 (Quadtree)

2차원 공간을 4개의 사분면으로 재귀적으로 분할하는 트리 자료구조로, 각 노드가 4개의 자식(NW, NE, SW, SE)을 가지며 공간 인덱싱과 충돌 감지에 사용

목적: 2D 공간 분할, 충돌 감지, 이미지 압축, 공간 쿼리

특징: 4진 트리, 재귀적 분할, 공간 적응적, 계층 구조

구성요소: ① 노드(경계 영역) ② 4개 자식(NW(North-West): 좌상, NE(North-East): 우상, SW(South-West): 좌하, SE(South-East): 우하) ③ 데이터(점 또는 객체) ④ 최대 용량(분할 기준)

동작: 노드에 점/객체 삽입 → 용량 초과 시 4개 사분면으로 분할 → 재귀적으로 삽입

종류

시간 복잡도: 삽입·검색·삭제 평균 O(log n), 최악 O(n)

공간 복잡도: O(n)

장점: 공간 쿼리 효율(범위/최근접), 동적 분할, 이미지 압축, 충돌 감지 빠름

단점: 불균형 가능, 2D만 지원, 구현 복잡도

적용사례: 게임(충돌 감지), 이미지 압축, GIS(지리 정보), 컴퓨터 그래픽스, 메시 생성

비교: Quadtree(2D/4분할) vs Octree(3D/8분할) vs KD-Tree(k차원/2분할)

연관: Octree, KD-Tree, 공간 분할, 충돌 감지