5 장 트 리 - PDF Free Download

트리 트리 : 하나이상의노드 (node) 로이루어진유한집합 1 하나의루트 (root) 노드 2 나머지노드들은 n( 0) 개의분리집합 T 1, T 2,, T n 으로분할 (T i : 루트의서브트리 ) 노드 : 한정보아이템 + 다른노드로뻗어진가지 노드의차수 (degree) : 노드의서브트리수 단말 ( 리프 ) 노드 : 차수 = 0 비단말노드 : 차수 0 자식 : 노드 X 의서브트리의루트 ( 부모 ) 형제 : 부모가같은자식들 트리의차수 = max{ 노드의차수 } 조상 : 루트까지의경로상에있는모든노드 노드레벨 : 루트 - 레벨 1, 자식레벨 = 부모레벨 +1 트리의높이 ( 깊이 ) = max{ 노드레벨 } Copyright 2007 DBLAB, Seoul National University 3

이진트리의성질 (1) 최대노드수 레벨 i 에서의최대노드수 : 2 i-1 (i 1) 깊이가 k 인이진트리가가질수있는최대노드수 : 2 k - 1(k 1) 증명 1 귀납기초 : 레벨 i=1 일때루트만이유일한노드이므로레벨 i=1 에서의최대노드수 : 2 1-1 = 2 0 = 1 귀납가설 : i 를 1 보다큰임의의양수라고가정. 레벨 i-1 에서의최대노드수는 2 i-2 라고가정 귀납과정 : 가설에의해레벨 i-1 의최대노드수는 2i-2 각노드의최대차수는 2 이므로레벨 i 의최대노드수는레벨 i-1 에서의최대노드수의 2 배 2 i-1 증명 2 k i 1 ( 레벨i의최대노드 수) k 2 i 1 i 1 2 k 1 Copyright 2007 DBLAB, Seoul National University 12

이진트리의성질 (2) 리프노드수와차수가 2 인노드수와의관계 n 0 =n 2 +1 n 0 : 리프노드수 n 2 : 차수가 2 인노드수 증명 n 1 : 차수 1 인노드수, n : 총노드수, B : 총가지수 n = n 0 + n 1 + n 2 루트를제외한모든노드들은들어오는가지가하나씩있으므로 n = B + 1 모든가지들은차수가 2 또는 1 인노드에서뻗어나오므로 B = n 1 + 2n 2 n = B + 1 = n 1 + 2n 2 + 1 n 0 = n 2 +1 Copyright 2007 DBLAB, Seoul National University 13

이진트리의성질 (4) 완전이진트리 (Complete binary tree) 깊이가 k 이고노드수가 n 인이진트리 각노드들이깊이가 k 인포화이진트리에서 1 부터 n 까지 번호를붙인노드와 1대 1로일치 n 노드완전이진트리의높이 : log 2 ( n 1) A B C D E F G H I Copyright 2007 DBLAB, Seoul National University 15

이진트리의표현 (1) 배열표현 1차원배열에노드를저장 보조정리 5.4 n 개의노드를가진완전이진트리 1 parent(i) : i / 2 if i 1 2 leftchild(i) : 2i if 2i n 왼쪽자식없음 if 2i > n 3 rightchild(i) : 2i+1 if 2i+1 n 오른쪽자식없음 if 2i + 1 > n 완전이진트리 : 낭비되는공간없음 편향트리 : 공간낭비 최악의경우, 깊이 k 편향트리는 2 k -1 중 k 개만사용 Copyright 2007 DBLAB, Seoul National University 16

이진트리의표현 (2) E 편향트리 B C D A [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]... [16] - A B - C - - - D -... E H D 완전이진트리 A B E F I C G [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] - A B C D E F G H I Copyright 2007 DBLAB, Seoul National University 17

이진트리의표현 (3) 연결표현 노드표현 left child 클래스정의 data 부모알기어려움 parent 필드추가 right child template <class T> class Tree; // 전방선언 template <class T> class TreeNode{ friend class Tree<T>; private: T data; TreeNode<T> *leftchild; TreeNode<T> *rightchild; }; LeftChild data RightChild template <class T> class Tree { public: // 트리연산들... private: TreeNode<T> *root; }; Copyright 2007 DBLAB, Seoul National University 18

이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder) 순회 산술식의이진트리표현 + * E * D / C A B Copyright 2007 DBLAB, Seoul National University 20

중위순회 호출 currentnode 의값조치호출 currentnode 의값 조치 Driver 1 2 3 4 5 4 6 3 7 8 7 9 2 + * * / A 0 A 0 / B 0 B 0 * cout<< A cout<< / cout<< B cout<< * 10 11 10 12 1 13 14 13 15 Driver 16 17 16 18 C 0 C 0 * D 0 D 0 + E 0 E 0 cout<< C cout<< * cout<< D cout<< + cout<< E 출력 : A/B*C*D+E Copyright 2007 DBLAB, Seoul National University 21

레벨순서순회 큐사용 루트방문 -> 왼쪽자식방문 -> 오른쪽자식방문 + * E * D / C A B template <class T> void Tree<T>::LevelOrder() {// 이진트리의레벨순서순회 Queue<TreeNode<T>*> q; TreeNode<T> * currentnode = root; while(currentnode){ Visit(currentNode); if(currentnode->leftchild) q.push(currentnode->leftchild); if(currentnode->rightchild) q.push(currentnode->rightchild); if(q.isempty()) return; currentnode = q.front(); q.pop(); } } Copyright 2007 DBLAB, Seoul National University 22

만족성문제 (1) 변수 x 1, x 2,, x n 과연산자,, 으로이루어진식 변수 = { 참, 거짓 } 규칙 (1) 변수도하나의식 (2) x, y 가식일때, x, x y, x y 도식 (3) 연산순서는,, 순, 괄호사용 명제해석식 (formula of propositional calculus) 위규칙을이용해서구성한식 x x ) 1 ( 2 x3 Copyright 2007 DBLAB, Seoul National University 24

만족성문제 (3) 가능한모든 true 와 false 의조합을대입 : O(g 2 n ) g : 식을계산하는데필요한시간 전체식이하나의값이될때까지서브트리를계산하면서트리를후위순회 x 1 x 2 x 3 formular T T T? T T F? T F T? T F F? F T T? F T F? F F T? F F F? Copyright 2007 DBLAB, Seoul National University 26

만족성문제 (4) 후위순회계산 Tree 템플릿클래스를 T=pair<Operator, bool> 로인스턴스화 enum Operator { Not, And, Or, True, False}; for n 개변수에대한 2 n 개의가능한참값조합 { 다음조합을생성 ; 그들의값을변수에대입 ; 명제식을나타내는트리를후위순회로계산 ; if(formula.data().second()){cout << current combination; return;} } cout << no satisfiable combination ; Copyright 2007 DBLAB, Seoul National University 27

스레드 (2) 스레드 (Thread) 0 링크필드를다른노드를가리키는포인터로대치 if p->rightchild == 0, p->rightchild = p 의중위후속자에대한포인터 if p->leftchild = 0, p->leftchild = p 의중위선행자에대한포인터 root A B C D E F G H I Copyright 2007 DBLAB, Seoul National University 29

스레드 (3) 노드구조 LeftThread LeftChild data RightChild RightThread TRUE FALSE leftthread == false : leftchild 포인터 == true : leftchild 스레드 rightthread == false : rightchild 포인터 == true : rightchild 스레드 헤드노드 연결되지않은스레드제거 Copyright 2007 DBLAB, Seoul National University 30

스레드이진트리의중위순회 스택을이용하지않고중위순회가능 중위순회의후속자 x->rightthread == true : x->rightchild == false : 오른쪽자식의왼쪽자식링크를따라가서 LeftThread==true 인노드 스레드이진트리에서중위후속자를찾는함수 T* ThreadedInorderIterator::Next() {// 스레드이진트리에서 currentnode 의중위후속자를반환 ThreadedNode<T> *temp = currentnode->rightchild; if(!currentnode->rightthread) while(!temp->leftthread) temp = temp->leftchild; currentnode = temp; if(currentnode == root) return 0; else return &currentnode->data; } Copyright 2007 DBLAB, Seoul National University 32

우선순위큐 우선순위가가장높은 ( 낮은 ) 원소를먼저삭제 임의의우선순위를가진원소삽입가능 최대우선순위큐 template <class T> class MaxPQ{ public: virtual ~MaxPQ(){} // 가상파괴자 virtual bool IsEmpty() const = 0; // 우선순위큐가공백이면 true 를반환 virtual const T& Top() const =0; // 최대원소에대한참조를반환 virtual void Push(const T&) = 0; // 우선순위큐에원소를삽입 virtual void Pop() = 0; // 최대우선순위를가진원소를삭제 }; Copyright 2007 DBLAB, Seoul National University 34

최대히프의정의 최대 ( 최소 ) 트리 : 각노드의키값이그자식의키값보다작지 ( 크지 ) 않은트리. 최대히프 : 최대트리이면서완전이진트리. 최소히프 : 최소트리이면서완전이진트리. 14 9 30 최대히프 12 7 6 3 25 10 8 6 5 2 10 11 최소히프 7 4 20 83 21 10 8 6 50 Copyright 2007 DBLAB, Seoul National University 36

이원탐색트리 사전 (dictionary) pair< 키, 원소 > 의집합 template <class K, class E> class Dictionary{ public: virtual bool IsEmpty() const=0; // 공백이면 true 반환 virtual pair<k,e>*get(const K&) const = 0; // 지시한키값을가진쌍에대한포인터반환, 쌍이없으면 0 반환 virtual void Insert(const pair<k,e>&)=0; // 쌍을삽입, 키가중복되면관련원소갱신 virtual void Delete(const K&)=0; // 지시된키를가진쌍삭제 }; Copyright 2007 DBLAB, Seoul National University 39

이원탐색트리 정의 이진트리로서공백가능하고, 만약공백이아니라면 (1) 모든원소는서로상이한키를갖는다. (2) 왼쪽서브트리의키들은그루트의키보다작다. (3) 오른쪽서브트리의키들은그루트의키보다크다 (4) 왼쪽과오른쪽서브트리도이원탐색트리이다. 이원탐색트리 20 30 60 15 25 5 40 70 12 10 22 2 65 80 (a) X (b) O (c) O Copyright 2007 DBLAB, Seoul National University 40

이원탐색트리의탐색 k = 루트의키 : 성공적종료 k < 루트의키 : 왼쪽서브트리탐색 k > 루트의키 : 오른쪽서브트리탐색 template <class K, class E> //Driver pair<k,e>* BST<K,E>::Get(const K& k) {// 키 k 를가진쌍을이원탐색트리 (*this) 에서탐색 // 쌍을발견하면포인터반환, 아니면 0 반환 return Get(root, k); } template <class K, class E> //Workhorse pair<k,e>* BST<K,E>::Get(TreeNode <pair <K,E>>*p, const K& k) { if(!p) return 0; if(k<p->data.first) return Get(p->leftChild,k); if(k>p->data.first) return Get(p->rightChild,k); return &p->data; } Copyright 2007 DBLAB, Seoul National University 41

순위에의한이원탐색트리의탐색 순위 (rank) 중위순서에서의위치 leftsize = 왼쪽서브트리의원소수 + 1 순위에의한이원탐색트리의탐색 template <class K, class E> // 순위에의한탐색 pair<k,e>* BST<K,E>::RankGet(int r) {//r번째작은쌍을탐색한다. TreeNode<pair<K,E>>*currentNode = root; while(currentnode) if(r<currentnode->leftsize) currentnode = currentnode->leftchild; else if (r> currentnode->leftsize) { } r -= currentnode->leftsize; currentnode = currentnode->rightchild; } else return &currentnode->data; return 0; 1 2 leftsize key 3 30 2 5 1 40 Copyright 2007 DBLAB, Seoul National University 42

이원탐색트리에서의삭제 리프원소의삭제 부모의자식필드에 0 을삽입. 삭제된노드반환 하나의자식을가진비리프노드의삭제 삭제된노드의자식을삭제된노드의자리에위치 30 5 30 을삭제 5 40 2 40 2 80 80 두개의자식을가진비리프노드의삭제 왼쪽서브트리에서가장큰원소나오른쪽서브트리에서가장작은원소로대체 대체된서브트리에서대체한원소의삭제과정진행 시간복잡도 : O(h) Copyright 2007 DBLAB, Seoul National University 44

이원탐색트리의조인과분할 (1) ThreeWayJoin(small, mid, big) 이원탐색트리 small 과 big 에있는쌍들과쌍 mid 로구성되는이원탐색트리를생성 새로운노드를하나얻어서 데이타필드 =mid 왼쪽자식포인터 =small.root 오른쪽자식포인터는 big.root O(1) TwoWayJoin(small, big) 두이원탐색트리 small 과 big 에있는모든쌍들을포함하는하나의이원탐색트리생성 small 또는 big 이공백일경우 공백이아닌것이이원탐색트리 둘다공백이아닌경우 small 에서가장큰키값을가진 mid 쌍삭제 : small ThreeWayJoin(small, mid, big) 수행 O(height(small)) Copyright 2007 DBLAB, Seoul National University 45

이원탐색트리의조인과분할 (2) Split(k, small, mid, big) 이원탐색트리 *this 를세부분으로분할 small 은 *this 의원소중키값이 k 보다작은모든쌍포함 mid 는 *this 의원소중키값이 k 와같은쌍포함 big 은 *this 의원소중키값이 k 보다큰모든쌍포함 k = root->data.first 인경우 small = *this 의왼쪽서브트리 mid = 루트에있는쌍 big = *this 의오른쪽서브트리 k < root->data.first 인경우 big 루트, 오른쪽서브트리 k > root->data.first small 루트, 왼쪽서브트리 Copyright 2007 DBLAB, Seoul National University 46

이원탐색트리 (n) 의높이 이원탐색트리의원소수 : n 최악의경우 이원탐색트리의높이 = n 키 [1,2,3,...,n] 을순서대로삽입 평균 이원탐색트리의높이 = O(log n ) 균형탐색트리 (balanced search tree) 최악의경우에도 height = O(log n ) 이되는트리 탐색, 삽입, 삭제의시간복잡도 : O(h) AVL, 2-3, 2-3-4, 레드 - 블랙 (red-black), B 트리, B+ 트리등 Copyright 2007 DBLAB, Seoul National University 47

승자트리 (1) 런 (run) 하나의순서순차로합병될 k 개의순서순차 각런은 key 필드에따라비감소순서로정렬 승자트리 (winner tree) 각노드가두개의자식노드중더작은노드를나타내는완전이진트리 루트노드 : 트리에서가장작은노드 리프노드 : 각런의첫번째레코드 이진트리에대한순차할당기법으로표현 Copyright 2007 DBLAB, Seoul National University 48

승자트리 (2) K=8 인경우의승자트리 1 6 2 3 6 8 4 5 6 7 9 6 8 17 8 9 10 10 9 20 6 11 12 13 14 15 8 9 90 17 15 20 20 15 15 11 95 18 16 38 30 25 50 16 99 20 28 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 Copyright 2007 DBLAB, Seoul National University 49

승자트리 (3) 승자트리에서한레코드가출력되고나서재구성 새로삽입된노드에서루트까지의경로를따라토너먼트재수행 4 9 2 9 15 1 8 5 6 7 8 9 10 11 12 13 14 15 10 9 20 15 8 9 90 17 8 8 3 17 15 20 20 25 15 11 95 18 16 38 30 28 50 16 99 20 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 Copyright 2007 DBLAB, Seoul National University 50

패자트리 (1) 승자트리의문제점 재구성할때루트까지의경로를따라형제노드들사이에토너먼트발생 형제노드는전에시행되었던토너먼트의패자들 패자트리 (loser tree) 비리프노드가패자레코드에대한포인터유지 전체토너먼트의승자를표현하기위한노드 0 첨가 토너먼트는부모와비교 형제노드에는접근하지않음 Copyright 2007 DBLAB, Seoul National University 51

포리스트를이진트리로변환 (1) 각트리를이진트리로변환 변환된모든이진트리들을루트의 rightchild 로연결 정의 만일 T 1,T 2,,T n 이트리로된포리스트라하면이포리스트에대응하는이진트리, B(T 1,T 2,,T n ) 은 n=0 이면공백 B 의루트 = T 1 의루트왼쪽서브트리 = B(T 11,T 12,,T 1m ) T 11,T 12,,T 1m 는 T1 의루트의서브트리오른쪽서브트리 = B(T 2,,T n ) Copyright 2007 DBLAB, Seoul National University 54

포리스트순회 (1) 포리스트전위 (forest preorder) F가공백이면복귀 F의첫번째트리의루트방문 첫번째트리의서브트리들을포리스트전위순회 F의나머지트리들을포리스트전위로순회 포리스트중위 (forest inorder) F가공백이면복귀 F의첫번째트리의서브트리를포리스트중위로순회 첫번째트리의루트방문 나머지트리들을포리스트중위로순회 Copyright 2007 DBLAB, Seoul National University 56

포리스트순회 (2) 포리스트후위 (forest postorder) F가공백이면귀환 F의첫트리의서브트리를포리스트후위로순회 나머지트리들을포리스트후위로순회 F의첫트리의루트를방문 포리스트레벨순서순회 포리스트의각루트부터시작하여노드를레벨순으로방문 레벨내에서는왼쪽에서부터오른쪽으로차례로방문 Copyright 2007 DBLAB, Seoul National University 57

분리집합의표현 (1) 분리집합 (disjoint set) 의트리표현 집합의모든원소는수 0,1,2,...,n-1 이라고가정 모든집합들은쌍별로분리된다고가정 임의의두집합은어떤원소도공유하지않음 자식에서부터부모로가는링크로연결 0 4 2 6 7 8 1 9 3 5 S 1 S 2 S 3 Copyright 2007 DBLAB, Seoul National University 58

분리집합의표현 (2) S 1, S 2, S 3 의데이타표현 Set Name Pointer S 1 0 4 2 S 2 6 7 8 1 9 3 5 S 3 S 1, S 2, S 3 의배열표현 i 번째원소 : 원소 i 를포함하는트리노드 원소 : 대응되는트리노드의부모포인터 루트의 parent 는 -1 i [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] parent -1 4-1 2-1 2 0 0 0 4 Copyright 2007 DBLAB, Seoul National University 59

SimpleUnion 과 SimpleFind 분석 변질 (degenerate) 트리 n 개의원소가각각 n 개의집합에하나씩포함된경우 S i ={i} ( 0 i < n) 초기상태 : n 개의노드들로이루어진포리스트 parent[i]= -1 (0 i n) Union(0,1), Union(1,2),Union(2,3),..., Union(n-2,n-1) n-1 번의합집합이 O(n) 시간에수행 Find(0), Find(1),..., Find(n-1) 수행 레벨 i 에있는원소에대한수행시간 : O(i) n번의 Find 수행 : O( i ) = O(n 2 ) n i 1 n-1 n-2 Copyright 2007 DBLAB, Seoul National University 61 0

가중규칙을적용한합집합 (1) Union(i,j) 를위한가중규칙 루트 i 를가진트리의노드수 < 루트 j 를가진트리의노드수 : j 를 i 의부모로 otherwise : i 를 j 의부모로 0 1 n-1 0 1 2 n-1 1 0 2 3 n-1 initial Union(0,1) Union(0,2) 0 1 2 3 Union(0,3) 4 n-1 0 1 2 3 n-1 Union(0,n-1) Copyright 2007 DBLAB, Seoul National University 62

가중규칙을이용한합집합 (2) 모든트리의루트에 count( 계수 ) 필드유지 루트의 parent 는 -1 이므로, 루트의 parent 에 count 유지 void sets::weightedunion(int i, int j) // 가중규칙을이용하여루트가 i 와 j(i j) 인집합의합을구함 // parent[i] = -count[i] 이며 parent[j] = -count[j] 임. { int temp = parent[i] + parent [j]; if (parent[i] > parent[j]) { // i 의노드수가적으면 parent[i] = j; // j 를새루트로만든다 parent[j] = temp; } else ( // j 의노드수가적거나같으면 parent[j] = i; // i 를새루트로만든다 parent[i] = temp; } } Copyright 2007 DBLAB, Seoul National University 63

WeightedUnion 과 WeightedFind 의분석 WeightedUnion : O(1) WeightedFind(=SimpleFind) : O(log m) 합집합의결과가 m 개의노드를가진트리의높이 log 2 m 1 u-1 개의합집합 + f 개의탐색 : O(u+f log u) 트리의노드수 u Copyright 2007 DBLAB, Seoul National University 64

붕괴규칙을이용한탐색알고리즘 붕괴규칙 (collapsing rule) 만일 j 가 i 에서루트로가는경로상에있고 parent[i] root(i) 면 parent[j] 를 root(i) 로지정 int Sets::CollapsingFind(int i) {// 원소 i 를포함하는루트를찾음 // 붕괴규칙을이용하여 i 로부터루트로가는모든노드를붕괴시킴 for (int r = i; parent[r] >= 0; r = parent[r]); // 루트를찾음 while( i!= r) { // 붕괴 int s = parent[i]; parent[i] = r; i = s; } return r; } Copyright 2007 DBLAB, Seoul National University 67

동치부류의응용 (1) 동치쌍 (equivalence pair) 의처리 동치부류 (equivalence class) 를집합으로간주 i j i 와 j 를포함하고있는집합찾기 다른집합에포함된경우합집합으로대체 같을때는아무작업도수행할필요없음 n 개의변수, m 개의동치쌍 초기포리스트형성 : O(n) 2m 개의탐색, 최대 min{n-1,m} 개의합집합 : O(n+mα(2m, min{n-1,m})) Copyright 2007 DBLAB, Seoul National University 68

동치부류의응용예제 (1) [-1] [-1] [-1] [-1] [-1] [-1] [-1] [-1] [-1] [-1] [-1] [-1] 0 1 2 3 4 5 6 7 8 9 10 11 (a) Initial trees [-2] [-2] [-2] [-1] [-1] [-1] [-1] [-1] 0 3 6 8 2 5 7 11 4 1 10 9 0 4, 3 1, 6 10, and 8 9 다음의높이 -2 트리 Copyright 2007 DBLAB, Seoul National University 69

스택순열 (1) 전위순서 ABCDEFGHI, 중위순서 BCAEDGHFI 전위순서 : A 는트리의루트 중위순서 : BC 는 A 의왼쪽서브트리, EDGHFI 는오른쪽서브트리 B,C 전위순서 : B 가다음번루트 중위순서 : B 의왼쪽서브트리는공백, 오른쪽은 C A A D,E,F,G,H,I B D,E,F,G,H,I 반복 B C A C E D G F H I Copyright 2007 DBLAB, Seoul National University 72

행렬곱셈 n 개행렬의곱셈 M 1 *M 2 *M 3 *... *M n n 개의행렬을곱하는방법의수 b n b 1 =2, b 2 =1, b 3 =2, b 4 =5 Mij = M i *M i+1 *... *M j M 1n = M 1i *M i+1,n n-1 M 1i _ 계산방법수 : b i b n bibn-1, n 1 M i+1,n 계산방법수 : b n-i i 1 b n = 루트, 노드수가 b i, b n-i-1 인서브트리로된이진트리들 n-1 bn bibn-i-1, n 1그리고b0 i 1 1 Copyright 2007 DBLAB, Seoul National University 75

상이한이진트리의수 (1) 이진트리의수를구하는생성함수 (generating function) i B(x) b i x i 0 순환관계에의하여 xb 2 (x)=b(x)-1 B(0)=b 0 =1 을이용하여이차방정식을풀면 B(x) 1-1- 4x 2x 이항정리를이용하여 (1-4x) 1/2 를확장하면 B(x) 1 2x 1 n 0 1/ 2 n n m 2m 1 m 4x ( 1) 2 x m 0 1/ 2 m Copyright 2007 DBLAB, Seoul National University 76