5장 - Threaded Binary Tree/Selection Tree

Treaded Binary Tree

n개의 노드를 갖는 이진 트리에는 2n개의 링크가 존재하는데,

2n개의 링크 중 n+1개의 링크의 값은 null이다(단말노드)

이 null링크들을 다른 노드에 대한 포인터로 대체하자.

 

• ptr->left_child=NULL인 경우 inorder predecessor을 가리키도록 변경
• ptr->right_child=NULL인 경우 inorder successor을 가리키도록 변경

 

노드의 구조

struct thread_tree {
	short int left_thread;
	struct thread_tree* left_child;

	char data;

	short int right_thread;
	struct thread_tree* right_child;

};

기존의 노드에서 

left_thread, right_thread가 추가되었다. 

child가 가리키는 것이 자식 노드인지, inorder predecessor/successor인지 알 수 있게 하는 flag이다.

 

추가로, Head Node가 존재한다.

트리에서 가장 왼쪽 노드의 inorder predecessor은 Head Node를 가리키고,

가장 오른쪽 노드의 inorder successor은 Head Node를 가리키게 한다.

Head Node의 left child는 root, right child는 head node(자기자신)이다.

 

Inorder Traversal

ptr이 현재 노드를 가리킬 때 ptr->right_thread가 true(1)이라면, inorder successor == right_child이다.

아닌 경우에는, ptr->right_child로 간 다음, left_child를 따라 단말 노드가 나올 때까지 내려간다. 그럼 해당 노드가 inorder successor임.

 

struct thread_tree* insucc(struct thread_tree* ptr)
{//ptr의 inorder successor 리턴하는 함수
	struct thread_tree* temp = ptr->right_child;
	if (ptr->right_thread == false) {
		while (temp->left_thread == false) {
			temp = temp->left_child;
		}
	}
	return temp;
}

 

이 insucc함수를 활용한 중위순회

void t_inorder(struct thread_tree* tree) {
	struct thread_tree* temp = tree;
	for (;;) {
		temp = insucc(temp);
		if (temp == tree)
			break;
		printf("%3c", temp->data);
	}
}

 

노드를 추가하기

r_child로 새 노드를 추가하는 방법.

void insert_right(struct thread_tree* parent, struct thread_tree* child)
{
	struct thread_tree* temp;
	child->left_child = parent;
	child->left_thread = true;
	child->right_child = parent->right_child;
	child->right_thread = parent->right_thread;
	
	parent->right_child = child;
	parent->right_thread = false;

	if (child->right_thread == false) {
		temp = insucc(child);
		temp->left_child = child;

	}
}

새 노드 먼저 설정하는 것이 편하다. 

이 코드는 오른쪽 자식으로 추가하는 것이지만, 왼쪽 자식으로 추가하는 버전도 써 보자.

 

---

8. 선택 트리(Selection Tree)

외부 정렬(External sorting)에 사용.

 

아주 큰 용량의 파일이 있는데 메모리는 조그마할 때.

파일을 sorting하려면, 메모리에 조금씩 조금씩 덜어서 정렬해야 한다.

그럼 정렬된 파일들 = k개의 sorting된 run들이 생기는데,

이 run들을 병합할 때, 선택 트리가 사용된다.

 

tree of winners

작은것 토너먼트이다.

크기비교하여 작은 것이 부모노드로 올라가고, 계속해서 작은 것이 위로 올라가는 구조이다.

 

tree of losers

패자가 부모노드에 기록되며, 상위 토너먼트에서는 (기록해두진 않았지만) 승자끼리 비교하고, 기록은 패자로 기록함.

비교횟수가 적어지는 장점이 있다고 한다.