목적
새벽에 백준문제를 풀다가 쿼드 트리라는 개념을 봤는데 어디서 많이 들어본 개념인데 생각이 안나서 이번기회에 정리를 해서 내것으로 만들려고한다.
쿼드트리(Quad Tree)
데이터베이스 검색에 사용되는 트리구조이다. 항상 하나의 노드에 4개의 가지로 구성되는 트리 구조로서 구하는 레코드가 나타날때까지 계속 4개로 등분해서 검색이 행해진다. 상급레벨의 정보를 공유하는 같은 사이즈의 네개의 하위레벨을 갖는 트리의 노드를 표현하는 데이터 우계구조를 사용한다.
또한 그리드의 사분면 내에서 속성의 중복 제거에 기초한 래스터 압축 기법으로도 불린다. 공간을 4개의 정사각형(이를 Quadrant라고한다.)으로 계층적으로 분할하는 원리에 바탕을 둔 위계적 자료 구조이다. 사지수형 자료 구조는 대상체를 정보의 조밀 여부에 따라 세분해 나가는 방법이며 계층적 래스터 자료 구조의 변형이다. 계층적 자료 구조란 공간 분할에 사용되는 단위의 크기를 달리해 데이터베이스를 구축한 기번으로 넓은 지역에 대한 데이터베이스 구축에 매우 용이하게 적용될 수 있다.
원 자료의 정보 그대로 자료를 저장하고 있어 단순한 자료압축의 한 기법이 아니라 래스터의 또 다른 자료구조로서 인식되기도 한다. 래스터 표현에서 상세한 위치를 나타낼때 격자의 수가 폭발적으로 증가하기 때문에 압축한 자료 구조가 필요한데 그 대표적인 것이 사지수형이며 이에는 면 사지수형(Area Quadtree)과 점 사지수형(Point Quadtree)이 있다.
공간 데이터(Spatial Data) 구성
공간 데이터: 공간 데이터 레코드는 속성으로서 위치 감각을 포함한다. 일반적으로 위치는 좌표 데이터(2D 또는 3D)로 표시된다. 위치를 핵심 값으로 공간 데이터를 검색하려면 검색시 두 가지 이상의 대안 중 선택을 효율적으로 표현하는 데이터 구조가 필요하다. 2D 데이터에 대한 한 가지 접근법은 쿼드 트리를 사용하는 것인데 각 내부 노드는 좌표 공간을 분해하여 얻은 서로 다른 영역을 나타내는 최대 4개의 자식을 가질 수 있다.
공간 분해
이진 검색 트리에서 트리의 구조는 어떤 데이터 값이 삽입되는지 뿐만 아니라 어떤 순서로 삽입되는지에 따라 달라진다. 점 영역 쿼드 틀리의 구조는 그것이 포함하는 데이터 값에 의해 전적으로 결정되며 삽입 순서와는 독립적이다.
실제로 PR 쿼드 트리의 각 노드는 2D 좌표 공간에서 특정 영역을 나타낸다. 내부 노드는 정확히 4개의 자식노드(노드 중에 일부는 비어 있을 수 있다.)를 가지고 있으며 각각은 부모 노드에 의해 표현되는 영역의 서로 다른 합동 사분면을 나타낸다. 내부 노드는 데이터를 저장하지 않는다. 리프 노드는 단일 데이터 값을 유지한다. 따라서 삽입이 수행될 때 좌표 공간이 분할되어 하나의 점 이상을 포함하는 영역이 없다. PR쿼드 트리는 유한 경계 좌표 공간의 점을 나타낸다.
공간 분할 좌표
256 x 256 좌표 공간에서 점들의 집합을 보자
좌표 공간의 세분화는 포인트가 PR 쿼드 트리에 추가될때 분할 되는 방법을 나타낸다.
PR 쿼드 트리 삽입
첫 번째 점인 A를 삽입하면 A를 보유한 리프 노드가 생성된다. 그 다음 B를 삽입하면 원래 좌표 공간이 4개의 사분면으로 분할되고 루트가 비어 있지 않은 두 자식이 있는 내부 노드로 대체된다.
각 노드가 논리적으로 표현한 영역의 SW 및 NE 코너와 리프 노드에 저장된 데이터 값을 보여준다. 구현에서 노드는 자신의 영역을 명시적으로 정의하는 정보를 저장하지 않으며 빈 리프 노드도 할당되지 않을 것이다.
삽입 중 리프 분할
C를 삽입하면 자연스럽게 빈 리프로 들어가기 때문에 좌표 공간이 추가로 분할 되지 않는다. 하지만 D를 삽입하면 SE사분면이 분할 되어 B와 D가 분리된다.
다중 분할
이제 값 E(80,80)가 트리에 삽입되었다고 가정해보자. A지점과 동일한 영역에 속하며 (0,0)에서 (128,128)까지 해당한다. 그러나 이 영역을 분할하면 세개의 빈 영역과 A와 E가 모두 있는 영역(64,64)에서 (128,128)이 생성된다. 그렇기 떄문에 그 지역은 다시 분할되어야 한다. 이렇게 하면 A와 E가 두개의 개별 영역으로 분리된다. 만약 그렇지 않다면, A와 E 둘다 있는 영역은 완전히 분리될 때까지 단시 분할되고 필요하다면 반복적으로 분할된다.
그렇기 때문에 E를 삽입하면 다음 트리가 생성된다.
삽입은 재귀적으로 진행되며 적절한 리프 노드(빈 것으로 추정)가 발견될 때까지 하강한 다음 각 리프로 표현되는 영역 내에 하나 이상의 점이 없을 때까지 분할 및 하강한다. 점들이 서로 충분히 가깝게 있는 경우, 한번의 삽입으로 관련 하위 트리에 많은 수준을 추가할 수 있다. 물론 삽입 시 분할이 필요하지 않을 수도 있다. 트리의 모양은 데이터 요소가 추가되는 순서와 완전히 독립적이다.
PR Quadtree Deletion
삭제시에는 항상 리프 노드가 적어도 하나는 제거된다.. 다음 트리에서 A를 삭제할거다.
상위 포인터를 null로 설정하면 트리에서 리프 노드가 제거되고 추가 작업이 필요하지 않다.
반면에 리프 노드를 삭제하면 상위 노드가 언더플로 될 수 있다. 이번에는 B를 한번 삭제할거다.
이제 상위 노드에서 하위 노드가 하나만 있으므로 반드시 분할해야 할 이유가 없다. 따라서 상위 노드를 나머지 하위노드(리프)로 교체하여 분기를 축소 시킬 수 있다.
branch를 축소하면 다음과 같이 된다.
이 트리의 루트 노드에 다른 자식이 없으면 branch 축소가 계속될 수 있다.
PR Quadtree Achilles' Heel
삽입된 데이터 포인트가 트리의 다른 데이터 포인트에 매우 가까운 경우, 이들을 분리하기 위해 많은 레벨의 파티셔닝이 필요할 수 있다.
PR 쿼드 트리의 최소 높이는 다음과 같을 수 있다.
여기서 s는 world의 한 변의 길이이고 d는 트리의 두 데이터 점 사이의 최소 거리이다.
버킷을 사용한 PR 쿼드 트리
각 리프 노드가 하나 이상의 데이터 객체를 저장할 수 있게 함으로써 stalky PR 쿼드 트리 분기(branch)의 문제를 완화할 수 있다.
마무리
새벽에 한참 생각했는데 알고리즘이 어려운것같다. 계속 이 알고리즘을 생각해봐야할것같다.
