Quad Tree - 2D 공간을 트리로 표현

Quad Tree의 특징

1. 재귀적(recursive)으로 2D 공간을 4개의 공간으로 분할(문제에 따라서 꼭 4개가 아닌 n개로 분할할 떄도 있음)

2. 부모 노드는 일반적으로 4개의 자식 노드(분할 횟수에 따라 자식 노드 갯수는 달라짐)를 가지고 있다. 

Quad Tree의 활용

1. 2D 물체(ex. 게임 캐릭터)의 위치를 빨리 탐색할 때!

-> 만약, 게임 속 전체 맵 속에 게임 오브젝트가 100만 개가 있다고 하자.

나의 캐릭터가 맵 속을 이동할 떄마다 실시간으로 그려져야 할 게임 오브젝트를 연산하여 모니터에 렌더링을 해 줘야 한다.

그러나, 100만 개의 게임 오브젝트를 전부 검사하여 렌더링 해줄지의 여부를 결정하게 되면, 매우 느리다.

그래서 나의 캐릭터의 위치가 4분할된 영역 중, 어디에 위치해있는지를 쿼드 트리로 알아 내어, 그 영역에 저장되어 있는 

게임 오브젝트를 찾아서 그 게임 오브젝트만 렌더링을 해주면 된다. 

시간 복잡도는 O(lgN)이 될 것이다. 

2. 큰 데이터를 압축할 떄!(ex. 허프만 코딩, 픽셀 데이터의 압축)

아래 문제를 참조하여 쿼드 트리가 어떻게 데이터 압축(enCoding)하는 지 참고!

참고로, 쿼드 트리에 의해 압축된 데이터는 stack을 이용하여 deCoding하면 된다. 

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리