[자료구조] 트리

트리의 구성

• 노드: 트리의 항목/트리에 저장되는 데이터의 묶음
• 부모노드-자식노드: 상하 계층구조가 있고 직접적으로 연결된 노드들로서 상위계층의 부모 노드와 하위계층의 자식 노드를 의미함
• 루트 노드: 트리의 최상위 노드(부모가 없는 노드)
• 서브트리: 부모 노드를 삭제하면 생기는 트리들
• 잎 노드: 트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드
• 진입/진출 차수
  • 루트 노드: 진입 차수 = 0
  • 루트를 제외한 모든 노드의 진입 차수: 1
  • 잎 노드: 진출 차수 = 0
• 내부 노드와 형제
  • 내부 노드: 루트도 아니고 잎도 아닌 노드
  • 형제: 같은 부모를 갖는 노드들
• 트리의 레벨
  • 노드의 레벨: 루트로부터 그 노드까지 이어진 선(경로)의 길이
  • 트리의 깊이: 트리의 레벨에서 가장 큰 값에 1을 더한 것

추상 자료형

• 트리 객체의 정의: 루트 노드를 갖는 유한 리스트
• 연산
  • Tree Create() ::= 트리를 생성하고 루트 노드를 가리키는 포인터를 반환한다.
  • Destroy(Tree) ::= 더 이상 사용하지 않는 트리의 기억 장소를 시스템에 반환한다.
  • Tree Copy_Tree(Tree) ::= 트리를 복사하고 새로 생성한 트리의 루트 노드를 가리키는 포인터를 반환한다.
  • Insert(n) ::= 트리에 노드 n을 삽입한다.
  • Delete() ::= 트리에서 노드를 삭제한다. 보통 재구성 단계를 포함한다.
  • Search() ::= 트리에서 특정 키 값을 갖는 노드를 찾는다. 찾으면 true 아니면 false를 반환한다.
  • Traverse() ::= 트리를 순회하고 방문 순서대로 값을 반환한다.
  • Root() ::= 루트 노드 값을 반환한다.
  • Parent(n) ::= 노드 n의 부모(값 혹은 포인터)를 반환. n이 루트이면 오류를 반환한다.
  • Children() ::= 노드 n의 자식(값 혹은 포인터)를 반환. n이 앞이면 오류를 반환한다.
  • IsRoot(n) ::= 노드 n이 루트이면 true 아니면 false를 반환한다.
  • IsInternal(n) ::= 노드 n이 내부 노드이면 true 아니면 false를 반환한다.
  • IsLeaf(n) ::= 노드 n이 잎이면 true 아니면 false를 반환한다.
  • IsEmpty() ::= 트리가 비었으면 true 아니면 false를 반환한다.
  • Replace(n, m) ::= 노드 n을 노드 m으로 바꾼다.

이진 트리

• 모든 노드의 차수가 2 이하인 트리
• 수학적으로 이진 트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 효율적임
• 모든 노드가 2개 이하의 자식 노드를 가지므로 일반성을 잃지 않고 오른쪽, 왼쪽이라는 방향 개념을 부여할 수도 있음
• 오른쪽 노드와 왼쪽 노드의 개념적 접근(의미적 관계)도 있음
• 포화 이진 트리: 이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리
• 완전 이진 트리: 높이가 k인 이진 트리가 0 레벨부터 k-2 레벨까지 다 채우고, 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진 트리
• 배열을 이용한 이진 트리의 구현: 트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적임

// 포인터를 이용한 이진 트리의 노드 생성
typedef struct node {
	struct node *left;
	char data
	struct node *right;
} node;

이진 트리 연산

• 이진 트리의 순회: 이진 트리의 각 노드를 (빠짐없이 그리고 중복없이) 한 번씩 방문하는 것
• 전위 순회(PLR): 루트노드 - 왼쪽 자식노드(왼쪽 서브트리) - 오른쪽 자식노드(오른쪽 서브트리)

void preorder(node* root) {
	if(root != NULL) {
		printf("%c", root -> data);
		preorder(root -> left);
		preorder(root -> right);
	}
}

• 후위 순회(LPR): 왼쪽 자식노드 - 오른쪽 자식노드 - 루트노드

void postorder(node* root) {
	if(root != NULL) {
		postorder(root -> left);
		postorder(root -> right);
		printf("%c", root -> data);
	}
}

• 중위 순회(LRP): 왼쪽 자식노드 - 루트노드 - 오른쪽 자식노드

void postorder(node* root) {
	if(root != NULL) {
		postorder(root -> left);
		postorder(root -> right);
		printf("%c", root -> data);
	}
}

• 이진 트리의 생성/삽입/삭제 
  • 일반적인 이진 트리를 생성하는 것은 연결 리스트 연산을 사용함
  • 첫 노드를 생성하면 루트 노드가 되고, 새로운 노드를 추가하려면 연결 리스트의 삽입 연산을 사용함
  • 노드를 삭제할 때, 삭제하려는 노드가 잎 노드인 경우는 해당 노드를 가리키는 포인터를 NULL로 지정하면 됨
  • 잎 노드가 아닌 경우에는 삭제하려는 노드의 자식노드에 대한 처리를 추가로 해주어야 함

// 노드 삽입
node *insert(node *here, node *it) {
	if(here == NULL) {
		here = it;
		return NULL;
	} else {
		node* victim;
		victim = here;
		*here = *it;
		return victim;
	}
}

// 개수를 세는 연산
int get_nodeNum(node *root) {
	int num = 0;
	if(root == NULL) return 0;
	else {
		num = 1;
		num += (get_nodeNum(root -> left) + get_nodeNum(root -> right));
		return num;
	}
}

// 노드 삭제
node *delete(node *root, node *it, char direction) {
	node *parent = searchParent(root, it);
	if(parent == NULL) {
		printf("삭제 불가!₩n");
		return NULL;
	} else {
		if(direction == 'l') {
			parent -> left = NULL;
			free(parent -> left);
			return it;
		} else if(derection == 'r') {
			parent -> right = NULL;
			free(parent -> right);
			return it;
		}
		else return NULL;
	}
}

// 잎 노드의 개수 세는 연산
int get_leafNum(node *root) {
	int result = 0;
	if(root == NULL) return 0;
	else if(root -> left == NULL && root -> right == NULL) return 1;
	result += (get_leafNum(root -> left) + get_leafNum(root -> right));
	return result;
}

일반 트리를 이진 트리로 변환

일반 트리에 대하여 각 노드의 형제들을 연결하고, 각 노드에 대하여 가장 왼쪽 링크만 남기고 모두 제거한 후, 루트 노드는 반드시 왼쪽 자식노드 하나만 갖도록 함

스레드 트리

• 이진 트리의 노드 순회: 전위 순회, 중위 순회, 후위 순회
• 이진 트리의 노드를 순환 함수를 사용하지 않고 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야 하는 번거로움이 발생함
• 스레드 트리: 스레드(순회 방법에 따른 방문 순서를 유지하는 포인터)를 추가하여 트리 순회를 편리하게 한 것

스레드 트리 구현

포인터 필드의 추가

• 스레드를 저장하는 포인터를 추가하는 것
• 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의함
• 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴
• 왼쪽 스레드: 그 노드의 선행 노드를 가리킴

// 포인터 필드의 추가
typedef struct tfNode {
	struct tfnode *left;
	struct tfnode *lthread;
	char data;
	struct tfnode *right;
	struct tfnode *rthread;
} tfnode;

// 추가된 포인터 필드를 이용한 중위 순회 연산
void inorder(tfNode *startNode) {
	tfNode *ptr;
	ptr = startNode;
	while(ptr != NULL) {
		printf("%c", ptr -> data);
		ptr = ptr -> rthread;
	}
}

• 스택을 운영하지 않고도 트리에 속한 모든 노드를 순회할 수 있음
• 하지만 스레드를 위해 추가 기억장소를 사용한다는 부담이 생김

빈 포인터 활용

• 노드의 빈 포인터 필드를 활용: 기존 이진 트리의 노드 구조를 그대로 사용하면서, 노드에 있는 사용하지 않는 포인터(빈 포인터)를 활용하는 방법
• 추가 기억장소를 사용하지 않아도 되는 장점이 있음
• 어떤 노드 X에 대해 오른쪽 포인터가 NULL이면 이 포인터를 노드 X의 후행 노드를 가리키도록 함
• 왼쪽 포인터가 NULL이면 노드 X의 선행 노드를 가리키도록 함
• 잎 노드의 빈 포인터 필드의 활용: 이진 트리의 포인터 갯수(노드의 개수를 n개라 가정함) → 왼쪽 서브트리를 가리키는 포인터 n개 + 왼쪽 서브트리를 가리키는 포인터 n개 = 2n개의 포인터
• 노드의 빈 포인터 필드의 활용
  • 루트 노드를 제외한 각 노드 개수는 모든 진입 차수가 1이 되므로
  • 루트 노드를 제외한 전체 노드, 즉 누군가로부터 가리켜져야 할 노드의 개수: n-1
  • (각 노드의) NULL이 아닌 포인터 개수: n-1
  • 2n - (n-1) = n+1개의 NULL 포인터가 노드에 존재함
• 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브트리에 대한 포인터인지를 구분하기 위해 스레드 사용여부 태그 필드가 필요함(삽입/삭제 연산에서 반드시 필요함)
• 전위 순회: 각 노드의 오른쪽 포인터 필드를 스레드로 사용하는 제한을 가정함
  • 어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면(실선) 그대로 두고
  • NULL이면 전위 순회로 순회할 때 다음으로 순회되는 노드(후행 노드)를 가리키도록(점선) 지정함

스레드 트리 순회, 삽입, 삭제

중위 순회 스레드 트리

typedef struct thNode {
	struct tfNode *left;
	char data;
	struct tfNode *right;
	int threadFlag;
} tfNode;

void inorderStart(tfNode* start) {
	if(ptr == NULL) return NULL;
	while(ptr -> left != NULL) ptr = ptr -> left;
	return ptr;
}

void inorder(tfNode* root) {
	tfNode* ptr = inorderStart(root);
	while(ptr != NULL) {
		printf("%c", ptr -> data);
		if(ptr -> threadFlag) // 오른쪽 포인터를 스레드로 사용함
			ptr = ptr -> right;
		else ptr = inorderStart(ptr -> right);
	}
}

스레드 트리 삽입

typedef struct thNode {
	struct tfNode *left;
	struct tfnode *lthread;
	char data;
	struct tfNode *right;
	struct tfnode *rthread;
} tfNode;

void insert(tfNode *x, tfNode *y) {
	y -> left = NULL;
	y -> right = x -> right;
	y -> lthread = x;
	y -> rthread = x -> rthread;
	x -> right = y;
	x -> rthread = y;
}

스레드 트리 삭제

삭제된 노드의 자식 노드를 처리하는 방법이 필요함

• 노드의 자식 노드를 모두 삭제하는 방법
• 삭제하려는 노드 x의 왼쪽 서브 트리나 오른쪽 서브 트리의 루트를 x가 있던 위치로 옮기는 방법
• 잎 노드가 아닌 노드를 삭제하지 못하게 하는 것