5 장 트 리

Transcription

1 5 장 트리 Copyright 2007 DBLAB, Seoul National University

2 트리구조 Copyright 2007 DBLAB, Seoul National University 2

3 트리 트리 : 하나이상의노드 (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

4 트리의표현 레벨 A 1 B C D 2 E F G H I J 3 K L M 4 Copyright 2007 DBLAB, Seoul National University 4

5 리스트표현 트리의리스트표현 (A(B(E(K,L),F),C(G),D(H(M),I,J))) 차수가 k 인트리에대한노드구조 공간낭비많음 k 원트리에서노드수가 n 이면 nk 의자식필드중 n(k-1)+1 개필드가 0 Copyright 2007 DBLAB, Seoul National University 5

6 왼쪽자식 - 오른쪽형제표현 노드구조 left child data right sibling 트리 A B C D E F G H I J K L M Copyright 2007 DBLAB, Seoul National University 6

7 차수가 2 인트리표현 차수가 2 인트리 왼쪽자식 - 오른쪽형제트리의오른쪽형제포인터를 45 회전 루트노드의오른쪽자식은공백 이진트리 (binary tree) 왼쪽자식 - 오른쪽자식트리 Copyright 2007 DBLAB, Seoul National University 7

8 트리표현 A A A B B B 트리왼쪽자식 - 오른쪽형제트리이진트리 A A A B B C B C 트리왼쪽자식-오른쪽형제트리이진트리 C Copyright 2007 DBLAB, Seoul National University 8

9 이진트리 (1) 이진트리의특성 한노드는최대두개의가지 왼쪽서브트리와오른쪽서브트리구별 0 개의노드를가질수있음 이진트리의정의 공백이거나두개의분리된이진트리로구성된노드의유한집합 Copyright 2007 DBLAB, Seoul National University 9

10 이진트리 (2) 이진트리와일반트리의차이점 공백이진트리존재 자식의순서구별 서로다른두이진트리 Copyright 2007 DBLAB, Seoul National University 10

11 이진트리 (3) 편향이진트리와완전이진트리 A A level 1 B B C 2 C D E F G 3 D H I 4 E (a) 편향이진트리 (b) 완전이진트리 5 Copyright 2007 DBLAB, Seoul National University 11

12 이진트리의성질 (1) 최대노드수 레벨 i 에서의최대노드수 : 2 i-1 (i 1) 깊이가 k 인이진트리가가질수있는최대노드수 : 2 k - 1(k 1) 증명 1 귀납기초 : 레벨 i=1 일때루트만이유일한노드이므로레벨 i=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

13 이진트리의성질 (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 n 0 = n 2 +1 Copyright 2007 DBLAB, Seoul National University 13

14 이진트리의성질 (3) 포화이진트리 (full binary tree) 깊이가 k 이고, 노드수가 2 k -1 (k 0) 인이진트리 노드번호 1,,2 K -1 까지순차적부여가능 1 깊이 Copyright 2007 DBLAB, Seoul National University 14

15 이진트리의성질 (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

16 이진트리의표현 (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

17 이진트리의표현 (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

18 이진트리의표현 (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

19 이진트리의표현 (4) 연결표현의예 A root B A 0 C B 0 D C 0 D 0 E 0 E 0 root A A B C B C D E F G D E 0 0 F 0 0 G 0 H I 0 H 0 0 I 0 Copyright 2007 DBLAB, Seoul National University 19

20 이진트리순회와트리반복자 트리순회 (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

21 중위순회 호출 currentnode 의값조치호출 currentnode 의값 조치 Driver * * / A 0 A 0 / B 0 B 0 * cout<< A cout<< / cout<< B cout<< * Driver 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

22 레벨순서순회 큐사용 루트방문 -> 왼쪽자식방문 -> 오른쪽자식방문 + * 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

23 스택없는순회 각노드에 parent ( 부모 ) 필드추가 스택을사용하지않아도루트노드로올라갈수있음 스레드 (thread) 이진트리로표현 각노드마다두비트필요 leftchild 필드와 rightchild 필드를루트로돌아갈수있는경로를유지하도록사용 경로상의주소스택은리프노드에저장 Copyright 2007 DBLAB, Seoul National University 23

24 만족성문제 (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

25 만족성문제 (2) 명제식의만족성 (satisfiability) 문제 식의값이 true가되도록, 변수에값을지정할수있는방법이있는가? ( x x 1 x2) ( x1 x3) 3 x 3 x 1 x 3 x 2 x 1 Copyright 2007 DBLAB, Seoul National University 25

26 만족성문제 (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

27 만족성문제 (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

28 스레드 (1) n 노드이진트리의연결표현 총링크의수 : 2n 0 링크의수 : n+1 root A B C D 0 E 0 0 F 0 0 G 0 0 H 0 0 I 0 Copyright 2007 DBLAB, Seoul National University 28

29 스레드 (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

30 스레드 (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

31 스레드이진트리의메모리표현 root f - f f A f f B f f C f f D f t E t t F t t G t t H t t I t f = false; t = true Copyright 2007 DBLAB, Seoul National University 31

32 스레드이진트리의중위순회 스택을이용하지않고중위순회가능 중위순회의후속자 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

33 스레드이진트리에서의노드삽입 s 의오른쪽자식으로 r 을삽입 Copyright 2007 DBLAB, Seoul National University 33

34 우선순위큐 우선순위가가장높은 ( 낮은 ) 원소를먼저삭제 임의의우선순위를가진원소삽입가능 최대우선순위큐 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

35 우선순위큐 표현방법 무순서선형리스트 IsEmpty() : O(1) Push() : O(1) Top() : Θ(n) Pop() : Θ(n) 최대히프 IsEmpty() : O(1) Top() : O(1) Push() : O(log n) Pop() : O(log n) Copyright 2007 DBLAB, Seoul National University 35

36 최대히프의정의 최대 ( 최소 ) 트리 : 각노드의키값이그자식의키값보다작지 ( 크지 ) 않은트리. 최대히프 : 최대트리이면서완전이진트리. 최소히프 : 최소트리이면서완전이진트리 최대히프 최소히프 Copyright 2007 DBLAB, Seoul National University 36

37 최대히프에서의삽입 삽입후에도최대히프유지 새로삽입된원소는부모원소와비교하면서최대히프가되는것이확인될때까지위로올라감 (a) (b) (c) (d) Copyright 2007 DBLAB, Seoul National University 37

38 최대히프에서의삭제 루트삭제 루트와마지막위치의노드교환후노드수 -1 루트와왼쪽자식, 오른쪽자식비교 가장큰것을루트로 (a) (b) (c) Copyright 2007 DBLAB, Seoul National University 38

39 이원탐색트리 사전 (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

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

41 이원탐색트리의탐색 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

42 순위에의한이원탐색트리의탐색 순위 (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 Copyright 2007 DBLAB, Seoul National University 42

43 이원탐색트리에서의삽입 x 의 key 값을가진노드를탐색 탐색이성공하면이키에연관된원소를변경 탐색이실패하면탐색이끝난지점에쌍을삽입 삽입 35 삽입 Copyright 2007 DBLAB, Seoul National University 43

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

45 이원탐색트리의조인과분할 (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

46 이원탐색트리의조인과분할 (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

47 이원탐색트리 (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

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

49 승자트리 (2) K=8 인경우의승자트리 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 Copyright 2007 DBLAB, Seoul National University 49

50 승자트리 (3) 승자트리에서한레코드가출력되고나서재구성 새로삽입된노드에서루트까지의경로를따라토너먼트재수행 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 Copyright 2007 DBLAB, Seoul National University 50

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

52 패자트리 (2) 0 6 전체승자 Run Copyright 2007 DBLAB, Seoul National University 52

53 포리스트 포리스트 (forest) n( 0) 개의분리 (disjoint) 트리들의집합 A E G B C D F H I Copyright 2007 DBLAB, Seoul National University 53

54 포리스트를이진트리로변환 (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

55 포리스트를이진트리로변환 (2) 세개의트리로구성된포리스트 A E G B C D F H 위그림의이진트리표현 I A B E C F G D H Copyright 2007 DBLAB, Seoul National University 55 I

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

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

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

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

60 분리합집합 분리합집합 (disjoint set union) S i S j = {x x 는 S i 또는 S j 에포함되는모든원소 } 두트리중의하나를다른트리의서브트리로넣음 S 1 S 2 or S 1 S 2 Copyright 2007 DBLAB, Seoul National University 60

61 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

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

63 가중규칙을이용한합집합 (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

64 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

65 최악의경우의트리 (1) Copyright 2007 DBLAB, Seoul National University 65

66 최악의경우의트리 (2) Copyright 2007 DBLAB, Seoul National University 66

67 붕괴규칙을이용한탐색알고리즘 붕괴규칙 (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

68 동치부류의응용 (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

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

70 동치부류의응용예제 (2) [-3] [-4] [-3] [-2] (c) 7 4, 6 8, 3 5,and 2 11 다음의트리 [-5] 0 [-4] 6 [-3] (d) 11 0 다음의트리 Copyright 2007 DBLAB, Seoul National University 70

71 이진트리의개수계산 상이한이진트리 n=2 일때서로다른이진트리 : 2 개 A A and B B n=2 일때서로다른이진트리 : 5 개 Copyright 2007 DBLAB, Seoul National University 71

72 스택순열 (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

73 스택순열 (2) 전위순열 (preorder permutation) 이진트리를전위순회에따라방문한노드들의순서 중위순열 (inorder permutation) 이진트리를중위순회에따라방문한노드들의순서 Copyright 2007 DBLAB, Seoul National University 73

74 스택순열 (3) 모든이진트리는유일한전위 - 중위순서쌍을가짐 n 개의노드를가진서로다른이진트리의수 = 1,2,...,n 의전위순열을가지는이진트리로부터얻을수있는중위순열의수 =1 부터 n 까지의수를스택에넣었다가가능한모든방법으로삭제하여만들수있는상이한순열의수 Copyright 2007 DBLAB, Seoul National University 74

75 행렬곱셈 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

76 상이한이진트리의수 (1) 이진트리의수를구하는생성함수 (generating function) i B(x) b i x i 0 순환관계에의하여 xb 2 (x)=b(x)-1 B(0)=b 0 =1 을이용하여이차방정식을풀면 B(x) x 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

77 상이한이진트리의수 (2) B(x) 에서 x n 의계수인 b n 은아래와같다. 1/ 2 n 2n 1 ( 1) 2 n 1 1 2n n 1 n b n b n O(4 n /n 3/2 ) Copyright 2007 DBLAB, Seoul National University 77