하나의 부모 아래에 복수 개의 자식이 포함될 수 있는 구조를 계층적(Hierarchical)이라고 하는데 이런 자료는 아주 흔하다. 회사의 조직도, 우편 번호부, 상품 분류표 등 일상 생활에서도 흔히 접할 수 있는 정보들이 모두 계층적이며 프로그램이 이런 자료를 다루어야 하는 경우가 많다.
원론적으로 계층적인 자료들은 트리(Tree)로 관리할 수 있지만 너무 복잡하고 비효율적인데다가 데이터 베이스의 테이블 구조와는 맞지 않다. 관계형 데이터 베이스의 테이블은 배열 형태로 되어 있다. 그래서 계층적인 자료라도 통상 배열이나 연결 리스트를 사용하는 간단한 방법을 많이 사용하는데 각 레코드에 부모가 누구인지를 표시함으로써 레코드간의 계층을 구성한다.
시군행정도를 배열로 표현해 보도록 하자. 행정도는 대한민국이라는 루트 레코드 아래에 서울시, 경기도, 강원도 등이 있고 강원도 아래에 속초시, 원주시, 춘천시 등이 있는 전형적인 계층 구조이다. 다음 예제의 arCity 배열이 이런 계층적인 관계를 일차원의 배열로 기억한다.
|
예 제 : CityTree |
#include <Turboc.h>
struct tag_City
{
int Parent;
TCHAR *Name;
};
tag_City arCity[]={
-1,"대한민국",
0,"서울특별시",
1,"동대문구",
2,"청량리동",
2,"회기동",
2,"신설동",
1,"한강구",
6,"퐁당동",
6,"월척동",
0,"경기도",
9,"화성시",
9,"금성시",
9,"목성시",
};
BOOL HaveChild(int idx)
{
int i;
for (i=0;i<sizeof(arCity)/sizeof(arCity[0]);i++) {
if (arCity[i].Parent == idx) {
return TRUE;
}
}
return FALSE;
}
void PrintCity(int Parent,int indent)
{
int i,j;
for (i=0;i<sizeof(arCity)/sizeof(arCity[0]);i++) {
if (arCity[i].Parent == Parent) {
for (j=0;j<indent;j++) putch(' ');
printf("%s\n",arCity[i].Name);
if (HaveChild(i)) {
PrintCity(i,indent+2);
}
}
}
}
void main()
{
PrintCity(-1,0);
}
tag_City 구조체가 하나의 레코드인데 Parent 멤버가 부모 레코드의 첨자를 기억하며 Name은 행정명이다. arCity 배열의 초기값을 분석해 보면 대한민국의 부모는 -1로 지정되어 있어 루트임을 표시하고 있다. 서울특별시, 경기도는 대한민국의 자식 레코드이므로 부모가 0번 레코드로 지정되어 있으며 동대문구, 한강구의 부모는 1번 첨자인 서울특별시로 되어 있다. 퐁당동, 월척동은 한강구 아래에 있으므로 부모의 첨자가 6번이다.
arCity 배열은 재귀적인 계층적 구조를 가지고 있으므로 이 배열을 순회하려면 재귀 호출을 사용해야 한다. 예제에서는 arCity에 포함된 모든 레코드를 순회하면서 트리 형태로 출력하는 PrintCity 함수를 작성하고 있다. PrintCity 함수는 Parent 아래의 모든 차일드를 indent 위치에 출력한다. indent는 들여쓰기 정도를 의미하며 계층 구조상의 레코드 깊이를 표현한다. 자식 레코드는 부모보다 두 칸 더 들여쓰는 것이 보기에 좋다. main 함수에서 PrintCity(-1,0)을 호출하여 루트 레코드 아래의 모든 자식들을 들여쓰기 0에 출력한다. 이후 대한민국 아래의 모든 레코드를 출력하는 일은 PrintCity 함수가 담당한다.
PrintCity 함수는 루프를 돌며 부모가 Parent인 모든 레코드를 검색해서 출력하되 만약 이 레코드가 자식을 거느리고 있으면 재귀 호출이 발생한다. 최초 main에서 Parent값으로 -1을 주었고 부모가 -1인 레코드는 대한민국 하나밖에 없으며 이 레코드 아래에 서울시, 경기도가 있으므로 두 번 재귀 호출이 발생할 것이다. 이때 indent를 2 증가시켜 부모보다 조금 더 들여 쓰도록 했다. 출력 결과는 다음과 같다.
대한민국
서울특별시
동대문구
청량리동
회기동
신설동
한강구
퐁당동
월척동
경기도
화성시
금성시
목성시
대한민국 아래의 레코드들이 보기좋게 들여쓰기되어 출력되었다. 그래픽 환경이라면 부모와 자식간의 관계를 직선으로 연결하여 좀 더 보기 좋게 출력할 수도 있고 Win32 트리 뷰 컨트롤을 사용하면 탐색기처럼 계층적인 노드를 생성할 수도 있을 것이다. 특정 레코드밑에 자식이 있는지 없는지는 HaveChild 함수로 간단하게(그러나 조금 비효율적으로) 검사했다.
이 함수는 불필요한 재귀 호출을 막아주는 역할을 하는데 사실 이 예제에서는 꼭 필요치 않다. 무조건 PrintCity를 재귀 호출해도 자식이 없는 레코드는 빈 루프만 돌다가 헛탕치고 돌아올 것이다. 앞 항의 FileList 예제도 마찬가지로 디렉토리이기만 하면 무조건 재귀 호출을 했는데 이 경우는 갔다가 그냥 돌아오는 시간이 디렉토리 안에 파일이 있는지 검사하는 것과 별반 차이가 없기 때문이다. 그러나 그렇지 않은 경우는 자식을 가지지 않은 항목에 대해서는 가급적 재귀 호출을 자제해야 한다. 예를 들어 헛탕치고 돌아오는데도 굉장한 시간이 걸린다거나 자료에 어떤 변형을 가하는 동작을 할 경우가 이에 해당된다.
PrintCity 함수는 지정한 레코드의 모든 자식(그 아래의 자식까지)을 출력하므로 main에서는 대한민국 아래를 출력하도록 PrintCity 함수만 호출하면 된다. 물론 원한다면 서울시 아래의 행정명만 출력하는 것도 가능하다. 이 함수는 루프를 돌며 Parent 아래의 모든 자식들을 출력하되 자식이 있는 레코드는 재귀 호출하여 문제의 범위를 점점 좁혀가는 방법을 사용한다. 만약 재귀 호출을 쓰지 않는다면 이 문제는 대단히 풀기 어려운데 직접 시도해 보면 아마 잘 안될 것이다. 논리적으로 가능은 하지만 코드가 길어지고 속도도 이 예제보다 느리다.
재귀 호출을 실제 문제에 적용하는 일반적인 법칙 같은 것은 없다. 실제 문제의 복잡성과 특성에 따라 전달할 인수와 반환점, 지역변수 목록, 루프의 구조를 적절하게 선택해야 한다. 어떤 경우는 물리적인 한계로 인해 지역변수를 마음대로 쓸 수 없는 상황도 있다. arCity 배열은 언제든지 참조할 수 있는 배열이지만 이런 데이터가 데이터 베이스에 저장되어 있다거나 네트워크를 통해 전송받는 경우는 값을 읽는 방법의 특성을 잘 고려해야 한다. arCity가 데이터 베이스에 들어 있다면 이 함수의 형태는 아마 다음과 같이 변경되어야 할 것이다. 편의상 들여쓰기 기능은 제외하도록 하자.
void PrintCity(int Parent)
{
Parent 아래의 자식들 목록 조사하는 쿼리 실행
for (child=첫째~막내) {
child의 이름 출력
if (child의 자식이 있으면)
PrintCity(child);
}
}
arCity 배열을 읽는 대신 쿼리(Query)문으로 조건에 맞는 레코드를 검색하도록 했다. 일반적으로 쿼리의 결과셋은 데이터 베이스 서버가 가지므로 클라이언트의 입장에서 결과셋은 전역적이라는 특성이 있다. 결과셋은 함수 호출 인스턴스별로 스택에 유지되지 않으며 재귀 호출된 함수가 새로운 쿼리를 실행하는 즉시 이전 결과셋은 파괴되어 버린다. PrintCity가 재귀 호출된 후 리턴되었을 때 현재 함수는 결과셋을 잃어 버리게 되고 계속적인 검색을 할 수 없다.
이는 네트워크를 통해 데이터를 전송받을 때도 마찬가지이다. 근본적으로 지역 쿼리나 지역 네트워크 접속이라는 것이 어렵기 때문에 이런 경우는 쿼리를 하면서 재귀 호출을 하는 것이 불가능하다. 그래서 한 번 쿼리를 할 때 서버에 있는 결과셋을 클라이언트로 모조리 복사해야 하며 사본을 뜬 후 재귀 호출을 해야 리턴했을 때 다음 결과셋을 제대로 읽을 수 있다.
void PrintCity(int Parent)
{
Parent 아래의 자식들 목록 조사하는 쿼리 실행
결과셋의 결과만큼 배열 할당 후 사본 복사
for (child=첫째~막내) {
child의 이름 출력
if (child의 자식이 있으면)
PrintCity(child);
}
배열 해제
}
각 호출 인스턴스는 전역 퀴리를 사용하되 결과셋의 사본을 별도의 메모리 공간에 복사해 둔다. 결과셋이 스택에 저장되는 지역변수가 아니기 때문에 각 호출 인스턴스마다 메모리를 동적으로 할당해서 저장해야 한다. 전역적인 쿼리 결과를 지역적인 사본으로 만들어서 각 함수 호출 인스턴스가 자기만의 결과셋을 가질 수 있도록 해 주는 것이다.
CityTree 예제는 레코드가 부모 레코드의 배열상 첨자를 기억하는데 이 방식을 쓰면 1차원 배열로 간편하게 계층 구조를 표현할 수 있고 자식들의 순서가 꼭 정렬되어 있지 않아도 상관없다. 대신 부모 레코드의 첨자를 기억하고 있기 때문에 삽입, 삭제에 의해 부모의 첨자가 변경될 경우 자식들이 참조하고 있는 부모의 첨자를 조정해 주어야 하는 단점이 있다. 이런 문제를 해결하려면 배열상의 첨자가 아닌 고유의 id를 각 항목에 할당하고 자식들은 부모의 id를 가리키도록 하면 된다. 다음은 수정된 예제이다.
|
예 제 : CityTree2 |
#include <Turboc.h>
struct tag_City
{
int id;
int Parent;
TCHAR *Name;
};
tag_City arCity[]={
0,-1,"대한민국",
1,0,"서울특별시",
2,1,"동대문구",
3,2,"청량리동",
4,2,"회기동",
5,2,"신설동",
6,1,"한강구",
7,6,"퐁당동",
8,6,"월척동",
9,0,"경기도",
10,9,"화성시",
11,9,"금성시",
12,9,"목성시",
};
BOOL HaveChild(int idx)
{
int i;
for (i=0;i<sizeof(arCity)/sizeof(arCity[0]);i++) {
if (arCity[i].Parent == idx) {
return TRUE;
}
}
return FALSE;
}
void PrintCity(int Parent,int indent)
{
int i,j;
for (i=0;i<sizeof(arCity)/sizeof(arCity[0]);i++) {
if (arCity[i].Parent == Parent) {
for (j=0;j<indent;j++) putch(' ');
printf("%s\n",arCity[i].Name);
if (HaveChild(arCity[i].id)) {
PrintCity(arCity[i].id,indent+2);
}
}
}
}
void main()
{
PrintCity(-1,0);
}
tag_City 배열에 id 멤버를 추가하고 각 배열 요소가 중복되지 않는 고유의 id를 가지도록 했다. PrintCity 함수에서 HaveChild를 호출할 때 배열 첨자인 i 대신 arCity[i].id를 사용하며 재귀 호출을 할 때도 arCity[i].id를 사용함으로써 배열상의 순서에 상관없이 계층 구조를 순회할 수 있다. 이렇게 되면 배열상의 순서가 바뀌어도 id는 항상 일정하므로 항목의 순서는 아무 의미가 없어진다. 다음과 같이 arCity 배열을 마구 뒤섞어 놓고 실행해도 결과는 동일하다.
tag_City arCity[]={
4,2,"회기동",
10,9,"화성시",
11,9,"금성시",
5,2,"신설동",
1,0,"서울특별시",
2,1,"동대문구",
12,9,"목성시",
3,2,"청량리동",
7,6,"퐁당동",
8,6,"월척동",
0,-1,"대한민국",
9,0,"경기도",
6,1,"한강구",
};
항목끼리 id가 중복되지 않고 자식들이 부모의 id를 제대로 가리키고만 있으면 배열상의 순서가 바뀌어도 id는 항상 일정하므로 항목의 추가, 삭제, 이동이 자유롭다. 이 방식대로라면 실행중에 트리를 편집할 수도 있다. 배열상의 첨자를 부모의 id로 사용하는 방법은 구조가 간편하므로 우편번호부같이 변경되지 않는 정적인 트리를 표현하는데 적합하며 별도의 id를 사용하는 방법은 회사 조직도나 디렉토리와 파일 계층같은 동적인 트리를 관리하는데 적합하다.