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

쿼드트리 특징

-degree가 4인 트리(각 사분면에 속하는 요소가 한 개일때까지 나눈다) 

-performance: O(log4n)

-불균형 트리

 

 

위의 쿼드 트리의 노드를 각 사분면 별로 mapping해서 트리형식으로 표현하면 아래와 같다. (왼쪽부터 차례대로 1,2,3,4사분면)

쿼드트리에서 root노드는 실제로 존재하지 않지만 mapping하여 표현할 때는 root노드를 그려준다. 

 

 

나뉘어진 사분면의 개수와 각 사분면에 있는 1의 개수를 세는 함수이다. 

char graph[25][25];
int region[625] = { 0, };

int quad(int i, int j, int n, int cnt)
{
    graph[i][j] = 0;
    region[cnt]++;

    if (i - 1 >= 0 && graph[i - 1][j] == '1') 
        quad(i - 1, j, n, cnt);
    if (i + 1 < n && graph[i + 1][j] == '1')
        quad(i + 1, j, n, cnt);
    if (j - 1 >= 0 && graph[i][j - 1] == '1')
        quad(i, j - 1, n, cnt);
    if (j + 1 < n && graph[i][j + 1] == '1')
        quad(i, j + 1, n, cnt);

    return 0;
}