Tree & Heap SANGJI University Kwangman Ko

Slides:



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

알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
이진 나무 구조 강윤섭 2008년 5월 23일.
2.6 탐색(Search) 1. 순차검색 (Sequential Search, Linear Search)
주요 내용 기본 용어 이진 트리(binary tree) 이진 탐색 트리(binary search tree)
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
CHAP 8:우선순위큐 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 20).
T-tree 엄종진 강원대학교 컴퓨터과학과.
연결리스트(linked list).
Linked List 학기 SANGJI University.
컴퓨터 프로그래밍 기초 [Final] 기말고사
트리 이 현 직
자료구조론 9장 트리(tree).
Internet Computing KUT Youn-Hee Han
CHAP 7:트리.
7장 이원 탐색 트리.
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 50).
강의 #7 트리(Tree).
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
제 3 장 선형 리스트 3.1 선형 리스트 3.2 연결 리스트 3.3 다항식.
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express Slide 1 (of 13)
제 7 장. 트리(Tree).
제3장 스택과 큐.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
제 11 장 다원 탐색 트리.
7장 인덱스된 순차 화일.
트리 2-3 트리 2-3 트리의 노드 AVL은 균형 트리 (Balanced Tree)를 지향
CHAPTER 5 트리(Tree).
자료구조: CHAP 4 리스트 (1) 순천향대학교 컴퓨터공학과 하 상 호.
제 5 장 트 리 5.1 트리 5.2 이진 트리 5.3 스레드 이진 트리.
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
CHAP 7: 트 리 (1) 한 성 대 학 교 정보통신공학과 봉 정 식.
13. 탐색 트리.
Introduction To Data Structures Using C
Tree & Heap SANGJI University Kwangman Ko
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 10:그래프 (2) 순천향대학교 하상호.
JA A V W. 03.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
8장. 상호 배타적 집합의 처리.
* 프로그램을 간단히 하기 위해 malloc 성공체크는 안 함
11장 균형 탐색 트리.
알고리즘: 우선순위 큐(8장) 순천향대학교 컴퓨터 학부 하 상 호.
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
선택 정렬 #define SWAP(x, y, t) {(t) = (x); (x) = (y); (y) = (t);}
제 1 강.
자료구조: CHAP 7(2) 트리 순천향대학교 컴퓨터공학과 하 상 호.
CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호.
CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호.
13장. 균형 탐색 트리 and the pain you must suffer to learn them
트리.
객체기반 SW설계 팀활동지 4.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
데이터 동적 할당 Collection class.
알고리즘: 우선순위 큐(8장) 순천향대학교 컴퓨터 학부 하 상 호.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
탐색 선형 탐색, 이진 탐색, 이진 탐색 트리.
Chapter 07 트리.
제 4장 트리.
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
컴퓨터 개론 √ 원리를 알면 IT가 맛있다 쉽게 배우는 컴퓨터 기본 원리 한빛미디어 교재출판부.
우선순위 큐 & Heap Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
C++ Espresso 제15장 STL 알고리즘.
11. 트리.
Presentation transcript:

Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 프로그래밍언어론(2006, 상지대학교)

트리 개요 트리(Tree) 계층적인 구조를 나타내는 비선형(Non-linear) 자료구조 트리는 부모-자식 관계의 노드로 구성 응용분야 계층적인 조직 표현 파일 시스템 인공지능에서의 결정 트리 kkman@sangji.ac.kr

트리 자료구조를 사용하는 이유 ? 다른 자료구조와 달리 비선형 구조 배열 탐색은 빠르지만 O(logN), 삽입/삭제는 느림 (O(N)) 연결리스트 삽입/삭제는 빠르지만 (O(1)), 탐색은 느림 (O(N)) 트리 삽입과 삭제, 탐색이 모두 빠름 (O(logN)) kkman@sangji.ac.kr

트리에서 자주 사용하는 용어 루트(root) 트리의 가장 상위에 있는 노드로 루트는 항상 하나만 존재 부모, 자식(parent, children) 링크로 연결된 노드 중 위에 있는 노드를 부모 노드, 아래 있는 노드를 자식 노드. 경로(path) 어떤 한 노드에서 다른 노드까지 링크를 통해 이동했을 때, 거쳐 온 노드들의 집합. 키(key) 자료 항목을 찾거나 또는 다른 동작을 하기 위해 필요한 값 각 자료 항목을 구분해주는 역할, 자료 항목을 대표하는 값 kkman@sangji.ac.kr

A B C D E F G I J H kkman@sangji.ac.kr

kkman@sangji.ac.kr

트리의 일반적인 성질 한 노드에서 다르 노드로 가는 경로가 유일 N개의 노드를 갖는 트리는 N-1개의 링크. 임의의 두 노드에 대해 최소 공통 선조 (least common ancestor)를 갖음. 두 노드가 가질 수 있는 가장 가까운 선조 경로가 중복되지 않는다면 두 노드간의 경로는 반드시 한 노드에서 최소 공통 선조까지 올라갔다 다른 노드로 내려오는 유일한 경로만이 존재. N개의 노드를 갖는 트리는 N-1개의 링크. 그래프와 달리 루트를 제외하고는 모든 노드가 자신의 선조를 향한 하나의 링크를 가지고 있음. N개의 노드를 가진 트리는 N-1개의 링크를 갖음. kkman@sangji.ac.kr

2. 이진 트리 이진 트리(binary tree) 트리 구조 중 자식을 최대 둘까지 가질 수 있는 트리 모든 노드의 차수가 2 이하 구현하기가 편리함 모든 노드가 2개의 서브 트리를 가지고 있는 트리 서브 트리는 공집합일 수 있음. 이진 트리에는 서브 트리간의 순서가 존재 각 노드들은 자식이 없거나, 하나 또는 두 개의 자식 노드를 유지 가장 보편적인 트리 구조, 이진 탐색 트리(binary search tree) kkman@sangji.ac.kr

< < 특징 왼쪽 자식(left child), 오른쪽 자식(right child). 루트 키(key) 값 왼쪽 자식 노드의 키값보다 크다. 오른쪽 자식 노드의 키값보다 작다. 50 < < 27 68 kkman@sangji.ac.kr

노드의 개수가 n개 간선(edge)의 개수는 ?? n-1 A B C D E F G kkman@sangji.ac.kr

높이가 h인 이진 트리 최소 h개의 노드 최대 2h-1개의 노드 kkman@sangji.ac.kr

n개의 노드를 가지는 이진 트리 높이 최대 n, 최소 log2(n+1) kkman@sangji.ac.kr

완전 이진 트리(complete binary tree) 마지막 레벨을 제외한 각 레벨의 노드들이 모두 차있고, 마지막 레벨에서는 노드들이 순서대로 존재하는 상태 포화 이진 트리(full binary tree) 모든 레벨이 꽉 찬 이진트리 kkman@sangji.ac.kr

이진트리에서 노드 번호 1 3 2 6 7 4 5 8 9 10 11 12 13 14 15 kkman@sangji.ac.kr

3. 이진트리 구현 배열 표현법 모든 이진트리를 포화 이진트리라고 가정 각 노드에 번호 부여, 그 번호를 배열의 인덱스 1 A A 1 A 2 B 2 3 3 C B C 4 D 5 E 6 F 4 5 6 7 7 G D E F G 8 9 10 kkman@sangji.ac.kr

배열 구현법에서 인덱스 결정 경사 이진트리 노드 i의 부모 노드 인덱스 : i/2 노드 i의 왼쪽 자식노드 인덱스 : 2i A B C D E kkman@sangji.ac.kr

연결리스트 표현법 노드의 링크를 이용하여 부모노드가 자식노드를 가리키게 (포인팅)하는 방법 1 A A 2 3 B C B C 4 5 6 7 F D E F G kkman@sangji.ac.kr

노드 구조(in C) 구조체로 구현 각 노드가 포인터(=링크)를 가지고 있어 노드와 노드를 연결 typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } kkman@sangji.ac.kr

4. 트리 순회(traverse) 순회(traversal) 순회 방법 트리의 노드들을 일정한 순서로 방문 전위 순회(preorder traversal), VLR. 루트노드, 왼쪽 자손, 오른쪽 자손 노드 순서로 방문 중위 순회(inorder traversal), LVR. 왼쪽 자손, 루트, 오른쪽 자손 노드 순서로 방문 후위 순회(postorder traversal), LRV. 왼쪽 자손, 오른쪽 자손, 루트 노드 순서로 방문 kkman@sangji.ac.kr

V A L R B C D E F G kkman@sangji.ac.kr

전위 순회(Preorder Traverse) 루트를 먼저 방문하는 순회방법 1. 루트 노드. 2. 왼쪽 서브트리. 3. 오른쪽 서브트리. preorder( TreeNode *root ){     if ( root ){       printf("%d", root->data ); // 노드 방문       preorder( root->left ); // 왼쪽 하위트리       preorder( root->right ); // 오른쪽 하위트리     } } kkman@sangji.ac.kr

전위 방문 순서?? ① 50 ② 68 27 55 82 12 36 7 19 49 78 kkman@sangji.ac.kr

중위 순회 (Inorder Traverse) 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 방문 1. 왼쪽 서브트리 방문. 2. 루트 노드 방문. 3. 오른쪽 서브트리. inorder( TreeNode *root ){     if ( root ){       inorder( root->left ); // 왼쪽서브트리       printf("%d", root->data );  // 루트노드       inorder( root->right ); // 오른쪽서브트리     } } kkman@sangji.ac.kr

a * b + c / d + a * b c / d * / a b c d kkman@sangji.ac.kr

50 68 27 55 82 12 36 7 19 49 78 kkman@sangji.ac.kr

후위 순회 (Postorder Traverse) 왼쪽서브트리->오른쪽서브트리 -> 루트노드 순으로 방문 1. 왼쪽 서브트리 방문. 2. 오른쪽 서브트리 방문. 3. 루트 노드 방문. postorder( TreeNode *root ){ if ( root ){ postorder( root->left ); // 왼쪽서브트리 postorder( root->right ); // 오른쪽서브트리 printf("%d", root->data ); // 루트노드 } kkman@sangji.ac.kr

50 68 27 55 82 12 36 7 19 49 78 kkman@sangji.ac.kr

kkman@sangji.ac.kr

수식 트리(evalaution tree) 산술식을 트리 형태로 표현한 것 비단말노드: 연산자(operator) 단말노드: 피연산자(operand) kkman@sangji.ac.kr

수식 a + b 전위순회 + a b 중위순회 후위순회 a b + + a b kkman@sangji.ac.kr

- 수식 a - (b × c) 전위순회 중위순회 후위순회 a * b c kkman@sangji.ac.kr

이진 트리 연산 노드 개수 탐색 트리안의 노드의 개수를 계산 각 서브트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환 int get_node_count(TreeNode *node) { int count=0; if( node != NULL ) count = 1 + get_node_count(node->left)+ get_node_count(node->right); return count; } kkman@sangji.ac.kr

트리 높이 구하기 서브트리에 대하여 순환호출 서브트리들의 반환값 중에서 최대값을 구하여 반환 int get_node_count(TreeNode *node) { int count=0; if( node != NULL ) count = 1 + get_node_count(node->left)+ get_node_count(node->right); return count; } kkman@sangji.ac.kr

스레드(thread) 이진 트리 정의 및 특징 이진트리의 NULL 링크를 이용하여 순환호출 없이도 트리의 노드들을 순회 단말노드와 비단말노드의 구별을 위히여 is_thread 필드 필요 kkman@sangji.ac.kr

이진 트리 탐색 이진 트리(binary tree) 모든 원소의 키는 유일 왼쪽 서브트리의 키값들은 루트의 키값보다 작다. 오른쪽 서브트리의 키값들은 루트의 키값보다 크다. 왼쪽과 오른쪽 서브트리도 이진 트리 특성 유지. kkman@sangji.ac.kr

이진트리에서 탐색(search) 이진트리의 탐색 특징 어떤 주어진 키를 가지고 그 키와 동일한 값을 갖는 노드를 찾는 것. 루트노드부터 방문하여 노드의 키 값과 주어진 키 값을 비교하여 내려가는 식으로 진행. 이진트리의 탐색 특징 탐색작업을 효율적으로 하기 위한 자료구조 key(왼쪽서브트리)≤key(루트노드)≤key(오른쪽서브트리) 이진탐색를 중위순회하면 오름차순으로 정렬. kkman@sangji.ac.kr

루트 27 12 36 왼쪽서브트리 오른쪽서브트리 7 19 49 49 루트보다 작은값 루트보다 큰값 kkman@sangji.ac.kr

탐색(search) 어떤 주어진 키를 가지고 그 키와 동일한 값을 갖는 노드를 찾는 것. 루트노드부터 방문하여 노드의 키 값과 주어진 키 값을 비교하여 내려가는 식으로 진행. Public Node find(int key) { Node current = root; while (current.keyData != key) { if (current == null) return null; if (key < current.keyData) current = current.leftChild; else current = current.rightChild; } return current; kkman@sangji.ac.kr

특징 탐색작업을 효율적으로 하기 위한 자료구조 key(왼쪽서브트리)≤key(루트노드)≤key(오른쪽서브트리) 이진탐색를 중위순회하면 오름차순으로 정렬. 27 12 36 7 19 49 49 kkman@sangji.ac.kr

알고리즘 비교한 결과가 같으면 탐색 성공. 주어진 키 값이 루트 노드의 키값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작. 주어진 키 값이 루트 노드의 키값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작. kkman@sangji.ac.kr

else if k<x->key then return search(x->left, k); search(x, k) if x=NULL then return NULL; if k=x->key then return x; else if k<x->key then return search(x->left, k); else return search(x->right, k); kkman@sangji.ac.kr

kkman@sangji.ac.kr

최대값과 최소값 탐색 최소값 : 트리의 가장 왼쪽 최대값 : 트리의 가장 오른쪽에 존재 현 노드보다 작은 값은 왼쪽 자식에, 큰 값은 오른쪽 자식에 위치. 최소값 : 트리의 가장 왼쪽 루트에서 왼쪽 자식을 따라 내려가면서 더 이상 왼쪽 자식이 없는 노드를 만나면 그 노드가 최소값을 가진 노드. 최대값 : 트리의 가장 오른쪽에 존재 최대값은 오른쪽 자식을 따라가면 찾을 수 있다. kkman@sangji.ac.kr

kkman@sangji.ac.kr

이진트리에서 삽입 방법 노드가 삽입될 위치 탐색. 적절한 경로를 따라 내려간 뒤 그 위치의 부모가 되는 노드 탐색 삽입될 위치의 부모노드의 키보다 삽입될 노드의 키가 작다면 부모노드의 왼쪽 자식으로, 크다면 부모노드의 오른쪽 자식으로 생성. kkman@sangji.ac.kr

50 50 27 27 12 36 12 36 49 kkman@sangji.ac.kr

kkman@sangji.ac.kr

이진트리에서 삭제 삭제 노드가 단말 노드일 경우 삭제 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우 삭제하려는 노드의 자식 노드가 하나일 때 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우 삭제하려는 노드의 자식 노드가 둘일 때 kkman@sangji.ac.kr

삭제하려는 노드의 자식이 없을 경우 단말 노드 삭제 삭제 노드의 부모 노드에게서 삭제 노드를 가리키는 링크를 null kkman@sangji.ac.kr

35 18 68 7 26 3 12 22 30 kkman@sangji.ac.kr

삭제하려는 노드의 자식노드가 하나, 삭제하려는 노드의 자식노드와 부모노드를 바로 연결. kkman@sangji.ac.kr

kkman@sangji.ac.kr