이분 나무와 빨강 검정 나무 + 용어 색인 생성 프로그램

tree는 범용적으로는 족보나 디렉토리 구조처럼 뭔가 계층이라는 속성을 지닌 체계를 기술하기 위해 사용되는 개념이지만, 전산학에서는 tree에 특수한 조건을 두어 이를 범용적인 자료구조 모델로 사용하기도 합니다. 나무 중에서 사람의 양 팔처럼 한 노드 아래에 가지가 최대 두 개까지만 존재하는 나무를 이분 나무라고 하며, 왼쪽 가지에는 언제나 부모보다 작은 값만 존재하고 오른쪽 가지에는 언제나 부모보다 큰 값만 존재하는 나무를 이분 검색 나무(binary search tree)라고 합니다.

tree는 배열이나 연결 리스트처럼 선형적인 자료구조가 아니어서 임의의 ‘인덱스’에 대한 random access가 곤란하고 다루기가 까다로워 보이지만, 삽입과 삭제가 빈번하게 발생하면서도 일관된 정렬 순서 유지와 빠른 검색 속도가 요구되는 상황에서 매우 좋은 성능을 발휘합니다. dynamic set을 구현하는데 최적의 자료형입니다.

이 프로그램에서는 단순한 이분 검색 나무를 CTree라는 템플릿 클래스로 먼저 구현했습니다. 이걸 구현하는 것은 그리 어렵지 않습니다. 컨테이너 대상이 되는 타입은 ==(동등), <(비교) 연산만 상호 정의되어 있으면 됩니다.

하지만 아무런 자체 제어가 없는 이분 나무는 같은 자료라고 해도 자료가 입력된 순서에 따라 나무의 모양이 크게 달라지며, 특히 크기가 순차적으로 커지거나 작아지기만 하는 자료가 입력되면 나무의 깊이가 한쪽 노드로만 쏠리면서 연결 리스트와 조금도 다를 바 없는 비효율적인 형태가 됩니다. 퀵 정렬이 최악의 상황에 시간 복잡도 O(n2)와 메모리 복잡도 O(n)이 될 수 있는 것과 같은 이치입니다.

스스로 균형 잡는 나무

이 문제를 해결하기 위해 자료구조 교재의 한창 뒷부분에 나오는 것이 바로 스스로 균형 잡는(self-balancing) 나무입니다. 각 노드마다 본디 데이터 외에 내부적으로 사용하는 부가정보를 추가하고, 그에 맞춰 자료의 삽입/삭제 시에 최대한 각 노드들의 좌우 노드가 균형 있게 사용되고 나무의 전체 깊이가 n이 아닌 log n에 비례하도록 부가작업을 하는 것입니다. 그래서 아까와 같은 최악의 순서로 데이터가 들어오더라도 삽입, 삭제, 검색이 모두 언제나 log n의 시간 복잡도가 보장되도록 한 것이 스스로 균형 잡는 나무의 특징입니다. 그야말로 만능 자료구조가 아닐 수 없습니다.

이런 자료구조에 대한 소개가 뒷부분에 나오는 이유는 그 부가작업이란 것이 복잡하고 이해하기 꽤 어렵기 때문입니다. 이분 검색 나무의 기본적인 특징을 그대로 유지하면서 자가균형이 구현된 나무의 대표적인 예는 AVL 나무와 빨강-검정 나무입니다. 여기서는 빨강-검정 나무를 CTree에 이어 CTreeEx라는 템플릿 클래스로 구현했습니다. 두 클래스는 상속 관계는 아니지만 사용법은 완전히 같습니다. Insert, Delete, Lookup, GetCount, ResetContent 정도만 알면 되고 각 함수들이 하는 일에 대해서는 별도의 설명이 필요 없을 것입니다.

빨강-검정 나무는 자가균형을 유지하기 위해 각 노드마다 덧붙이는 추가 정보량이 빨강-검정이라는 1비트에 불과하며, AVL 나무보다 구현하기 쉽고 삽입/삭제 시의 부담도 더 적습니다. AVL 나무만치 철저하게 균형을 잡아 주지는 못하지만, 이는 비례상수 수준의 차이일 뿐 나무의 평균 깊이가 log n에 비례한다는 것은 변함없이 보장됩니다. STL에서 map, set 등의 컨테이너도 내부적으로는 대부분 빨강-검정 나무를 사용하여 구현되어 있습니다.

빨강-검정 나무의 삽입, 삭제 과정을 교과서적으로 아래에서 위로(bottom-up) 구현했을 경우 재귀호출이 일어나거나 별도의 스택 배열, 아니면 심지어 노드 구조체마다 부모 노드 포인터가 필요해집니다. 실제로 STL이 사용하는 빨강-검정 나무의 노드 구조체에는 부모 노드에 대한 포인터가 있습니다. STL의 스펙에 따라 iterator로 나무 안의 각 원소들을 별도의 스택 없이 순회하려면 그게 반드시 필요하기 때문입니다. 하지만 이 프로그램은 재귀호출 없이 단순 이분 나무에서 삽입, 삭제를 하듯이 top-down 방식으로 원소를 처리하며 부모 노드 포인터도 사용하지 않습니다. 단순 이분 나무의 간결함과 빨강-검정 나무의 성능만을 취했습니다.

CTreeEx는 CTree와는 달리, 원소를 삭제할 때 컨테이너 대상 타입에 대해 =(대입) 연산을 추가로 사용합니다. 그렇기 때문에 Delete 함수까지 사용하는 경우 여기에 대한 적절한 처리가 추가로 필요합니다.

예제 프로그램

이 클래스를 사용하여 용어 색인 생성 프로그램을 만들었습니다. 텍스트 파일을 쭉 읽어들인 후, 그 파일에 들어있는 단어들을 모두 분리하여 알파벳 순으로 정렬하되, 그 단어가 등장한 줄번호를 같이 나열해 줍니다. 단어는 트리 구조이고 등장 줄 번호는 간단한 단일 연결 리스트로 저장합니다. 트리를 사용한 응용 프로그램으로 이보다 더 적절한 예는 없는 것 같습니다.

CTree는 구현만 해 놓았고, 실제 자료구조는 이보다 더 효율적인 자가균형 나무인 CTreeEx를 사용했습니다.

소스 코드, 실행 파일, 예제 데이터 받기 (src18_tree.zip, 9K)

input.txt의 일부

# Paul, a prisoner of Jesus Christ, and Timothy our brother, unto Philemon our dearly beloved, and fellowlabourer,
And to our beloved Apphia, and Archippus our fellowsoldier, and to the church in thy house:
Grace to you, and peace, from God our Father and the Lord Jesus Christ.
# I thank my God, making mention of thee always in my prayers,
Hearing of thy love and faith, which thou hast toward the Lord Jesus, and toward all saints;

(신약성경 빌레몬서의 내용입니다. 후략)

그때 출력 결과의 일부

a (9): 1 9 15 16 17 22 25
above (1): 16
account (1): 18
acknowledging (1): 6
again (1): 12
aged (1): 9
albeit (1): 19
all (1): 5
also (3): 9 21 22
always (1): 4
Amen (1): 25
an (1): 9
And (1): 2

(후략)

나무 각 원소들에 대한 순회 (iteration)

앞서 말씀드렸듯이 나무는 선형적인 자료구조가 아니기 때문에 모든 자료를 처음부터 끝까지 순차적으로 탐색하기가 까다로운 편입니다.

나무는 순회를 어떤 방식으로 하냐에 따라서 원소가 나열되는 순서가 달라진다는 것이 매우 흥미롭습니다. 자기 노드부터 먼저 출력한 뒤 자식 노드로 들어가는 것을 전위(preorder) 순회라고 하고, 자기 왼쪽의 자식을 먼저 출력한 뒤 내 원소를 출력하고 오른쪽으로 제어를 넘기는 것을 중위(inorder) 순회, 끝으로 자신의 모든 자식부터 먼저 출력한 뒤 자신이 가진 원소를 출력하는 것을 후위(postorder) 순회라고 합니다.

CTree에는 재귀적으로 콜백 함수를 호출하는 InOrder, PreOrder, PostOrder 함수가 정의되어 있습니다. 그 반면 CTreeEx는 자체적인 스택을 갖춘 enumerator 클래스가 따로 정의되어 있어서 while, for문 안에서 루프 돌듯이 간단하게 나무 안의 원소들을 셋 중 어느 순서대로나 순회할 수 있습니다. 그 쓰임새는 아래와 같습니다.

CTree<int> tr; //단순 이분 검색 나무 + 콜백 함수 기반 순회
CTreeEx<int> trex; //빨강 검정 나무 + 자체 스택 기반 순회

const int idd[]={ 11, 5, 16, 2, 9, 13, 20, 1, 3, 8, 10, 12, 14, 17, 23, 0 };
//const int idd[]={ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, 0 };
for(const int *p=idd; *p; p++) { tr.Insert(*p); trex.Insert(*p); }

puts("재귀호출에 의한 순회");
puts("PreOrder:");
tr.PreOrder(CallbackFunc, NULL); puts("");

puts("InOrder:");
tr.InOrder(CallbackFunc, NULL); puts("");

puts("Postorder:");
tr.PostOrder(CallbackFunc, NULL); puts(""); puts("");

puts("비재귀 방식에 의한 순회");
CTreeEx<int>::CEnumerator en;

puts("PreOrder:");
en.Init(trex, CTreeEx<int>::MIDDLE);
while(en.CanFetch()) printf("%d ", en.GetNextPreOrder()); puts("");

puts("InOrder:");
en.Init(trex, CTreeEx<int>::LEFT_END);
while(en.CanFetch()) printf("%d ", en.GetNextInOrder()); puts("");
en.Init(trex, CTreeEx<int>::RIGHT_END);
while(en.CanFetch()) printf("%d ", en.GetNextInOrder(CTreeEx<int>::RIGHT_END)); puts("");

puts("PostOrder:");
en.Init(trex, CTreeEx<int>::LEFT_END);
while(en.CanFetch()) printf("%d ", en.GetNextPostOrder()); puts("");

콜백 함수는,

void CALLBACK CallbaclFunc(int& typ, PVOID context)
{
	printf("%d ", typ);
}

프로그램의 실행 결과는 다음과 같습니다.

재귀호출에 의한 순회
PreOrder:
11 5 2 1 3 9 8 10 16 13 12 14 20 17 23
InOrder:
1 2 3 5 8 9 10 11 12 13 14 16 17 20 23
Postorder:
1 3 2 8 10 9 5 12 14 13 17 23 20 16 11

비재귀 방식에 의한 순회
PreOrder:
11 5 2 1 3 9 8 10 16 13 12 14 20 17 23
InOrder:
1 2 3 5 8 9 10 11 12 13 14 16 17 20 23
23 20 17 16 14 13 12 11 10 9 8 5 3 2 1
PostOrder:
1 3 2 8 10 9 5 12 14 13 17 23 20 16 11

데이터가 콜백 함수를 통해 넘어왔을 때에 맞춰서 처리를 해야 하는 재귀 버전보다, 내가 원하는 때에 얼마든지 반복문 안에서 데이터를 꺼내올 수 있는 비재귀 버전이 사용하기 더 편리할 것입니다. Init는 CEnumerator 오브젝트의 내부 상태를 검색 대상인 CTreeEx에 맞게 초기화하는 역할을 합니다. 중위나 하위 순회를 하기 위해서는 초기에 나무의 가장 작은 원소에 가 있어야 하고(오름차순 기준), 전위 순회를 하기 위해서는 그냥 나무의 root에 맞춰 놓으면 됩니다. 이것이 MIDDLE 또는 LEFT/RIGHT_END 상수의 의미입니다.

재귀 버전은 언제나 오름차순으로만 순회할 수 있는 반면 비재귀 버전은 방향을 지정해서 보다시피 내림차순 순회도 가능합니다. 그리고 순회 도중에라도 얼마든지 순회 방식(전/중/후위)과 순회 방향을 바꿀 수 있습니다.

위의 예에서는 나무가 완전히 균형잡힐 수 있는 순서대로 자료가 입력되었기 때문에 두 나무의 순회 결과가 완전히 같습니다. 하지만 자료가 1부터 15까지 오름차순으로 입력된 경우 일반 나무와 자가균형 나무는 내부 구조에 차이가 생기게 됩니다.

재귀호출에 의한 순회
PreOrder:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
InOrder:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Postorder:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

비재귀 방식에 의한 순회
PreOrder:
4 2 1 3 8 6 5 7 10 9 12 11 14 13 15
InOrder:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
PostOrder:
1 3 2 5 7 6 9 11 13 15 14 12 10 8 4

CTree는 깊이가 15인 불균형 나무(연결 리스트와 동일)가 된 반면, CTreeEx는 최대 깊이가 6입니다. 원소가 15개이니 이상적인 최대 깊이의 최소값은 4이지요.