제 5 장 트 리

트리 구조

트리 트리 : 하나 이상의 노드(node)로 이루어진 유한집합 ①하나의 루트(root) 노드 ②나머지 노드들은 n(0)개의 분리 집합T1, T2, … , Tn으로 분할 (Ti : 루트의 서브트리) 노드 : 한 정보 아이템 + 다른 노드로 뻗어진 가지 노드의 차수(degree) : 노드의 서브트리 수 단말(리프) 노드 : 차수 = 0 비단말 노드 : 차수  0 자식 : 노드 X의 서브트리의 루트 (↔ 부모) 형제 : 부모가 같은 자식들 트리의 차수 = max{노드의 차수} 조상 : 루트까지의 경로상에 있는 모든 노드 노드 레벨 : 루트-레벨1, 자식 레벨=부모 레벨+1 트리의 높이(깊이) = max{노드 레벨}

트리의 표현 레벨 A 1 B C D 2 E F G H I J 3 K L M 4

리스트 표현 트리의 리스트 표현 (A(B(E(K,L),F),C(G),D(H(M),I,J))) 공간 낭비 많음 k원 트리에서 노드 수가 n이면 nk의 자식 필드 중 n(k-1)+1개 필드가 0

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

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

트리 표현 A B C 트리 왼쪽 자식-오른쪽 형제 트리 이진트리

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

이진 트리 (2) 이진 트리와 일반 트리의 차이점 공백 이진 트리 존재 자식의 순서 구별 서로 다른 두 이진 트리

이진 트리 (3) 편향 이진 트리와 완전 이진 트리 A B D E C F G H I level 1 2 3 4 5

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

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

이진 트리의 성질 (3) 포화 이진 트리(full binary tree) 깊이가 k이고, 노드수가 2k-1 (k≥0)인 이진 트리 노드 번호 1,…,2K-1 까지 순차적 부여 가능 1 2 4 8 9 5 10 11 3 7 12 13 14 15 깊이 4

이진 트리의 성질 (4) 완전 이진 트리(Complete binary tree) 깊이가 k이고 노드 수가 n인 이진 트리 D H I E C F G

이진 트리의 표현 (1) 배열 표현 1차원 배열에 노드를 저장 보조 정리 5.4 완전 이진 트리 : 낭비 되는 공간 없음 n 개의 노드를 가진 완전이진트리 ① parent(i) : if i  1 ② leftChild(i) : 2i if 2i ≤ n 왼쪽 자식 없음 if 2i > n ③ rightChild(i) : 2i+1 if 2i+1≤ n 오른쪽 자식 없음 if 2i + 1 > n 완전 이진 트리 : 낭비 되는 공간 없음 편향 트리 : 공간 낭비 최악의 경우, 깊이 k 편향 트리는 2k-1중 k개만 사용

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

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

이진 트리의 표현 (4) 연결 표현의 예 A B C D E root A root B E D H I C G F A B C D E B C D E root B C D E A root B E D H I C G F A B C D E F G H I

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

중위 순회 출력 : A/B*C*D+E 호출 Driver 1 2 3 4 5 6 7 8 9 + * / A B B cout<<‘A’ cout<<‘/’ cout<<‘B’ cout<<‘*’ currentNode의 값 조치 10 11 12 13 14 15 16 17 18 C D E cout<<‘C’ cout<<‘D’ cout<<‘+’ cout<<‘E’ 출력 : A/B*C*D+E

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

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

만족성 문제 (1) 규칙 명제 해석식(formula of propositional calculus) 변수 x1, x2 , … , xn 과 연산자 ∧, ∨, ￢으로 이루어진 식 변수 = {참, 거짓} 규칙 (1) 변수도 하나의 식 (2) x, y가 식일때, ￢x, x∧y, x∨y 도 식 (3) 연산순서는 ￢, ∧, ∨ 순, 괄호 사용 명제 해석식(formula of propositional calculus) 위 규칙을 이용해서 구성한 식

만족성 문제 (2) 명제식의 만족성(satisfiability) 문제 식의 값이 true가 되도록, 변수에 값을 지정할 수 있는 방법이 있는가? Ú Ù Ø x3 x1 x2

만족성 문제 (3) 가능한 모든 true와 false의 조합을 대입 : O(g 2n) g : 식을 계산하는데 필요한 시간 전체 식이 하나의 값이 될 때까지 서브 트리를 계산하면서 트리를 후위 순회 x1 x2 x3 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 ?

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

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

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

스레드 (3) 노드 구조 헤드 노드 leftThread == false : leftChild  포인터 == true : leftChild  스레드 rightThread == false : rightChild  포인터 == true : rightChild  스레드 헤드 노드 연결되지 않은 스레드 제거 LeftThread LeftChild data RightChild RightThread TRUE FALSE

스레드 이진 트리의 메모리 표현 f - A C B D t E F G I H f = false; t = true root

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

스레드 이진 트리에서의 노드 삽입 s의 오른쪽 자식으로 r을 삽입

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

우선순위 큐 표현 방법 무순서 선형 리스트 최대 히프 IsEmpty() : O(1) Push() : O(1) Top() : Θ(n) Pop() : Θ(n) 최대 히프 Top() : O(1) Push() : O(log n) Pop() : O(log n)

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

최대 히프에서의 삽입 삽입 후에도 최대 히프 유지 새로 삽입된 원소는 부모 원소와 비교하면서 최대 히프가 되는 것이 확인될 때까지 위로 올라감 20 15 14 10 2 (a) (b) 21 (c) (d) 5

최대 히프에서의 삭제 루트 삭제 루트와 마지막 위치의 노드 교환 후 노드 수 -1 루트와 왼쪽 자식, 오른쪽 자식 비교 가장 큰 것을 루트로. 15 14 10 20 6 2 (a) (b) (c)

이원 탐색 트리 사전(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; //지시된 키를 가진 쌍 삭제 };

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

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

순위에 의한 이원 탐색 트리의 탐색 순위(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; 3 30 2 5 1 40 leftSize key

이원 탐색 트리에서의 삽입 x의 key값을 가진 노드를 탐색 탐색이 성공하면 이 키에 연관된 원소를 변경 탐색이 실패하면 탐색이 끝난 지점에 쌍을 삽입 30 30 30 80 삽입 35 삽입 5 40 5 40 5 40 2 2 80 2 35 80

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

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

이원 탐색 트리의 조인과 분할 (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 ⊇ 루트, 왼쪽 서브트리

이원 탐색 트리(n)의 높이 이원 탐색 트리의 원소 수 : n 최악의 경우 평균 이원 탐색 트리의 높이 = O(log n ) 균형 탐색 트리(balanced search tree) 최악의 경우에도 height = O(log n )이 되는 트리 탐색, 삽입, 삭제의 시간 복잡도 : O(h) AVL, 2-3, 2-3-4, 레드-블랙(red-black), B 트리, B+ 트리 등

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

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

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

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

패자 트리 (2) 9 10 20 6 17 8 90 1 2 4 3 5 7 11 12 13 14 15 전체 승자 Run 1 2 3 4 5 6 7 8

포리스트 포리스트(forest) n(0)개의 분리(disjoint) 트리들의 집합 A B D C E F G H I

포리스트를 이진 트리로 변환 (1) 각 트리를 이진 트리로 변환 변환된 모든 이진 트리들을 루트의 rightChild로 연결 정의 만일 T1,T2,…,Tn이 트리로 된 포리스트라 하면 이 포리스트에 대응하는 이진 트리, B(T1,T2,…,Tn)은 n=0이면 공백 B 의 루트 = T1의 루트 왼쪽 서브 트리 = B(T11,T12,…,T1m) T11,T12,…,T1m는 T1의 루트의 서브트리 오른쪽 서브트리 = B(T2,…,Tn)

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

포리스트 순회 (1) 포리스트 전위(forest preorder) 포리스트 중위(forest inorder) 첫 번째 트리의 서브트리들을 포리스트 전위 순회 F의 나머지 트리들을 포리스트 전위로 순회 포리스트 중위(forest inorder) F의 첫 번째 트리의 서브트리를 포리스트 중위로 순회 첫 번째 트리의 루트 방문 나머지 트리들을 포리스트 중위로 순회

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

분리 집합의 표현 (1) 분리 집합(disjoint set)의 트리 표현 모든 집합들은 쌍별로 분리 된다고 가정 임의의 두 집합은 어떤 원소도 공유하지 않음 자식에서부터 부모로 가는 링크로 연결 6 8 7 2 3 5 4 1 9 S1 S2 S3

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

분리 합집합 분리 합집합(disjoint set union) Si∪Sj = {x|x는 Si 또는 Sj에 포함되는 모든 원소} 두 트리 중의 하나를 다른 트리의 서브트리로 넣음 6 4 7 8 1 9 S1 È S2 or

SimpleUnion과 SimpleFind 분석 변질(degenerate) 트리 n개의 원소가 각각 n개의 집합에 하나씩 포함된 경우 Si={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( ) = O(n2) n-1 n-2 · · ·

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

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

WeightedUnion과 WeightedFind의 분석 WeightedUnion : O(1) WeightedFind(=SimpleFind) : O(log m) 합집합의 결과가 m개의 노드를 가진 트리의 높이≤ u-1개의 합집합 + f개의 탐색 : O(u+f log u) 트리의 노드 수 ≤ u

최악의 경우의 트리 (1)

최악의 경우의 트리 (2)

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

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

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

동치 부류의 응용 예제 (2) 2 [-2] 5 7 11 1 3 [-3] 6 10 [-4] 8 9 4 4 (c) 7≡4, 6≡8, 3≡5,and 2≡11 다음의 트리 2 5 7 11 1 3 [-3] 6 10 [-4] 8 9 [-5] 4 (d) 11≡0 다음의 트리

이진 트리의 개수 계산 상이한 이진 트리 n=2 일때 서로 다른 이진 트리 : 2개 n=2 일때 서로 다른 이진 트리 : 5개 A B and n=2 일때 서로 다른 이진 트리 : 5개

스택 순열 (1) 전위 순서 ABCDEFGHI, 중위 순서 BCAEDGHFI 전위 순서: A는 트리의 루트 반복 A B,C D,E,F,G,H,I A D,E,F,G,H,I B C A B C D E F G I H

스택 순열 (2) 전위 순열(preorder permutation) 중위 순열(inorder permutation) 이진 트리를 전위 순회에 따라 방문한 노드들의 순서 중위 순열(inorder permutation) 이진 트리를 중위 순회에 따라 방문한 노드들의 순서 1 2 3 4 5 6 7 9 8

스택 순열 (3) 모든 이진 트리는 유일한 전위-중위 순서 쌍을 가짐 n개의 노드를 가진 서로 다른 이진트리의 수

행렬 곱셈 n개 행렬의 곱셈 n개의 행렬을 곱하는 방법의 수 bn Mij = Mi*Mi+1* ... *Mj M1*M2*M3* ... *Mn n개의 행렬을 곱하는 방법의 수 bn b1=2, b2=1, b3=2, b4=5 Mij = Mi*Mi+1* ... *Mj M1n = M1i*Mi+1,n M1i_계산 방법 수 : bi Mi+1,n 계산 방법 수 : bn-i bn = 루트,노드 수가 bi, bn-i-1인 서브트리로 된 이진트리들

상이한 이진 트리의 수 (1) 이진 트리의 수를 구하는 생성 함수(generating function) 순환 관계에 의하여 xB2(x)=B(x)-1 B(0)=b0=1을 이용하여 이차 방정식을 풀면 이항 정리를 이용하여 (1-4x)1/2를 확장하면

상이한 이진 트리의 수 (2) B(x)에서 xn의 계수인 bn은 아래와 같다.