[자료구조] 쿼드 트리 (Quad Tree)

쿼드 트리란?

---

자식노드가 4개인 트리를 말합니다.

 

 

 

쿼드 트리의 쓰임

---

쿼드 트리의 대표적인 문제가 흑백 영상의 데이터를 압축하는 문제입니다.

 

 

위의 그림의 과정은 다음과 같습니다.

1. 가장 처음의 맵이 모두 흰색(0)이거나, 모두 검은색(1)이 아니기 때문에 압축할 수 없습니다. 따라서, 맵을 4등분합니다. (위의 그림에서 빨간색 라인)
2. 4등분된 맵에서 각각의 구간을 살펴보면, 왼쪽 위 구간은 모두 0이기 때문에 압축이 가능합니다. 따라서, 하나의 0으로 표현합니다.
3. 오른쪽 위 구간은 모두 흰색(0)이거나, 모두 검은색(1)이 아니기 때문에 압축할 수 없습니다. 따라서, 맵을 다시 4등분합니다.
4. 모든 구간들을 계속 반복합니다.