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