Chapter 8. 트 리.

Presentation on theme: "Chapter 8. 트 리."— Presentation transcript:

1 Chapter 8. 트 리

2 개요 트리의 개념, 용어, 방향 트리, 분자식과 같은 응용 분야들에 관해 알아봄
이진 트리의 종류, 배열 및 연결 리스트에 의한 이진 트리의 표현법과 더불어 중순위 탐방, 전순위 탐방 그리고 후순위 탐방에 대해서도 살펴봄 생성 트리와 최소 비용 생성 트리, 프림의 알고리즘과 크루스칼의 알고리즘을 알아봄 문법의 파싱, 허프만 코드, 결정 트리, 게임 등의 분야에서 트리의 응용을 고찰함

3 CONTENTS 8.1 트리의 기본 개념 8.2 방향 트리 8.3 이진 트리 8.4 이진 트리의 표현 8.5 이진 트리의 탐방 8.6 생성 트리와 최소 비용 생성 트리 8.7 트리의 활용

4 8. 트 리 트리(Tree) 그래프 모양이 나무를 거꾸로 세워놓은 것처럼 생겼다고 해서 불리는 이름인데 수형도(樹型圖)라고 함
그래프의 특별한 형태로서 컴퓨터를 통한 자료 처리와 응용에 있어서 매우 중요한 역할을 담당함 이진 트리의 경우에는 산술적 표현이나 자료 구조 등을 매우 간단하게 표현할 수 있는 장점이 있음 컴퓨터 기술의 발전과 더불어 수많은 응용 분야에 적용 가능함 Discrete Mathematics Chapter 8. 트 리

5 8.1 트리의 기본 개념 Discrete Mathematics Chapter 8. 트 리

6 8.1 트리의 기본 개념 Discrete Mathematics Chapter 8. 트 리

7 8.1 트리의 기본 개념 화합물인 포화 탄화수소는 Ck H2k+2인 형태의 분자식을 가짐
탄소의 원자가는 4이고, 수소의 원자가는 1임을 고려하여 화합물 내 에 결합되어 있는 원소들을 선으로 연결하여 구조를 표현함 CH4를 분자식으로 가지는 메탄의 구조는 트리의 형태로 나타냄 Discrete Mathematics Chapter 8. 트 리

8 8.1 트리의 기본 개념 부탄과 이소부탄은 화학식(C4H10)으로는 같으나, 서로 다른 화학적 구조를 가지는 이성체임
트리 개념의 도입은 수많은 이성체들의 분자 구조를 규명하는 데 결정적인 역할이라 함 컴퓨터 기술의 발전과 확산에 힘입어 다양한 분야들에 적용됨 Discrete Mathematics Chapter 8. 트 리

9 8.1 트리의 기본 개념 Discrete Mathematics Chapter 8. 트 리

10 8.1 트리의 기본 개념 Discrete Mathematics Chapter 8. 트 리

11 8.1 트리의 기본 개념 루트(root) : 주어진 그래프의 시작 노드로서 통상 트리의 가장 높은 곳에 위치하며 노드 A가 루트 노드임 차수(degree) : 어떤 노드의 차수는 그 노드의 서브 트리의 개수를 나타내고, 노드 A의 차수는 3, B의 차수는 2, F의 차수는 0임 잎 노드(leaf node) : 차수가 0인 노드로서 K, L, F, G, M, I, J가 잎 노드에 해당됨 자식 노드(children node) : 어떤 노드의 서브 트리의 루트 노드들을 말하는데 A의 자식 노드는 B, C, D임 Discrete Mathematics Chapter 8. 트 리

12 8.1 트리의 기본 개념 부모 노드(parent node) : 자식 노드의 반대 개념으로서, B의 부모 노드는 A이고 G의 부모 노드는 C임 형제 노드(sibling node) : 동일한 부모를 가지는 노드인데, B, C, D는 모두 형제 노드들이고 K, L도 형제 노드들 임 중간 노드(internal node) : 루트도 아니고 잎 노드도 아닌 노드를 말함 조상(ancestor) : 루트로부터 그 노드에 이르는 경로에 나타난 모든 노드들을 말하는데, F의 조상은 B와 A이며, M의 조상은 H, D, A임 Discrete Mathematics Chapter 8. 트 리

13 8.1 트리의 기본 개념 자손(descendant) : 그 노드로 부터 잎 노드에 이르는 경로상에 나타난 모든 노드 들을 말하는데 B의 자손은 E, F, K, L이고 H의 자손은 M임 레벨(level) : 루트의 레벨을 0으로 놓고 자손 노드로 내려가면서 하나씩 증가한다. 즉, 어떤 노드의 레벨이 p라면 그것의 자식 노드의 레벨은 p+1이 됨 트리의 높이(height) : 트리에서 노드가 가질 수 있는 최대 레벨로서 트리의 깊이(depth)라고도 한다. 이 트리의 높이는 3이 됨 숲(forest) : 서로 연결되지 않는 트리 들의 집합으로서 트리에서 루트를 제거하면 숲을 얻을 수 있음 Discrete Mathematics Chapter 8. 트 리

14 8.1 트리의 기본 개념 Discrete Mathematics Chapter 8. 트 리

15 8.1 트리의 기본 개념 Discrete Mathematics Chapter 8. 트 리

16 8.1 트리의 기본 개념 Discrete Mathematics Chapter 8. 트 리

17 8.2 방향 트리 방향이 있고 순서화된 트리는 다음의 성질들을 만족하는 방향 그래프
선행자가 없는 루트라고 불리는 노드가 하나 있으나, 이 루트에서는 모든 노드로 갈 수 있는 경로가 있음 루트를 제외한 모든 노드들은 오직 하나씩만의 선행자를 가짐 각 노드의 후속자들은 통상 왼쪽으로부터 순서화됨 어떤 방향 트리를 그릴 때 그 트리의 루트를 가장 위에 있음 아크(연결선)들은 밑을 향하여 그려짐 Discrete Mathematics Chapter 8. 트 리

18 8.2 방향 트리 Discrete Mathematics Chapter 8. 트 리

19 8.3 이진 트리 사향 이진 트리(skewed binary tree) 포화 이진 트리(full binary tree)
왼쪽 또는 오른쪽으로 편향된 트리의 구조를 가짐 완전 이진 트리(complete binary tree) 높이가 k일 때 레벨 1부터 k-1까지는 모두 차 있고 레벨 k에서는 왼쪽 노드부터 차례로 차 있는 이진 트리임 포화 이진 트리(full binary tree) 잎 노드가 아닌 것들은 모두 2개씩의 자식 노드를 가지며 트리의 높이가 일정한 경우를 말함 Discrete Mathematics Chapter 8. 트 리

20 8.3 이진 트리 Discrete Mathematics Chapter 8. 트 리

21 8.3 이진 트리 Discrete Mathematics Chapter 8. 트 리

22 8.3 이진 트리 Discrete Mathematics Chapter 8. 트 리

23 8.4 이진 트리의 표현 이진 트리를 표현하는 방법 배열(array)에 의한 방법과 연결 리스트(linked list)에 의한 방법으로 나눌 수 있음 배열에 의한 방법은 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 지울 경우 비효율적임 일반적으로 가장 많이 쓰이고 있는 연결 리스트에 의한 방법임 데이터(data)를 저장하는 중간 부분, 왼쪽 자식(left child), 오른쪽 자식(right child)을 각각 가리키는 포인터(pointer) 부분으로 구성되며, C언어로 나타낼 수 있음 Discrete Mathematics Chapter 8. 트 리

24 8.4 이진 트리의 표현 Discrete Mathematics Chapter 8. 트 리

25 8.4 이진 트리의 표현 이진 트리를 연결 리스트에 의한 표현 Discrete Mathematics Chapter 8. 트 리

26 8.5 이진 트리의 탐방 트리는 자료의 저장과 검색에 있어서 매우 중요한 구조를 제공함
트리에서의 연산에는 여러 가지가 있으나 가장 빈번하게 하는 것은 각 노드를 꼭 한 번씩만 방문하는 탐방(traversal)일 것임 탐방의 결과 각 노드에 들어 있는 데이터를 차례로 나열하게 됨 이진 트리를 탐방하는 것은 여러 가지 응용에 널리 쓰임 각 노드와 그것의 서브 트리를 같은 방법으로 탐방할 수 있음 Discrete Mathematics Chapter 8. 트 리

27 8.5 이진 트리의 탐방 L, D, R을 각각 왼쪽(Left)으로의 이동, 데이터(Data) 프린트, 오른쪽(Right)으로의 이동을 나타낸다고 할 때 총 6가지의 나열 방법이 있음 왼쪽을 오른쪽보다 항상 먼저 방문한다고 가정하면 LDR, DLR, LRD의 3가지 경우가 있음 이것을 각각 중순위(inorder), 전순위(preorder), 후순위(postorder)탐방이라고 함 이 순서들은 수식 표현에서 중순위 표기(infix), 전순위 표기(prefix), 후순위 표기(postfix)와 각각 대응됨 Discrete Mathematics Chapter 8. 트 리

28 8.5 이진 트리의 탐방 Discrete Mathematics Chapter 8. 트 리

29 8.5 이진 트리의 탐방 재귀적 알고리즘(Recursive algorithm)
보통 상당히 복잡하므로 중순위 탐방과 같은 전개 과정을 거치는 것이 매우 편리함 루트로부터 시작하여 inorder(currentnode→leftchild), printf(currentnode→data), inorder(currentnode→rightchild)의 트리 형태로 계속 전개시켜 나가서 프린트된 결과를 왼쪽부터 차례로 적어나감 이 방법을 탐방에 쓰이는 이진 트리에 적용한 결과 D, B, E, A, C의 순서로 프린트함 Discrete Mathematics Chapter 8. 트 리

30 8.5 이진 트리의 탐방 Discrete Mathematics Chapter 8. 트 리

31 8.5 이진 트리의 탐방 탐방에 쓰이는 이진 트리를 적용한 프로그램의 작동 결과는 A,B,D,E,C
Discrete Mathematics Chapter 8. 트 리

32 8.5 이진 트리의 탐방 Discrete Mathematics Chapter 8. 트 리

33 8.5 이진 트리의 탐방 탐방에 쓰이는 이진 트리를 적용한 프로그램의 작동 결과는 D,E,B,C,A
Discrete Mathematics Chapter 8. 트 리

34 8.5 이진 트리의 탐방 Discrete Mathematics Chapter 8. 트 리

35 8.5 이진 트리의 탐방 Discrete Mathematics Chapter 8. 트 리

36 8.5 이진 트리의 탐방 Discrete Mathematics Chapter 8. 트 리

37 8.5 이진 트리의 탐방 Discrete Mathematics Chapter 8. 트 리

38 8.5 이진 트리의 탐방 Discrete Mathematics Chapter 8. 트 리

39 8.6 생성 트리와 최소 비용 생성 트리 주어진 그래프 G와 그것의 3가지 생성 트리들 Discrete Mathematics
Chapter 8. 트 리

40 8.6 생성 트리와 최소 비용 생성 트리 Discrete Mathematics Chapter 8. 트 리

41 8.6 생성 트리와 최소 비용 생성 트리 최소 비용 생성 트리의 대표적인 예는 통신 네트워크의 연결임
각 도시들을 연결하는 데 있어서 최소 비용으로 연결하는 방법을 찾는 것임 최소 비용 생성 트리의 대표적인 2가지 방법은 프림(Prim)의 알고리즘과 크루스칼(Kruskal)의 알고리즘임 Discrete Mathematics Chapter 8. 트 리

42 8.6 생성 트리와 최소 비용 생성 트리 = Discrete Mathematics Chapter 8. 트 리

43 8.6 생성 트리와 최소 비용 생성 트리 Discrete Mathematics Chapter 8. 트 리

44 8.6 생성 트리와 최소 비용 생성 트리 Discrete Mathematics Chapter 8. 트 리

45 8.6 생성 트리와 최소 비용 생성 트리 Discrete Mathematics Chapter 8. 트 리

46 8.6 생성 트리와 최소 비용 생성 트리 Discrete Mathematics Chapter 8. 트 리

47 8.6 생성 트리와 최소 비용 생성 트리 Discrete Mathematics Chapter 8. 트 리

48 8.6 생성 트리와 최소 비용 생성 트리 Discrete Mathematics Chapter 8. 트 리

49 8.7 트리의 활용 문법의 파싱(parsing) 트리는 문법의 파싱을 통하여 자연어 처리와 컴파일러(compiler) 등에 활용됨 문장 트리에서 문장은 주어, 동사, 목적어로 이루어짐 주어는 관사와 명사구로 나누어지고 목적어는 관사와 명사구로 나누어짐 명사구는 형용사와 명사로 다시 나누어지는 파싱 과정을 반복함 Discrete Mathematics Chapter 8. 트 리

50 8.7 트리의 활용 Discrete Mathematics Chapter 8. 트 리

51 8.7 트리의 활용 (2) 허프만 코드(Huffman code)
알파벳의 열(sequence)로서 이루어진 메시지가 있고, 각 메시지의 영문자가 각각 독립적이고 위치에 관계없이 어떤 정해진 확률로 나타남 예를 들자면, 5개의 영문자 a, b, c, d, e가 나타날 확률이 각각 0.12, 0.4, 0.15, 0.08, 0.25라고 할 때, 이 영문자를 각각 0과 1의 열로서 코드화하고자 하면, 어느 영문자의 코드도 다른 어떤 영문자의 코드의 접두어로 표현되어서는 안됨 a가 01이고 b가 010일 때 a는 b의 접두어가 되므로 적합하지 않음 Discrete Mathematics Chapter 8. 트 리

52 8.7 트리의 활용 허프만 코드 특성을 이용하여 최소 개의 코드로써 정확하게 송신할 수 있으며 수신된 코드를 정확하게 코드화가 가능함 접두어 성질을 만족하는 최적의 코드화 방법을 허프만 알고리즘 이라고 함 Discrete Mathematics Chapter 8. 트 리

53 8.7 트리의 활용 Discrete Mathematics Chapter 8. 트 리

54 8.7 트리의 활용 Discrete Mathematics Chapter 8. 트 리

55 8.7 트리의 활용 Discrete Mathematics Chapter 8. 트 리

56 8.7 트리의 활용 (3) 결정 트리(decision tree) 8개의 동전 문제(eight-coins problem)
트리를 이용할 때 매우 유용하게 쓰이는 것은 결정 트리임 가능성 있는 경우의 수가 너무나 많기 때문에 모든 면에서 입증하기가 매우 어려운 문제를 만날 수가 있음 결정 트리를 활용하면 주어진 문제를 일목요연하게 입증할 수 있음 8개의 동전 문제(eight-coins problem) 결정 트리의 예로 잘 알려져 있음 크기와 색깔이 똑같은 8개의 동전 a, b, c, d, e, f, g, h 중에서 한 개는 불량품이어서 다른 동전들과는 다른 무게를 가짐 무게가 같거나 크고 작은 것만을 판단할 수 있는 하나의 천칭 저울을 사용하여 단 세 번만의 계량으로 어느 동전이 불량품이고, 다른 동전보다 무겁거나 가벼운지를 동시에 판단하고자 함 Discrete Mathematics Chapter 8. 트 리

57 8.7 트리의 활용 a+b+c ＜ d+e+f인 경우 불량품이 6개 가운데 있으며 이때의 g와 h는 정상품이라는 것을 알 수 있음 다음 단계에서 d와 b를 양 천칭 저울에서 바꾸어 계량한 결과 a+d ＜ b+e로 부등호에 변화가 없다면 다음의 2가지 가능성을 말해줌 a가 불량품이거나 e가 불량품인 경우임 이런 경우는 정상품과 비교하여 H나 L을 판단할 수 있음 만약 a+d = b+e인 경우에는 c나 f가 불량품임 또한 b나 d가 불량품인 경우에는 다른 정상품과 비교하여 b 또는 d가 H나 L이 되게 결정됨 Discrete Mathematics Chapter 8. 트 리

58 8.7 트리의 활용 Discrete Mathematics Chapter 8. 트 리

59 8.7 트리의 활용 최종 판단을 위한 프로시저인 comp의 프로그램임
프로시저 eight-coins는 앞의 결정 트리의 판단과 같은 기능을 수행함 Discrete Mathematics Chapter 8. 트 리

60 8.7 트리의 활용 Discrete Mathematics Chapter 8. 트 리

61 8.7 트리의 활용 (4) 게임(game) 트리는 체스, 틱텍토(tic-tac-toe), 장기, 바둑 등 게임에 있어서의 진행과 전략을 구사할 수 있는 게임 트리로도 활용됨 가로, 세로, 대각선으로 연속된 세 개를 놓으면 이기는 게임인 tic-tac-toe 게임의 일부를 나타냄 Discrete Mathematics Chapter 8. 트 리

62 8.7 트리의 활용 Discrete Mathematics Chapter 8. 트 리

63 8.7 트리의 활용 게임 트리를 이용하는 또 다른 응용으로는 8-puzzle 게임이 있음
이 게임은 3×3 크기의 박스 안에서 인접한 숫자를 빈 곳으로 계속적으로 움직여서 목표 상태(goal)로 만드는 서양식 게임임 Discrete Mathematics Chapter 8. 트 리

64 8.7 트리의 활용 Discrete Mathematics Chapter 8. 트 리

65 요약 Discrete Mathematics Chapter 8. 트 리

66 요약 Discrete Mathematics Chapter 8. 트 리

67 요약 이다. Discrete Mathematics Chapter 8. 트 리

68 응용 트리의 활용 문법의 파싱 허프만 코드 결정 트리 게임 등 Discrete Mathematics Chapter 8. 트 리

69 응용 트리의 응용 통신 네트워크 최적화 문제의 해결 자료의 탐색 정렬 데이터베이스 구성 전기회로망 설계와 응용 분자구조식 설계
유전학 언어들 간의 번역 언어학 사회과학 등 Discrete Mathematics Chapter 8. 트 리