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

Slides:



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

언어의 자서전 소단원 (1) 단원. 언어의 특성 기호성 자의성 사회성 규칙성 창조성 역사성.
알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
2.6 탐색(Search) 1. 순차검색 (Sequential Search, Linear Search)
주요 내용 기본 용어 이진 트리(binary tree) 이진 탐색 트리(binary search tree)
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
Internet Computing KUT Youn-Hee Han
CHAP 8:우선순위큐 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 20).
8. 파일 인덱스: 탐색트리 (Search Tree)
T-tree 엄종진 강원대학교 컴퓨터과학과.
Chapter 7. Binary Search Trees - 보충 자료-
트리 이 현 직
자료구조론 9장 트리(tree).
6장 트리.
Internet Computing KUT Youn-Hee Han
CHAP 7:트리.
7장 이원 탐색 트리.
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 50).
강의 #7 트리(Tree).
쉽게 배우는 알고리즘 5장. 검색트리
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
제 7 장. 트리(Tree).
Chapter 8. AVL Search Trees
제 11 장 다원 탐색 트리.
트리 2-3 트리 2-3 트리의 노드 AVL은 균형 트리 (Balanced Tree)를 지향
CHAPTER 5 트리(Tree).
제 5 장 트 리 5.1 트리 5.2 이진 트리 5.3 스레드 이진 트리.
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
CHAP 7: 트 리 (1) 한 성 대 학 교 정보통신공학과 봉 정 식.
자료구조 과제 풀이(6,7,8차) Yong-hwan Kim
12 검색.
13. 탐색 트리.
Tree & Heap SANGJI University Kwangman Ko
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
다음 주 과제 기말고사 시험범위 : 7장 ~12장 필기시험 : 2016년 12월 12일(6교시) 필기장소 : E???
AVLTree vs 편향 Tree.
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
자료구조(SCSC) Data Structures
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Tree & Heap SANGJI University Kwangman Ko
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
11장 균형 탐색 트리.
선택 정렬 #define SWAP(x, y, t) {(t) = (x); (x) = (y); (y) = (t);}
제 1 강.
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호.
CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호.
13장. 균형 탐색 트리 and the pain you must suffer to learn them
C언어 응용 제 15 주 검색.
동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차
트리.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
CHAP 12:탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 12 : 탐색.
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
5장. 선택 알고리즘.
알고리즘(Algorithm) 유비쿼터스 컴퓨팅학과 교수 송 창근
제 8 장 계산복잡도 개론 검색 문제 알고리즘 강의 슬라이드 8 검색 문제
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
강의 #11 탐색(Search).
탐색 선형 탐색, 이진 탐색, 이진 탐색 트리.
Chapter 07 트리.
(Ⅰ) 독서와 언어의 본질 언어의 본질 1 2 [고등 국어] – 독서와 문법 독서의 본질 (1) 독서의 특성
컴퓨터 개론 √ 원리를 알면 IT가 맛있다 쉽게 배우는 컴퓨터 기본 원리 한빛미디어 교재출판부.
우선순위 큐 & Heap Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
[CPA340] Algorithms and Practice Youn-Hee Han
11. 트리.
Presentation transcript:

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

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

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

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

이진 검색 트리 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

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

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

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

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

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

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

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

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

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

최적 이진검색 트리 문제 - 동적 계획법:설계 A[1][3] = min{A[1][0] + A[2][3] + P1 + P2 + P3 , A[1][1] + A[3][3] + P1 + P2 + P3 , 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가 루트 3이 루트 1가 루트 2가 루트

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

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

최적 이진검색 트리 문제 - 동적 계획법:알고리즘 [알고리즘 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]);

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