[File System] ::사분트리(QuadTree)

사분트리는 공간을 순환적으로 분해하는 특성을 갖는 계층적 자료구조이다. 사분트리는 다양한 종류가 있으며 다음 기준에 따라 구분할 수 있다.

- 표현하려는 자료의 유형

- 공간 분해 과정의 원칙

- 해상도 (resolution)

1. 표현하려는 자료의 유형 : 점,영역,곡선,개체의 표면, 개체의 볼륭(volume) 데이타 등이다.

1) 사분트리는 곡선이나 표면과 같이 개체의 경계를 표현하는 경우

2) 영역이나 볼류과 같이 개체의 내부를 표현하는 경우

2. 공간 분해 원칙은

1) 각 레벨마다 공간을 일정한 크기의 동일한 부분들로 분해

2) 입력 자료값에 따라 서로 다른 크기의 공간으로 분해

3.분해의 해상도 : 분해 과정을 몇 번이나 적용하느냐?

1) 고정

2) 동적

현재 사분트리는 2차원 영역(region) 데이터를 표현하기 위해 가장 많이 사용되고 있다. (책이 2000년에 나옴, 이때 기준 ...)

이러한 응용에 사용되는 트리를 영역 사분트리라고 하며 보통 사분트리라하면 이 영역사분트리이다.

영역 사분트리는 이미지를 표현하는 2진수 배열을 연속적으로 동일한 크기의 사분면들로 분할한다.

만약에 배열이 1,0으로만 이루어져 있지않으면 1,0으로 될때까지 사분면,부속 사분면들로 분할 한다.

아래의 그림에서 (a)에 있는 영역을 이진 배열로 표현하면 (b)와 같이 되고 (c)는 (b)의 배열을 위한 결과 블록이다. 그리고 마지막으로 (d)의 트리로 표현이 가능하다.

 - 트리는 NW,NE,SW,SE로 영역의 한 사분면을 표현하기 위한 레이블이다.

 - 단말노드에는 숫자가 부여되어있고 비단말노드는 문자를 부여하였다.

 - 단말노드는 내부(1로만 구성된), 외부(0으로만 구성된)를 나타내며 흑색, 백색 노드라고 부른다.

 - 단말 노드가 아닌 노드는 0,1 모두가지고 있어서 회색노드라 한다.

점 데이터를 표현하기 위해서 점 사분트리(point quadtree)를 사용한다. 영역 사분트리와 달리 공간을 동일하지 않은 4개의 부속 공간으로 분할한다.

점 사분트리의 효율성은 탐색이 필요한 공간을 얼마나 줄이는가?에 달려있다.

K-D트리는 점사분트리를 개선한 자료구조이다.

*k-d트리는  k차원의 트리를 말한다.기본키에 의한 검색과 보조키에 의한 검색을 하나의 구조로 결합한것

ex " 수입이 50만원 이상이고 자녀가 두명 이상인 모든 직원을 찾아라 "

점 사분트리는 다차원 데이터를 처리할 수 있도록 이진 탐색트리를 일반화 시킨것이다. 예로는 아래의 그림을 보자.

k-d트리처럼 단말 노드들이 버켓에 대한 포인터를 포함한다면 인덱스 역할을 한다.

비교되는 점 데이터들만 트리에 저장되고 전체 레코드들은 인덱스에 의해 참조되는 각 버켓에 저장된다는것이다.

(..???;; 아마 포인터처럼 주소만 가지고있다는 것인듯..)

아무튼 서울-(1)에는 0≤X≤5 와 45≤X≤100의 값을 갖는 점 데이터들이 저장 된 버켓을 지시하게 된다.

삽입은 아래와 같은 과정으로 이루어진다.  ( 단 점데이터는 유일하다고 가정한다. 동일 데이터를 포함하려면 오버플로 체인의 포인터를 포함하도록하면된다)

1) 대전을 삽입하고 대전 점을 기준으로 4분면으로 나눈다.

2) 그다음 진주는 라벨링을 한 기준으로 SE에 존재하므로 SE 아래의 노드로

그다음 같은 방법으로 위치를 탐색하고 일치하는 라벨에 입력한다.

그런데 만약에 이렇게 딱! 경계선에 데이터가 들어오면 어디다가 삽입해야할까? ( 초록색 점 )

점 사분트리를 구축하는 비용은 트리의 총 경로 길이와 동일하다.  평균 삽입 비용은 이며 한 노드의 탐색비용은

이다.

최악의 경우는 최종 점 사분트리 모양에 의존하며 이는 데이터 삽입 순서에 따라 결정된다.

점 사분트리는 모든 점 데이터들을 미리 알 수 있는 경우에 최적화가 가능하다.

1) 어떤 노드의 서브트리도 전체 노드 수의 반 이상을 갖지 않는 트리로 정의

2) 이를 위해 모든 점 데이터들을 하나의 좌표축 값으로 정렬하고 다른 좌표축 값은 보조키로 사용

3) root는 정렬 파일의 중간 값을 갖게 하고, 나머지는 4개의 그룹으로 나누어 root의 4개의 서브트리가 되도록 한다.

또는 트리를 부분적으로 재균형하는 방법을 이용할 수 있다.

검색은 탐색 공간을 좁혀나가는 기법으로 진행된다. (1/4씩)

예를들어서 "좌표가 (95,8)에 위치한 도시를 검색하시오" 라는 질의가 들어오면 ㅇㅏ래처럼 순서대로

삭제는 복잡하다. 삭제할 노드를 루트로 하는 서브트리에 있는 모든 트리들이 재삽입되어야한다.

이상적인 방법으로는(책에서 말하는) 삭제할 노드[A(xa,xy)]를 임의의 노드[B(xb,yb)]로 대치한 뒤 삭제하는데 이때 임의노드는 선

x=xa,x=xb 와 y=ya, y=yb사이의 영역이 비어 있는 조건을 만족할 수 있는 노드를 선택한다.

아래의 그림에서 빗금친 곳은 점데이터가 하나도 없는 공간이다. 이 안에 만약에 점데이터가 존재하면 재삽입해야한다 (-.-)힘들힘들

예를들어 점 C가 존재한다면 점A와 점B를 ROOT로 하는 각각의 경우 존재하는 사분면이 다르기때문에 재삽입이 일어나야한다.

재삽입이 최소로 일어나기 위해서는 대체 노드와 삭제될 노드가 가장 가까운 노드를 선택해야한다.

구체적인 방법은 책의 범위를 벗어나므로 생략한다.

쿼드트리에 대한 백준문제가 있다.

백준문제에서 내준 예제를 보면 아래와 같이 트윈을 나열한 것이다. (0(0011)(0(0111)01)1) 이렇게..

어떻게 해결할까 .. 일단 분할하려면 전체 데이터를 입력받아보자. 입력은

> 영상의 크기 (max는 64)

> 다음줄부터 그만큼의 영상값이 들어온다 한다. (아래와 같다)

그럼 전체 영상크기와 영상의 데이터를 저장할 변수를 지정하자!

c언어는 역시 쓸대없이 어렵다. scanf값을 인자로 배열을 생성할 수 없군..

malloc을 사용하여야 한다.

1차원 배열은 이렇게 한다.

우리가 필요한것은 2차원 배열! 2차원배열을 만들자. 이차원 배열은 할당한곳에 또 할당하는 식으로 진행하면 된다.

그렇게 하면 입력받은 대로 배열의 크기를 초기화 시킬 수 있다. (값을 따로 안정해줫더니 호모나)

이제 사용자가 입력하는 값을 배열에 저장하자.

찾아보니까 scanf("%1d",&변수명) 이렇게 하면 1자리씩 입력이 가능하단다 호호호 신기해라

예제에 있는 값을 입력해보아도 잘 된당

자! 이제 입력은 잘 받아지니까 처리하는 함수를 만들어보자. 우선 어떻게 해야할까?

무작정 분리해서 다 검사한뒤에 1인지 0인지를 뱉어내게 할까?

아니면 하나씩 검사해서 다른 값이 나오면 분리하게 할까?

일단 하나씩 검사해보자. 그게 더 나을거같다. 무작정 다 같을지도 모르는데 분리부터 하면 음..

아래 그림처럼 이전에 검사한 친구와 현재 읽고 있는 친구와 비교해서 둘이 같으면 계속 진행 ㄱㄱ하고 그렇지 않으면 전체데이터를 4등분하는식으로 하자.

아래의 사진처럼 그냥 처음부터 검사를 시작해서 이전 값과 다를때를 찾는다.

다른 값을 만나면 나뉜대로 또 다시 검사해서 나뉜 곳은 1,0 어떤 친구들을 대리고 있는지 알아보자.

그러면 나뉜 구역 각각의 인덱스별로 다시 자리를 정해주고 다시 똑같은 검사를 하는 방식으로 진행하게 하면 되지 않을까..

그렇게 해서 결론은.. ( 백준에 제출할때는 주석 제거하고, system("pause") 제거, scanf_s는 scanf로 수정 해야한다. 안그러면 런타임,컴파일 에러뜬다

#include <stdio.h>
#include<stdlib.h>
 
void divideData(int**, int,int,int);
 
int main() {
    int **value,size;
    scanf_s("%d", &size);
 
    //배열 생성
    value = (int**)malloc(sizeof(int*)*size);
    for (int i = 0; i < size; i++) 
        value[i]= (int*)malloc(sizeof(int)*size);
 
    //값 입력 받음
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++) 
            scanf_s("%1d",&value[i][j]);
 
    divideData(value,size,0,0);
 
    system("pause");
    return 0;
}
 
void divideData(int **data,int size,int x,int y) {
    int flag = 1;
    int prv = data[y][x];
 
    for (int i = y; i < y+size; i++)
        for (int j = x; j < x+size; j++) 
            if (prv != data[i][j]) 
                flag = 0;
 
    if(flag)
        printf("%d", prv);
    else {
        printf("(");
        divideData(data, size / 2, x, y);
        divideData(data, size / 2, x + size / 2, y);
        divideData(data, size / 2, x, y + size / 2);
        divideData(data, size / 2, x + size / 2, y + size / 2);
        printf(")");
    }
}

* 28번 라인 y,x 인덱스는 x,y로 해도되는데 대신 40,41 라인을 순서를 변경해야한다. 

* size를 1/2을 했기때문에 for문 돌릴때 x,y값을 더해주는것이다.

그림출처 :