<스레드 이진트리> 기본개념과 알고리즘

# 스레드 이진트리 // 이 글은 드래그 및 복붙이 되지 않습니다. 소스파일은 하단에 첨부되어 있습니다.

---

 이진트리 순회는 순환호출을 사용한다. 하지만, 순환호출은 반복문에 의해 훨씬 비효율적이다. 그리고 이 비효율성은 트리의 높이가 커질수록, 노드의 갯수가 많아질 수록 더 커진다. 따라서 이진트리의 순회를 순환 호출 없이 좀 더 효율적을 할 수 없을까? 라는 고민을 하게 된다.

 우선 이진트리의 노드에는 많은 NULL 링크들이 존재한다. 구체적으로 이 사실을 살펴보도록 하자.

/* 일반식으로서의 의미를 지니기 위해 n이라고 쓰지만, 실제로 논리를 따라 갈 때는 그림과 같이 n = 7 이라 생각하자. */

 

 트리의 노드 개수가 n개 라고 가정해보자. 각 노드당 2개의 링크가 존재하므로 (NULL도 포함) 총 링크의 개수는 2n개다. 이들 링크 중에서, n-1개의 링크들이 루트 노드를 제외한 n-1개의 다른 노드들을 가리키고 있다. n-1개의 링크만이 링크로서의 의미를 갖고 나머지는 NULL이란 뜻이다. 실제로 그림을 보면, 노드 개수는 7개인데 선은 6개가 존재한다. 6개의 선 만이 의미있는 링크를 가지고 나머지 8개 선은 NULL인 것이다.

 따라서 총 링크개수 2n개 중에 의미 있는 n-1개의 링크를 빼주면, n+1개의 링크가 NULL이라는 걸 알 수 있다. 이 포인트에서 n+1개의 남아도는 링크 자원을 효율적으로 활용할 수는 없을까? 라는 고민이 생겼다. 그 결과 스레드 이진 트리(threaded binary tree)라는 개념이 등장했다.

 아이디어를 요약하자면 n+1개의 NULL 링크에 중위 순회 시에 선행 노드인 중위선행자(inorder predecessor)나 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리가 스레드 이진 트리(threaded binary tree)이다. 실을 이용하여 노드들을 순회 순서대로 연결 시킨다고 하여 붙여진 이름이다. 문제를 간단히 하기 위해 일단 중위 후속자만 저장되어 있다고 가정하자.

 중위 후속자라는 단어는 어떤 걸 의미할까? 중위 순회 순서에서 그 다음에 이어질 차례인 노드를 말한다. 아래의 그림을 살펴보자.

/* L: 왼쪽 서브트리 R: 오른쪽 서브트리 V: 루트 노드 */

 중위 순회의 경우 순서가 LVR 순으로 가기 때문에 제일 처음 방문하는 노드는 C가 된다. C에서 다음으로 방문할 노드는 B노드이므로, C의 링크를 B에 연결시킨다. 중위 후속자의 의미를 이젠 알 수 있다.

 그러나 만약 이런 식으로 NULL 링크에 스레드가 저장된다면, 링크에 자식을 가리키는 포인터가 저장되어 있는지 아니면 중위후속자를 가리키는 스레드가 저장되어 있는지 구분이 안된다. 따라서 이를 구별해주는 태그가 필요하다. 이를 반영하여 트리노드의 구조가 다음과 같이 변경 되어야 한다.

/*************************************************
 ** 새롭게 정의된 트리노드 구조체
*************************************************/

typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
	int is_thread; // 만약 오른쪽 링크가 스레드이면 TRUE
} TreeNode;

/*************************************************
 ** End Line
*************************************************/

 만약 is_thread가 TRUE(1) 이면 right는 중위 후속자이고 is_thread가 FALSE(0)이면 오른쪽 자식을 가리키는 포인터가 된다. right만 따지는 이유는 어차피 두 개의 포인터 중 다음 중위후속자를 가리키는 건 하나만 필요하기 때문이다. 게다가 중위 순회의 순서는 언제나 왼쪽 서브트리를 먼저 방문하는 방식으로 이루어지고, 오른쪽 서브트리는 가장 나중에 방문한다. 논리적 구조상으로도 right만 스레드인지 아닌지를 따지는 것이 옳다.

 그렇다면 이제 스레드 이진트리가 구성되었다고 생각해보자. 중위 순회 연산은 어떻게 변경되어야 할까? 먼저 노드 n의 중위 후속자를 반환하는 함수 find_successor를 제작해보자. find_successor는 노드 n의 is_thread가 TRUE로 되어 있으면 바로 오른쪽 자식이 중위 후속자가 되므로 오른쪽 자식을 반환한다. 만약 오른쪽 자식이 NULL이면 더 이상 후속자가 없다는 것이므로 NULL을 반환한다.

 만약 is_thread가 아닌 경우는 서브 트리의 가장 왼쪽 노드로 가야 한다. is_thread가 FALSE인 경우는 내 자신이 루트노드 또는 중위후속자일 때 혹은 오른쪽 서브트리의 마지막 오른쪽 노드다. 중위 순회의 순서는 L V R 이고 현재 내 자신이 루트(중위후속자, V)이므로, 왼쪽 서브트리로 내려가는 것이 맞다. 따라서 왼쪽 자식이 NULL이 될 때까지 왼쪽 링크를 타고 이동한다.

/*************************************************
 ** 트리에서 중위 후속자(노드)를 반환하는 알고리즘
*************************************************/

TreeNode *find_successor(TreeNode *t)
{
	// pright t의 오른쪽 포인터
	TreeNode *pright = t->right;

	// 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
	// 오른쪽 포인터가 NULL이라는 뜻은, 더이상 후속자가 없다는 것이다. 오른쪽 서브트리의 맨 밑단인 것이다.
	if (pright == NULL || t->is_thread == TRUE)
		return pright;
	
	// 만약 pright(t의 오른쪽 포인터)가 NULL이 아니면, 왼쪽 서브트리가 존재한다는 뜻이므로 왼쪽 서브트리로 이동한다.
	// pright가 새로운 V가 되므로 왼쪽 서브트리로 이동하는 것이다. 중위 순회 순서는 L V R이기 때문이다.
	while (pright->left != NULL)
		pright = pright->left;
	
	return pright;
}

/*************************************************
 ** End Line
*************************************************/

 

 이번에는 스레드 이진 트리에서 중위 순회를 하는 함수 thread_inorder를 제작해보도록 하자. 중위 순회는 가장 왼쪽 노드부터 방문하는 순서로 되야하므로, 왼쪽 자식이 NULL이 될 때까지 왼쪽 링크를 타고 계속 이동해야 한다. 가장 왼쪽 끝에 도달한 후 데이터를 출력하면, 중위 후속자를 찾는 함수를 호출해서 후속자가 NULL이 아니면 계속 루프를 반복한다.

/*************************************************
 ** 스레드 중위 순회 알고리즘
*************************************************/

void thread_inorder(TreeNode *t)
{
	TreeNode *r;
	r = t; // 원본 데이터가 손상되지 않게 복사본을 만들어 준 후 작업을 진행한다.
	while (r->left != NULL) r = r->left; // 가장 왼쪽 노드로 이동한다.
	do
	{
		printf("%c", r->data);
		r = find_successor(r); // 중위후속자를 찾는 함수를 호출한다.
	} while (r != NULL); // 중위후속자가 존재하는 한 계속 무한반복
}

/*************************************************
 ** End Line
*************************************************/

 지금까지 다룬 내용들을 바탕으로 스레드 이진트리 순회 프로그램을 아래 작성했다. 스레드 트리는 순회를 빠르게 하는 장점이 있지만 스레드를 설정하기 위해 삽입 및 삭제 등 함수가 좀 더 많은 일을 하게끔 설계해야하는 단점이 있다.

/*************************************************
 ** 스레드 이진트리 중위 순회 프로그램
*************************************************/

#include "stdio.h" // 원래는 꺽새표시가 맞습니다만, 티스토리 html 에디터가 인식을 잘못해서 마지막에 불필요한 코드를 삽입하므로, 따옴표로 표시했습니다.
#include "stdlib.h"
typedef enum { FALSE, TRUE } bool;

typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
	int is_thread;
} TreeNode;

TreeNode *find_successor(TreeNode *t)
{
	// pright t의 오른쪽 포인터
	TreeNode *pright = t->right;

	// 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
	// 오른쪽 포인터가 NULL이라는 뜻은, 더이상 후속자가 없다는 것이다. 오른쪽 서브트리의 맨 밑단인 것이다.
	if (pright == NULL || t->is_thread == TRUE)
		return pright;
	
	// 만약 pright(t의 오른쪽 포인터)가 NULL이 아니면, 왼쪽 서브트리가 존재한다는 뜻이므로 왼쪽 서브트리로 이동한다.
	// pright가 새로운 V가 되므로 왼쪽 서브트리로 이동하는 것이다. 중위 순회 순서는 L V R이기 때문이다.
	while (pright->left != NULL)
		pright = pright->left;
	
	return pright;
}

void thread_inorder(TreeNode *t)
{
	TreeNode *r;
	r = t; // 원본 데이터가 손상되지 않게 복사본을 만들어 준 후 작업을 진행한다.
	while (r->left != NULL) r = r->left; // 가장 왼쪽 노드로 이동한다.
	do
	{
		printf("%c", r->data);
		r = find_successor(r); // 중위후속자를 찾는 함수를 호출한다.
	} while (r != NULL); // 중위후속자가 존재하는 한 계속 무한반복
}

//			G
//		C		F
//	  A	  B   D    E

TreeNode n1 = { 'A', NULL, NULL, 1 };
TreeNode n2 = { 'B', NULL, NULL, 1 };
TreeNode n3 = { 'C', &n1, &n2, 0 };
TreeNode n4 = { 'D', NULL, NULL, 1 };
TreeNode n5 = { 'E', NULL, NULL, 0 };
TreeNode n6 = { 'F', &n4, &n5, 0 };
TreeNode n7 = { 'G', &n3, &n6, 0 };
TreeNode *exp = &n7;

void main()
{
	// 스레드 설정
	n1.right = &n3;
	n2.right = &n7;
	n4.right = &n6;

	// 중위 순회
	thread_inorder(exp);
}

/*************************************************
 ** End Line
*************************************************/

스레드이진트리.c