트리 (Logical) Data Structures Linear list Tree Graph Linear structures

Presentation on theme: "트리 (Logical) Data Structures Linear list Tree Graph Linear structures"— Presentation transcript:

1 트리 (Logical) Data Structures Linear list Tree Graph Linear structures
Non-linear structures

2 트리 Definitions 트리의 높이(Height), 깊이(Depth), 수준(Level)
루트 노드에서 가장 멀리있는 말단노드까지 가는 유일한 경로상에 있는 노드의 개수 Depth 0 Depth 1 (=4) Depth 2 Depth 3 Data Structure

3 이진 검색 트리 이진검색트리(binary search tree): 순서가 정의되어 있는 키 값을 노드로 지니는 이진 트리로서 다음과 같은 특성을 가지고 있다. 각 노드는 키를 가지고 있다. 한 노드의 키는 그 노드의 왼쪽 부분트리에 있는 노드들의 모든 키보다 크다. 한 노드의 키는 그 노드의 오른쪽 부분트리에 있는 노드들의 모든 키보다 작다.

4 이진 검색 트리 이진검색트리의 예 Which is/are binary search tree(s)? 15 20 25 12 10
22 5 30 40 2 60 70 80 55

5 이진 검색 트리 Balance Factor Balanced Binary (Search) Tree
: the height of the left subtree : the height of the right subtree Balanced Binary (Search) Tree A tree with |B|  1 for all nodes HL HR

6 이진 검색 트리 균형 (Balance) 최악의 경우 탐색은 Leaf Node까지 왼쪽 트리는 Balanced Tree.
오른쪽 트리는 균형이 현저히 무너져 있음 최악의 경우 탐색은 Leaf Node까지 왼쪽 트리는 최악의 경우에도 높이가 3. 오른쪽 트리는 최악의 경우 레벨 5 (높이 6)까지 타고 내려와야 함. 오른쪽 트리는 연결 리스트(Linked List)에 가까움. 연결이 한쪽으로 일직선으로(Linear Structure) 진행하는 트리  편향 이진트리 (Skewed Binary Tree) Data Structure

7 최적 이진검색 트리 문제 소개

8 최적 이진검색 트리 문제 소개

9 최적 이진검색 트리 문제 소개

10 최적 이진검색 트리 문제 소개

11 최적 이진검색 트리 문제 - 동적 계획법:설계

12 최적 이진검색 트리 문제 - 동적 계획법:설계 예제 3. 8 (p. 117) c2=1 c3=1 key2 c3=2 c2=2

13 최적 이진검색 트리 문제 - 동적 계획법:설계 treek에서 임의의 키(key1,…, keyn)를 찾는 평균 검색 시간은 다음과 같다.

14 최적 이진검색 트리 문제 - 동적 계획법:설계 A: 최적 트리가 지니고 있는 검색 시간 정보를 지니고 있는 배열
A[i][j]: i번째 키부터 j번째 키까지의 최적 트리가 지니고 있는 검색 시간 정보

15 최적 이진검색 트리 문제 - 동적 계획법:설계 A[1][3] = min{A[1][0] + A[2][3] + P1 + P2 + P , A[1][1] + A[3][3] + P1 + P2 + P , A[1][2] + A[4][3] + P1 + P2 + P3} = min{A[2][3]+P1+P2+P3, P1+P3+P1+P2+P3, A[1][2]+P1+P2+P3} A[2][3] = min{A[2][1] + A[3][3] + P2 + P3, A[2][2] + A[4][3] + P2 + P3} = min{P3+P2+P3, P2+P2+P3}={2P3+P2, 2P2+P3}={0.4, 0.5}=0.4 A[1][2] = min{A[1][0] + A[2][2] + P1 + P2, A[1][1] + A[3][2] + P1 + P2} = min{P2+P1+P2, P1+P1+P2}={2P2+P1, 2P1+P2}={1.1, 1.6}=1.1 1이 루트 2가 루트 3이 루트 2가 루트 이 루트 1가 루트 가 루트

16 최적 이진검색 트리 문제 - 동적 계획법:설계 예제 3. 9 (p. 121)

17 최적 이진검색 트리 문제 - 동적 계획법:설계 R: 최적 트리를 구축할 수 있는 2차원 배열
R[i][j]: i번째 키부터 j번째 키까지를 포함한 최적 트리의 Root 키 인덱스 정보 2 david 3 1 4

18 최적 이진검색 트리 문제 - 동적 계획법:알고리즘
[알고리즘 3.9] 최적 이진검색 트리 float optsearchtree (int n, float[] p, index[][] R) { int i, j, k, diagonal; float minavg; float[][] A = new float[1 … n+1][0 … n]; for (i=1; i<=n; i++) { A[i][i-1] = 0; A[i][i] = p[i]; R[i][i-1] = 0; R[i][i] = i; } A[n+1][n] = 0; R[n+1][n] = 0; for (diagonal=1; diagonal <= n - 1; diagonal++) for (i=1; i <= n - diagonal; i++) { j = i + diagonal; return (A[1][n]);

19 최적 이진검색 트리 문제 - 동적 계획법:알고리즘