Chapter 8. 트리. 개요  트리의 개념, 용어, 방향 트리, 분자식과 같은 응용 분야  이진 트리의 종류, 배열 및 연결 리스트에 의한 이진 트리의 표현법, 중순위 탐방, 전순위 탐방 그리고 후순위 탐방  생성 트리와 최소 비용 생성 트리, 프림의 알고리즘과.

Chapter 8. 트리

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

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

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

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

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

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

8.1 트리의 기본 개념 Chapter 8. 트 리 11 Discrete Mathematics 루트 (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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8.7 트리의 활용 Chapter 8. 트 리 51 Discrete Mathematics (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 의 접두어가 되므로 적합하지 않음 )

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

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

8.7 트리의 활용 Chapter 8. 트 리 57 Discrete Mathematics 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 을 결정

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

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

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

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

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

Similar presentations

Similar presentations

About project

지원

로그인

Auth with social network:

Similar presentations

Similar presentations

About project

지원