[이산수학] 트리

트리의 개념을 익히고 트리의 응용 방법을 고찰한다

트리의 기본 개념

트리

그래프의 모양이 나무를 거꾸로 세워 놓은 것처럼 생겼다하여 불리는 이름

그래프의 특별한 형태로 컴퓨터를 통한 자료 처리와 응용에 있어 매우 중요한 역할

이진 트리는 산술적 표현이나 자료 구조를 매우 간단히 표현 가능 → 컴퓨터 기술의 발전에 따라 수 많은 분야에 적용 가능

트리는 하나 이상의 노드로 구성된 유한 집합으로 특별히 지정된 루트가 있으며 나머지 노드 들은 다시 각각 트리이며 연결되지 않는 서브 트리로 나뉜다

트리의 응용 분야

최적화 문제 해결, 언어들 간의 번역, 알고리즘, 자료 탐색/정렬, 등

트리의 구조

루트 : 주어진 그래프의 시작 노드로서 통상 트리의 가장 높은 곳에 위치

차수 : 어떤 노드의 차수는 그 노드의 서브 트리의 개수를 나타냄

잎 노드 : 차수가 0인 노드

자식 노드 : 어떤 노드의 서브 트리의 루트 노드

부모 노드 : 자식 노드의 반대 개념으로 해당 노드의 상위 노드

형제 노드 : 동일한 부모 노드를 가지는 노드

중간 노드 : 루트도 아니고 잎 노드도 아닌 노드

조상 : 루트로부터 그 노드에 이르는 경로에 나타난 모든 노드

자손 : 그 노드로부터 잎 노드에 이르는 경로상에 나타난 모든 노드들

레벨 : 루트의 레벨을 0으로 놓고 자손 노드로 내려가면서 하나씩 증가

트리의 높이 : 트리에서 노드가 가질 수 있는 최대 레벨, 트리의 깊이라고도 함

숲 : 서로 연결되지 않는 트리 들의 집합으로 루트를 제거하여 만들 수 있음

n-트리 : 모든 중간 노드들이 최대 n 개의 자식 노드를 가질 때

이진 트리 : 해당 n이 2일때 이진 트리라고 부른다

방향 트리

방향이 있고 순서화된 트리는 다음의 성질들을 만족하는 방향 그래프

1. 선행자가 없는 루트라고 불리는 노드가 하나 있으며 해당 루트 노드는 모든 노드로 갈 수 있는 경로가 있음
2. 루트를 제외한 모든 노드들은 오직 하나씩만의 선행자를 가짐
3. 각 노드의 후속자들은 통상 왼쪽으로부터 순서화

이진 트리

이진 트리는 노드들의 유한 집합으로 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브트리로 이루어진다

#1 사향 이진 트리

왼쪽이나 오른쪽 중 한 쪽으로 편향된 트리의 구조를 가짐

#2 완전 이진 트리

높이가 k일 때 레벨 1부터 k-1까지는 모두 차 있고 레벨 k에서는 왼쪽 노드부터 차례로 차 있는 이진 트리

#3 포화 이진 트리

잎 노드가 아닌 것들은 모두 2개씩 자식 노드를 가지며 트리의 높이가 일정한 경우

이진 트리의 표현

#1 이진 트리를 표현하는 방법

배열에 의한 방법과 연결 리스트에 의한 방법으로 나눌 수 있음

배열에 의한 방법은 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 지울 경우 비효율적

일반적으로 가장 많이 쓰이고 있는 연결리스트에 의한 방법

→ 데이터를 저장하는 중간 부분, 왼쪽 노드와 오른쪽 노드를 가리키는 포인터로 구성하여 나타낼 수 있음

typedef struct treenode{
	struct treenode *leftchild;
	char data;
	struct treenode *rightchild;
} TREE;

이진 트리의 탐방 / 순회

트리는 자료의 저장과 검색에 있어 매우 중요한 구조

가장 빈번한 연산으로는 노드를 한 번씩만 방문하는 탐방(traversal)

탐방의 결과 각 노드에 들어있는 데이터를 차례로 나열

이진 트리를 탐방하는 것은 여러 가지 응용에 널리 쓰임

각 노드와 서브 트리를 같은 방법으로 탐방 가능

중순위, 전순위, 후순위 탐방이 존재

#1 중순위 탐방

중순위 탐방은 루트에서 시작하여 트리의 각 노드에 대하여 다음과 같은 재귀적 방법으로 정의

void inorder(TREE *currentnode)
{
	if(currentnode != NULL)
	{
		inorder(currentnode->leftchild);
		printf("%c", currentnode->data);
		inorder(currentnode->rightchild);
	}
}

#2 전순위 탐방

전순위 탐방은 루트에서 시작하여 트리의 각 노드에 대하여 다음과 같은 재귀적 방법으로 정의

void preorder(TREE *currentnode)
{
	if(currentnode != NULL)
	{
		printf("%c", currentnode->data);
		preorder(currentnode->leftchild);
		preorder(currentnode->rightchild);
	}
}

#3 후순위 탐방

후순위 탐방은 루트에서 시작하여 트리의 각 노드에 대하여 다음과 같은 재귀적 방법으로 정의

void postorder(TREE *currentnode)
{
	if(currentnode != NULL)
	{
		postorder(currentnode->leftchild);
		postorder(currentnode->rightchild);
		printf("%c", currentnode->data);
	}
}

생성 트리와 최소 비용 생성 트리

생성 트리 : 어떤 그래프 G에서 모든 노드를 포함하는 트리를 생성 트리라고 함

생성 트리의 비용은 트리 연결선의 값을 모두 합한 값

따라서 최소 비용 생성 트리는 최소한의 비용을 가지는 생성 트리를 말한다

최소 비용 생성 트리의 대표적인 2가지 방법은 프림 알고리즘과 크루스칼 알고리즘

#1 프림 알고리즘

void Prim(graph G : set_of_edges T)
{
	set_if vertices U;
	vertex u, v;
	T = NULL;
	U = {1};
	while(U!=V)
	{
		let (u, v) be a lowest cost edge such that u is in U and v is in V-U
		T = T U {(u, v)};
		U = U U {v};
	}
}

#2 크루스칼 알고리즘

T = NULL;
while(T contains less than n-1 edges and E not empty)
{
	choose an edge (v, w) from E of lowest cost;
	delete (v, w) from E;
	if((v, w) does not create a cycle in T)
		add (v, w) to T;
	else discard (v, w);
}
if(T contains fewer than n-1 edges) pritnf("no spanning tree\\n");

트리의 활용

#1 문법의 파싱

문법의 파싱을 통하여 자연어 처리와 컴파일러에 활용

#2 허프만 코드

알파벳 열로서 이루어진 메시지가 있고 각 메시지의 영문자가 각각 독립적이고 위치에 관계없이 어떤 정해진 확률로 나타남

→ 해당 코드 특성을 이용하여 최적화 코드 방법을 만든 것을 허프만 알고리즘이라고 함

#3 결정 트리

트리를 이용할 때 매우 유용하게 쓰이는 것은 결정 트리

#4 게임

체스나 장기, 바둑과 같이 경우의 수를 통한 게임을 트리로 구현 가능

이처럼 트리에 대해 공부하여 여러 가지 트리의 활용 방법을 알아보았음