Tree & Heap SANGJI University Kwangman Ko kkman@sangji.ac.kr.

Presentation on theme: "Tree & Heap SANGJI University Kwangman Ko kkman@sangji.ac.kr."— Presentation transcript:

1 Tree & Heap SANGJI University Kwangman Ko

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

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

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

5 하위트리(subtree) 방문(visiting) 순회(traversing) 레벨(level) 높이(height)
하나의 큰 트리에 속해있는 부분트리. 방문(visiting) 노드에 도착해 노드의 자료 값을 읽는 행위. 순회(traversing) 트리의 노드 전체를 방문하는 행위. 레벨(level) 어떤 노드의 레벨은 루트노드로부터 얼마나 많이 떨어졌는지를 의미 여기에서는 루트를 레벨 1로 가정. 높이(height) 높이는 최장 루트-잎 경로의 길이이다.

6 노드(node) 루트(root) 서브트리(subtree) 단말노드(leaf node) 비단말노드 레벨(level)
트리의 구성요소 루트(root) 부모가 없는 노드(A) 서브트리(subtree) 하나의 노드와 그 노드들의 자손들로 이루어진 트리 단말노드(leaf node) 자식이 없는 노드(A,B,C,D) 비단말노드 적어도 하나의 자식을 가지는 노드(E,F,G,H,I,J) 레벨(level) 트리의 각층의 번호 높이(height) 트리의 최대 레벨(3) 차수(degree) 노드가 가지고 있는 자식 노드의 개수

7 7

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

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

10 생김새 특징 왼쪽 자식(left child), 오른쪽 자식(right child).
왼쪽 자식의 키(key)는 부모노드의 키보다 작고, 오른쪽 자식의 키는 부모노드의 키보다 크다.

11 노드의 개수가 n개이면 간선의 개수는 n-1

12 높이가 h인 이진 트리 최소 h개의 노드 최대 2h-1개의 노드

13 n개의 노드를 가지는 이진 트리의 높이 최대 n, 최소 log2(n+1)

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

15

16 3. 이진 트리 구현 배열 표현법 모든 이진트리를 포화 이진트리라고 가정 각 노드에 번호 부여, 그 번호를 배열의 인덱스

17 배열 구현법에서 인덱스 결정 노드 i의 부모 노드 인덱스 : i/2 노드 i의 왼쪽 자식노드 인덱스 : 2i

18 링크 표현법 포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법

19 노드 구조, in C 노드 구조체로 구현 각 노드가 포인터(=링크)를 가지고 있어 노드와 노드를 연결
교재 p.256, 프로그램 7.1 참고. typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; }

20 4. 트리 순회(traverse) 순회(traversal) 순회 방법 트리의 노드들을 체계적으로 방문하는 것
전위 순회(preorder traversal), VLR 루트 노드, 왼쪽 자식, 오른쪽 를 먼저 방문. 중위 순회(inorder traversal), LVR 왼쪽 자손, 루트, 오른쪽 자손 노드 순서로 방문. 후위 순회(postorder traversal), LRV 루트 노드보다 자손 노드를 먼저 방문.

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

22

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

24 + * / a b c d 1 2 3 5 6 7 8

25

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

27

28 전위, 중위, 후위 순회 구현 선택 방법 교재 p.265, 프로그램 7.3 참고.
레벨 순회, 그림 7-31, 프로그램 7.4 참고.

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

30 수식 a + b a - (b × c) (a < b) or (c < d) 전위순회 + a b - a × b c or < a b < c d 중위순회 a - b × c a < b or c < d 후위순회 a b + a b c × - a b < c d < or

31 5. 이진 트리 연산 노드 개수 탐색 트리안의 노드의 개수를 계산
각 서브트리에 대하여 순환 호출한 다음, 반환되는 값에 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; }

32 트리 높이 구하기 서브트리에 대하여 순환호출 서브트리들의 반환값 중에서 최대값을 구하여 반환
int get_height(TreeNode *node) { int height=0; if( node != NULL ) height = 1 + max(get_height(node->left), get_height(node->right)); return height; }

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

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

35 탐색(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;

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

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

38 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);

39

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

41 pubilc Node findMin() {
Node current = root; while (current.leftChild != null) current = current.leftChild; return current; } public Node findMax() { while (current.rightChild != null) current = current.rightChild;

42

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

44

45 insert_node(T,z) p←NULL; t←root; while t≠NULL do p←t; if z->key < p->key then t←p->left; else t←p->right; if p=NULL then root←z;// 트리가 비어있음 else if z->key < p->key then p->left←z else p->right←z

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

47 1. 삭제하려는 노드의 자식이 없을 때, 단말 노드 삭제
삭제 노드의 부모 노드에게서 삭제 노드를 가리키는 링크를 null　 If (current.leftChild == null && current.rightChild == null) { if (current == root) root = null; else if (current == parent.leftChild) parent.leftChild = null; else parent.rightChild = null; }

48 단말 노드의 부모 노드를 찾아서 연결을 삭제(null)

49 2. 삭제하려는 노드의 자식이 하나일 때 삭제하려는 노드의 자식노드와 부모노드를 바로 연결.

50

51 3. 삭제하려는 노드의 자식이 둘일 때 후보 노드(candidate node)
삭제하려는 노드의 자식 중 하나로 그 위치를 대체할 수 없음 삭제될 노드의 위치를 채워줄 후보 노드 선정. 후보 노드(candidate node) 삭제될 노드의 키 값보다 바로 위의 키 값을 가진 노드나 바로 아래의 키 값을 가진 값을 후보 노드로 선택.

52 후보 노드 선정 1 삭제될 노드보다 큰 값을 갖는 (오른쪽) 서브 트리 선택.
서브 트리에서 가장 작은 값을 갖는 노드를 후보 노드로 지정.

53 후보 노드 선정 2 삭제될 노드보다 작은 값을 갖는 (왼쪽) 서브 트리 선택.
서브 트리에서 가장 큰 값을 갖는 노드를 후보 노드로 지정.

54 삭제하려는 노드의 자식이 둘일 때 잘못된 대체의 예

55 후보노드가 삭제 노드의 오른쪽 자식일 경우 부모 노드에서 삭제 노드에 대한 링크 절단 후보 노드로 링크를 연결.
삭제 노드의 왼쪽 자식은 삭제 노드와의 링크 절단, 후보 노드의 왼쪽 자식으로 링크.

56 후보노드가 삭제노드의 오른쪽 자식의 왼쪽 자손일 경우
후보노드의 오른쪽 자식 후보노드의 부모노드에 대한 왼쪽 자식 노드로 저정 삭제노드의 오른쪽 자식 후보노드의 오른쪽 자식으로 지정. 부모노드에서 삭제노드에 대한 링크 절단, 후보노드로 연결 삭제노드의 왼쪽 자식 삭제노드와의 링크를 끊고 후보노드의 왼쪽 자식으로 연결

57

58

59 7 효율성 특징 노드의 수를 N, 레벨의 수를 L 트리 연산은 하위 레벨로의 탐색을 포함.
꽉 찬 트리에서 노드의 반 정도가 맨 아래 레벨에 존재. 노드들에 대한 연산(삽입, 삭제 등)은 최하위 레벨에 있는 노드까지 찾는 연산을 필요로 함 탐색하는 동안 최소한 하나의 레벨에 하나의 노드를 방문 어떠한 연산을 하는데 걸리는 시간은 트리의 레벨에 따라 유추 노드의 수를 N, 레벨의 수를 L L = log2(N + 1)

60 Chap 8: 우선순위 큐

61 1. 기본 개념 큐(queue) 우선순위 큐(priority queue) 먼저 들어온 자료를 먼저 처리
우선순위가 더 높은 자료를 먼저 처리 FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 처리    자료구조    삭제되는 요소    스택    가장 최근에 들어온 데이터    큐    가장 먼저 들어온 데이터    우선순위큐    가장 우선순위가 높은  데이터

62 우선순위 큐 구현 방법 구현방법, 교재 pp304-305 필독 배열을 이용한 우선순위 큐 연결 리스트를 이용한 우선순위 큐
히프(heap)를 이용한 우선순위 큐

63 힙(heap) 종류 우선순위 큐와 비슷한구체적인 자료구조, 완전 이진 트리
우선 순위 설정 방법, 우선 순위 높은 자료 추출 등의 방법 포함 큐 자료중 우선 순위가 가장 높은 자료를 선택 종류 최대 히프(max heap) 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리 key(부모노드) ≥key(자식노드) 최소 히프(min heap) 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리 key(부모노드) ≤key(자식노드)

64

65 이진 힙(binary heap) 이진 힙 조건 조건 1 : 완전 이진 트리(complete binary tree) 구조.
조건 2 : 부모 노드는 두 자식 노드보다 우선순위가 높다.

66 힙의 구현 방법 배열을 이용한 힙 구현 완전 이진트리의 각 노드에 번호를 부여. 부연된 번호를 배열의 인덱스로 간주
왼쪽 자식의 인덱스 = (부모의 인덱스)*2 오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1 부모의 인덱스 = (자식의 인덱스)/2

67

68 완전 이진 트리의 구현 배열을 이용한 레벨 순서 순회(level order traverse) 방법

69 배열, 부모 노드와 자식 노드 관계 왼쪽 자식 = 부모 노드 * 2 + 1 오른쪽 자식 = 부모 노드 * 2 + 2
왼쪽 자식 = 부모 노드 * 2 + 1 오른쪽 자식 = 부모 노드 * 2 + 2 부모 노드 = (왼쪽 자식 – 1) / 2 부모 노드 = (오른쪽 자식 – 2) / 2

70 힙 구현 : 삽입 연산 개념 회사에서 신입 사원이 들어오면 일단 말단 위치에 앉힌 다음에, 신입 사원의 능력을 봐서 위로 승진시키는 것과 비숫 히프에 새로운 요소가 들어 오면, 일단 새로운 노드를 히프의 마지막 노드에 이어서 삽입 삽입 후에 새로운 노드를 부모 노드들과 교환해서 히프의 성질을 만족

71 조건 이진 힙 삽입 알고리즘 적어도 삽입과 삭제의 두 가지 메소드 필요
자료의 삽입 시 자료의 위치를 바꿔 트리의 루트에 우선순위가 가장 높은 노드를 확보 이진 힙 삽입 알고리즘 단계 1. 삽입할 자료를 트리의 마지막 위치에 넣는다. 단계 2. 부모 노드와 우선순위를 비교하여 계속 반복. 2-1. 부모 노드의 우선순위가 더 높을 경우, 삽입 종료. 2-2. 부모 노드의 우선순위가 더 낮을 경우, 부모 노드와 교환 한 뒤 비교를 계속. 2-3. 트리의 루트가 되면 삽입 동작 종료.

72

73

74 입력 순서 : 5, 3, 8, 14, 4, 16, 1, 10, 11, 2, 6, 20

75

76

77

78

79 힙 구현 : 삭제 연산 개념 최대히프에서의 삭제는 가장 큰 키값을 가진 노드를 삭제
회사에서 사장의 자리가 비게 되면 먼저 제일 말단 사원을 사장 자리로 올린 다음에, 능력에 따라 강등시키는 것과 비숫. 루트 노드를 삭제, 마지막 노드를 루트 노드로 이동 루트에서부터 단말노드까지의 경로에 있는 노드들을 교환하여 힙 성질 만족.

80 이진 힙 삭제 알고리즘 단계 1. 루트 노드 삭제 단계 2. 힙의 마지막 노드를 루트 노드 자리로 이동
단계 3. 자식 노드들과 우선순위를 비교 3-1. 두 자식 노드의 우선순위가 더 낮을 경우, 삭제 종료 3-2. 우선순위가 더 높은 자식 노드가 있을 경우, 두 자식 노드 중 우선순위가 더 높은 노드와 교환한 뒤 다시 비교 3-3. 자식을 갖지 않는 잎(leaf) 노드가 될 경우, 삭제 종료

81

82

83

84 응용 : 힙 정렬(Heap sort) 개요 효율적인 메모리 관리 삭제를 수행할 때마다 우선순위가 가장 높은 루트 노드를 반환
반환 받은 노드를 별도의 배열에 순서대로 저장하여 정렬 수행 단점 힙에 사용된 배열 외에 별도의 메모리 필요 비교적 느린 속도 효율적인 메모리 관리 삭제된 자료를 별도의 배열에 저장하는 것이 아니라, 힙에서 삭제되면서 생긴 빈 공간에 기록

85

86

87 // 우선 순위 큐인 히프를 이용한 정렬 void heap_sort(element a[], int n) { int i; HeapType h; init(&h); for(i=0;i<n;i++){ insert_max_heap(&h, a[i]); } for(i=(n-1);i>=0;i--){ a[i] = delete_max_heap(&h);