7장 이원 탐색 트리.

7장 이원 탐색 트리

순서 7.1 이원 탐색 트리 7.2 히프 7.3 선택 트리

이원 탐색 트리 (binary search tree) (1)
임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료구조 모든 연산은 키값을 기초로 실행 정의 : 이원 탐색 트리(binary search tree:BST) 이진 트리 공백이 아니면 다음 성질을 만족 모든 원소는 상이한 키를 갖는다. 왼쪽 서브 트리 원소들의 키 < 루트의 키 오른쪽 서브 트리 원소들의 키 > 루트의 키 왼쪽 서브 트리와 오른쪽 서브 트리 : 이원 탐색 트리

예 그림 (a): 이원 탐색 트리가 아님 그림 (b), (c): 이원 탐색 트리임

이원 탐색 트리에서의 탐색 (순환적 기술) 키값이 x인 원소를 탐색 시작 : 루트 이원 탐색 트리가 공백이면, 실패로 끝남 루트의 키값 = x 이면, 탐색은 성공하며 종료 키값 x < 루트의 키값이면, 루트의 왼쪽 서브트리만 탐색 키값 x > 루트의 키값이면, 루트의 오른쪽 서브트리만 탐색 연결 리스트로 표현 노드 구조 : left key right

탐색 알고리즘 searchBST(B, x) // B는 이원 탐색 트리 // x는 탐색 키값 p ← B; if (p = null) then // 공백 이진 트리로 실패 return null; if (p.key = x) then // 탐색 성공 return p; if (p.key < x) then // 오른쪽 서브트리 탐색 return searchBST(p.right, x); else return searchBST(p.left, x); // 왼쪽 서브트리 탐색 end searchBST()

이원 탐색 트리에서의 삽입 키값이 x인 새로운 원소를 삽입 x를 키값으로 가진 원소가 있는가를 탐색 탐색이 실패하면, 탐색이 종료된 위치에 원소를 삽입 예 : 키값 13, 50의 삽입 과정

삽입 알고리즘 insertBST(B, x) // B는 이원 탐색 트리, x는 삽입할 키값 p ← B; while (p  null) do { if (x = p.key) then return; // 키값을 가진 노드가 이미 있음 q ← p; // q는 p의 부모 노드를 지시 if (x < p.key) then p ← p.left; else p ← p.right; } newNode ← getNode(); // 삽입할 노드를 만듦 newNode.key ← x; newNode.right ← null; newNode.left ← null; if (B = null) then B ← newNode; // 공백 이원 탐색 트리인 경우 else if (x < q.key) then // q는 탐색이 실패하여 종료된 원소 q.left ← newNode; else q.right ← newNode; return; end insertBST()

이원 탐색 트리에서의 원소 삭제 삭제하려는 원소의 키값이 주어졌을 때 이 키값을 가진 원소를 탐색 원소를 찾으면 삭제 연산 수행 해당 노드의 자식수에 따른 세가지 삭제 연산 자식이 없는 리프 노드의 삭제 자식이 하나인 노드의 삭제 자식이 둘인 노드의 삭제

자식이 없는 리프 노드의 삭제 부모 노드의 해당 링크 필드를 널(null)로 만들고 삭제한 노드 반환 예 : 키값 40을 가진 노드의 삭제시

자식이 하나인 노드의 삭제 삭제되는 노드 자리에 그 자식 노드를 위치 예 : 원소 20을 삭제

자식이 둘인 노드의 삭제 삭제되는 노드 자리 왼쪽 서브트리에서 제일 큰 원소 또는 오른쪽 서브트리에서 제일 작은 원소로 대체 해당 서브트리에서 대체 원소를 삭제 대체하게 되는 노드의 차수는 1 이하가 됨

예 : 키값이 50인 루트 노드의 삭제시

삭제 알고리즘의 골격 (왼쪽 서브트리에서의 최대 원소값으로 대체시) deleteBST(B, x) p  the node to be deleted; //주어진 키값 x를 가진 노드 parent  the parent node of p; // 삭제할 노드의 부모 노드 if (p = null) then return; // 삭제할 원소가 없음 case { p.left = null and p.right = null : // 삭제할 노드가 리프 노드인 경우 if (parent.left = p) then parent.left  null; else parent.right  null; p.left = null or p.right = null : // 삭제할 노드의 차수가 1인 경우 if (p.left ≠ null) then { if (parent.left = p) then parent.left  p.left; else parent.right  p.left; } else { if (parent.left = p) then parent.left ← p.right; else parent.right  p.right; } p.left ≠ null and p.right ≠ null : // 삭제할 노드의 차수가 2인 경우 q  maxNode(p.left); // 왼쪽 서브트리에서 최대 키값을 가진 원소를 탐색 p.key  q.key; deleteBST(p.left, p.key); end deleteBST()

스트링 타입의 키값을 가진 이원 탐색 트리 구축 char "R"을 가지고 있는 노드 탐색 트리에 없는 char "C"를 탐색

이원 탐색 트리 구축 및 탐색 프로그램 #include<stdio.h> typedef struct TreeNode { char key; struct TreeNode* left; struct TreeNode* right; } treeNode; treeNode* insertKey(treeNode* p, char x) { /* insert() 함수가 사용하는 보조 순환 함수 */ treeNode* newNode; if (p == NULL) { newNode = (treeNode*)malloc(sizeof(treeNode)); newNode->key = x; newNode->left = NULL; newNode->right = NULL; return newNode; } else if (x < p->key) { /* x를 p의 왼쪽 서브트리에 삽입 */ p->left = insertKey(p->left, x) return p; }

else if (x > p->key) { // x를 p의 오른쪽 서브트리에 삽입 p->right = insertKey(p->right, x); return p; } else { // key 값 x가 이미 이원 탐색 트리에 있음 printf("Duplicated key value"); return p; } } void insert(treeNode** root, char x) { *root = insertKey(*root, x); treeNode* find(treeNode* root, char x) { // 키 값 x를 가지고 있는 노드의 포인터를 반환 treeNode* p; p = root; while (p != NULL) { if (x < p->key) { p = p->left; } else if (x == p->key) { // 키 값 x를 발견 return p; } else p = p->right; } printf("No such key value is found"); return p;

void printNode(treeNode* p) { // printTree() 함수에 의해 사용되는 순환 함수 if (p != NULL) { printf("("); printNode(p->left); // leftsubtree를 프린트 printf("%c", p->key); printNode(p->right); // rightsubtree를 프린트 printf(")"); } } void printTree(treeNode* root) { // 서브트리 구조를 표현하는 괄호 형태로 트리를 프린트 printNode(root); printf(“＼n"); void freeNode(treeNode* p) { // 노드에 할당된 메모리를 반환 freeNode(p->left); freeNode(p->right); free(p); void freeTree(treeNode* root) { // 트리에 할당된 메모리를 반환 freeNode(root);

int main() { // 예제 실행을 위한 main() 함수 treeNode* root = NULL; // 공백 이원 탐색 트리 root를 선언 treeNode* N = NULL; treeNode* P = NULL; /* 그림 7.6의 BST를 구축 */ insert(&root, 'S'); insert(&root, 'J'); insert(&root, 'B'); insert(&root, 'D'); insert(&root, 'U'); insert(&root, 'M'); insert(&root, 'R'); insert(&root, 'Q'); insert(&root, 'A'); insert(&root, 'G'); insert(&root, 'E'); /* 구축된 BST를 프린트 */ printf("The Tree is "); printTree(root); printf("\n");

/* key 값 'R'을 탐색하고 프린트 */ printf("Search For 'R'\n"); N = find(root, 'R'); printf("Key of node found = %c\n", N->key); printf("\n"); /* key 값 'C'를 탐색하고 프린트 */ printf("Search For 'C'\n"); P = find(root, 'C'); if (P != NULL) { printf("Key of node found = %c", P->key); } else { printf("Node that was found = NULL"); } printf("\n"); /* 트리에 할당된 메모리를 반환 */ freeTree(root); return 0; }

이원 탐색 트리의 결합과 분할 3원 결합 : threeJoin (aBST, x, bBST, cBST) 이원 탐색 트리 aBST와 bBST에 있는 모든 원소들과 키값 x를 갖는 원소를 루트 노드로 하는 이원 탐색 트리 cBST를 생성 가정 aBST의 모든 원소 < x < bBST의 모든 원소 결합이후에 aBST와 bBST는 사용하지 않음 3원 결합의 연산 실행 새로운 트리 노드 cBST를 생성하여 key값으로 x를 지정 left 링크 필드에는 aBST를 설정 right 링크 필드에는 bBST를 설정

3원 결합의 예 연산 시간 : O(1) 이원 탐색 트리의 높이 : max{height(aBST) , height(bBST)} + 1

2원 결합 : twoJoin(aBST, bBST, cBST) 두 이원 탐색 트리 aBST와 bBST를 결합하여 aBST와 bBST에 있는 모든 원소들을 포함하는 하나의 이원 탐색 트리 cBST를 생성 가정 aBST의 모든 키값 < bBST의 모든 키값 연산후 aBST와 bBST는 사용 하지 않음 2원 결합 연산 실행 aBST나 bBST가 공백인 경우 cBST : 공백이 아닌 aBST 혹은 bBST aBST와 bBST가 공백이 아닌 경우 두 이원 탐색 트리 결합 방법은 두 가지로 나뉨

aBST에서 키 값이 가장 큰 원소를 삭제 이 결과 이원 탐색트리 : aBST’ 삭제한 가장 큰 키값 : max threeJoin(aBST’, max, bBST, cBST) 실행 실행 시간 : O(height (aBST)) cBST의 높이 : max{height(aBST), height(bBST)} + 1 20 40 27 15 25 35 80 20 40 23 27 30 15 25 35 80 (a) aBST (b) bBST 23 30 (c) cBST

bBST에서 가장 작은 키값을 가진 원소를 삭제 이 결과 이원 탐색 트리 : aBST’ 삭제한 가장 작은 키값 : min threeJoin(aBST, min, bBST', cBST)를 싷행

분할 : split(aBST, x, bBST, cBST) aBST 를 주어진 키값 x를 기준으로 두 이원 탐색 트리 bBST와 cBST로 분할 bBST : x보다 작은 키값을 가진 aBST의 모든 원소 포함 cBST : x보다 큰 키값을 가진 aBST의 모든 원소 포함 bBST와 cBST는 각각 이원 탐색 트리 성질을 만족 키값 x가 aBST에 있으면 true 반환 , 아니면 false 반환

분할 연산 실행 aBST의 루트 노드가 키값 x를 가질 때 왼쪽 서브트리 : bBST 오른쪽 서브트리 : cBST True 반환 x < 루트 노드의 키값 루트와 그 오른쪽 서브트리는 cBST에 속한다. x > 루트 노드의 키값 루트와 그 왼쪽 서브트리는 bBST에 속한다. 키값 x를 가진 원소를 탐색하면서 aBST를 아래로 이동

Split( aBST , 25 , bBST , cBST )

이원 탐색 트리(binary search tree) (27)
분할 연산 알고리즘 splitBST(aBST, x, bBST, cBST) // x는 aBST를 분할하는 키 값 // 트리 노드는 left, key, right 필드로 구성 Small ← getTreeNode(); // 키 값 x보다 큰 원소로 된 BST Large ← getTreeNode(); // 키 값 x보다 작은 원소로 된 BST S ← Small; // Small BST의 순회 포인터 L ← Large; // Large BST의 순회 포인터 p ← aBST; // aBST의 순회 포인터

분할 연산 알고리즘 while (p ≠ null) do { if (x = p.key) then { S.right ← p.left; L.left ← p.right; bBST ← Small.right; cBST ← Large.left; return true; // 키 값 x가 aBST에 있음 } else if (x < p.key) then { L.left ← p; L ← p; p ← p.left; else { S.right ← p; S ← p; p ← p.right; bBST ← Small.right; cBST ← Large.left; return false; // 키 값 x는 aBST에 없음 } end splitBST()

이원 탐색 트리의 높이 이원 탐색 트리의 높이가 크면 원소의 검색,삽입,삭제 연산 수행 시간이 길어진다. n개의 노드를 가진 이원 탐색 트리의 최대 높이 : n - 1 평균적인 이원 탐색 트리의 높이 : O(log n) 균형 탐색 트리 (balanced search tree) 탐색 트리의 높이가 최악의 경우 O(logn)이 되는 경우 검색, 삽입, 삭제 연산을 O(height)시간에 수행 예) AVL , 2-3, , red-black, B-tree

히프 (1) 특성 최대 히프(max heap): 각 노드의 키값이 그 자식의 키값보다 작지 않은 완전 이진 트리
최소 히프(min heap): 각 노드의 키값이 그 자식의 키값보다 크지 않은 완전 이진 트리 최대 히프 예

히프 (2) 최소 히프 예 최소 히프의 루트는 그 트리에서 가장 작은 키값 가짐
최대 히프의 루트는 그 트리에서 가장 큰 키값 가짐

히프 (3) 히프 추상 데이타 타입 히프 추상 데이타 타입에 포함될 기본 연산 ① 생성(create) : 공백 히프의 생성
② 삽입(insert) : 새로운 원소를 히프의 적절한 위치에 삽입 ③ 삭제(delete) : 히프로부터 키값이 가장 큰 원소를 삭제하고 반환

히프 (4) ADT Heap 데이타 : n, n>0, 개의 원소로 구성된 완전 이진 트리로 각 노드의 키 값은
그의 자식 노드의 키 값보다 작지 않다. 연산 : heap∈Heap; item∈Element; createHeap() := create an empty heap; insertHeap(heap, item) := insert item into heap; isEmpty(heap) := if (heap is empty) then return true else return false; deleteHeap(heap) := if (isEmpty(heap)) then return error else { item ← the largest element in heap; remove the largest element in heap; return item; } End Heap

히프 (5) 히프에서의 삽입 삽입 예 5개의 원소로 된 히프의 예(그림 (a))
이중 원으로 표현한 노드: 새로 확장될 노드의 위치 (그림 (b)) 키값 3 삽입시: 바로 완료 (그림 (c)) 키값 8 삽입시: 부모 노드와 교환후 완료 (그림 (d), (e)) 키값 19 삽입시: 부모 노드와 루트와 연속 교환후 완료 (그림 (f), (g), (h))

히프 (6) 18 13 12 5 8 19 (a)히프 (b) 삽입후의 히프구조 (e) 원소 8을 삽입 후
4 3 6 19 (a)히프 (b) 삽입후의 히프구조 (e) 원소 8을 삽입 후 (h) 원소 19 삽입 후 (c) 원소 3을 삽입 (f) 히프 (a)에 원소 19삽입 (g) 원소의 이동 (d)히프 (a)에 원소 8 삽입

히프 (7) 부모 노드 위치 결정 가정 최대 히프에서의 삽입 알고리즘 연결 표현 사용시: 각 노드에 parent 필드 추가
순차 표현 사용시: 위치 i의 부모노드는 i / 2 최대 히프에서의 삽입 알고리즘 insertHeap(Heap,item) // 순차 표현으로 구현된 최대 히프 // 원소 e를 히프 Heap에 삽입, n은 현재 히프의 크기(원소 수) if (n = heapSize) then heapFull; // 히프가 만원이면 히프 크기를 확장 n ← n+1; // 새로 첨가될 노드 위치 for (i←n; ; ) do { if (i = 1) then exit; // 루트에 삽입 if(item ≤ heap[⌊i/2⌋]) then exit; // 삽입할 노드의 키값과 // 부모 노드 키값을 비교 heap[i] ← heap[⌊i/2⌋]; // 부모 노드 키값을 자식노드로 이동 i ← ⌊i/2⌋; } heap[i] ← item; end insertHeap()

히프 (8) 히프에서의 삭제 루트 원소를 삭제 나머지 트리가 다시 히프가 되도록 재조정

히프 (9) 첫 번째 삭제 예 (루트 키값 19) 두번째 삭제 예 (루트 키값 18) 히프의 예 (그림 (a))
루트 원소 19의 삭제후 구조 (그림 (b)) 위치 6의 노드를 삭제하고 키값 5를 루트로 이동 (그림 (c)) 이 이동 원소값을 두 자식 노드 중에서 큰 원소값과 비교 비교 결과 자식 노드 원소값이 크면 그 값을 부모 노드로 옮긴 다음 이동 원소가 그 자식 노드로 내려가서 다시 히프 검사 만일 자식 노드 원소보다 크면 삭제 연산 종료 이 예의 경우, 5와 18 교환후 종료 (그림 (d)) 두번째 삭제 예 (루트 키값 18) 삭제(루트 18)후 구조 (그림 (e)) 위치 5의 노드를 삭제하고 키값 8을 루트로 이동 (그림 (f)) 이 예의 경우, 8과 13, 다시 8과 12 교환후 종료 (그림 (g), (h))

히프 (10)

히프 (11) 히프에서의 삭제 알고리즘 deleteHeap(heap)
// 히프로부터 원소 삭제, n은 현재의 히프 크기(원소 수) if (n=0) then return error; // 공백 히프 item ← heap[1]; // 삭제할 원소 temp ← heap[n]; // 이동시킬 원소 n ← n-1; // 히프 크기(원소 수)를 하나 감소 i ← 1; j ← 2; // j는 i의 왼쪽 자식 노드 while (j ≤ n) do { if (j < n) then if (heap[j] < heap[j+1]) then j ← j+1; // j는 값이 큰 자식을 가리킨다. if (temp ≥ heap[j]) then exit; heap[i] ← heap[j]; // 자식을 한 레벨 위로 이동 i ← j; j ← j*2; // i와 j를 한 레벨 아래로 이동 } heap[i] ← temp; return item; end deleteHeap()

히프 (12) 완전 이진 트리를 히프로 변환 초기에 히프로 되어 있지 않은 완전이원트리 H를 히프로 변환
완전 이원트리를 히프로 변환하는 알고리즘 makeTreeHeap(H, n) // H는 히프가 아닌 완전 이진 트리 for (i ← n/2; i ≥ 1; i ← i-1) do { // 각 내부 노드에 대해 레벨 순서의 역으로 p ← i; for (j ← 2*p; j ≤ n; j ← 2*j) do { if (j < n) then if (H[j] < H[j+1]) then j ← j+1; if (H[p] ≥ H[j]) exit; H[p] ← H[j]; p ← j; // 부모 노드를 한 레벨 밑으로 이동 } H[p] ← H[i]; } end makeTreeHeap()

히프 (13) 변환예 히프가 아닌 완전 이진 트리 내부 노드의 역레벨순서: 5, 4, 3, 2, 1
5번 노드를 루트로 하는 서브 트리에서 히프 연산 시작 이 노드는 루트보다 키값(60)이 큰 자식을 가지므로 교환(3060) 다음으로 4번 노드를 루트로 하는 서브 트리 조사 자식 중에 큰 키값(90)을 루트의 키값과 교환(70  90)

히프 (14) 다음으로 3번 노드를 루트로 하는 서브 트리 조사 노드6과 노드 3과의 큰 키값 교환(50  100)
여기까지의 과정에서 얻어진 트리

히프 (15) 다음으로 2번 노드를 루트로 하는 서브트리 조사 키값 40을 왼쪽 자식의 키값(90)과 교환(40  90)
다시 계속해서 9번 노드의 키값(70)과 교환(40  70) 이 결과로 얻어진 이진 트리

히프 (16) 끝으로 역레벨순서 마지막 노드인 루트 노드(1번 노드)를 고려
이 루트 노드는 먼저 3번 노드의 키값(100)과 교환(20  100) 다시 계속해서 7번 노드의 키값(80)과 교환(20  80) 최종 히프 구조

히프 (17) 히프로 우선 순위큐 표현 히프는 우선 순위큐 표현에 효과적
우선 순위가 제일 높은 원소를 찾거나 삭제하는 것은 아주 쉬움 노드 삭제시: 나머지 노드들을 다시 히프가 되도록 재조정 노드 삽입시: 삽입할 원소의 우선 순위에 따라 히프가 유지되도록 해야 됨 5.7.1절의 우선순위큐 정렬: O(n2) 히프정렬: O(nlog n)

히프 (18) 프로그램 #include<stdio.h> typedef struct { // 큐의 원소 타입
int key; // 우선순위 키 값을 표현 char name[10]; char grade; } element; typedef struct { int length; // 실제로 우선순위 큐에 저장되어 있는 원소 수 int qSize; // 배열의 크기: 실제 최대 원소 수는 qSize-1 int increment; // 배열 확장 단위 int *data; // 우선순위 큐의 원소를 저장하는 배열 // 실제 원소는 data[1], data[2], data[qSize]에 저장 } priorityQ; int currentLength(priorityQ* pQ) { // 우선순위 큐의 현재 원소 수 return pQ->length; }

히프 (19) void queueFull(priorityQ* pQ) {
// data[]가 만원이면 increment만큼 더 확장 int i; int* temp; pQ->qSize += pQ->increment; temp = (int*)malloc((pQ->qSize)*sizeof(int)); for (i=1; i < pQ->length; i++) { temp[i] = pQ->data[i]; } free(pQ->data); pQ->data = temp; } int delete(priorityQ* pQ) { // 우선순위가 제일 높은 원소를 삭제 int currentLoc; int childLoc; int itemToMove; // 이동시킬 원소 int deletedItem; // 삭제한 원소 if (pQ->length == 0) { // 우선순위 큐가 공백인 경우 printf("Queue is empty\n"); exit(1); }

히프 (20) else { deletedItem = pQ->data[1]; // 삭제하여 반환할 원소
itemToMove = pQ->data[(pQ->length)--]; // 이동시킬 원소 currentLoc = 1; childLoc = 2*currentLoc; while (childLoc <= pQ->length) { // 이동시킬 원소의 탐색 if (childLoc < pQ->length) { if (pQ->data[childLoc+1] > pQ->data[childLoc]) childLoc++; } if (pQ->data[childLoc] > itemToMove) { // 원소를 한 레벨 위로 이동 pQ->data[currentLoc] = pQ->data[childLoc]; currentLoc = childLoc; childLoc = 2*currentLoc; } else { // 이동시킬 원소 저장 pQ->data[currentLoc] = itemToMove; return deletedItem; } pQ->data[currentLoc] = itemToMove; // 최종 위치에 원소 저장 return deletedItem; } }

히프 (21) void insert(priorityQ* pQ, int item) { // 히프로 구현된 우선순위 큐에 원소 삽입 if (pQ->length == pQ->qSize - 1) queueFull(pQ); // 큐가 만원이면 먼저 큐를 확장 pQ->length++; // 삽입공간을 확보하고 원소의 삽입위치를 밑에서부터 찾아 올라감 int childLoc = pQ->length; int parentLoc = childLoc/2; while (parentLoc != 0) { if (item <= pQ->data[parentLoc]) { // 위치가 올바른 경우에 원소 삽입 pQ->data[childLoc] = item; return; } else { /* 한 레벨 위로 이동 */ pQ->data[childLoc] = pQ->data[parentLoc]; childLoc = parentLoc; parentLoc = childLoc/2; } pQ->data[childLoc] = item; /* 최종 위치에 원소 삽입 */ }

히프 (22) void priorityQsort(priorityQ* pQ, int* a, int n) {
int i; for (i = 1; i < n; i++) { // 배열 a[]의 원소를 우선순위 큐 pQ에 전부 삽입 insert(pQ, a[i]); } for (i = n-1; i > 0; i--) { // 우선순위가 큰 원소가 인덱스가 크게 저장 a[i] = delete(pQ); priorityQ* createPriorityQ(void) { // 공백 우선순위 큐의 생성 priorityQ* pQ; pQ = (priorityQ*)malloc(sizeof(priorityQ)); pQ->length = 0; pQ->qSize = 16; // 실제 최대 원소 수는 qSize-1 pQ->increment = 8; pQ->data = (int*)malloc(pQ->qSize*sizeof(int)); /* 우선순위 큐를 배열로 표현하는 히프로 구현하기 때문에 */ /* data[0]는 인덱스가 0이 되어 실제로 사용하지 않음 */ return pQ;

히프 (23) void freeQueue(priorityQ* pQ) { // 우선순위 큐에 할당된 메모리를 반환
free(pQ->data); free(pQ); } int main() { // 예제 실행을 위한 main() 함수 int input[] = {100, 30, 50, 120, 340, 200, 10}; int n = 8; /* 정렬할 원소 수 +1 */ int i; int* a = (int*)malloc(8*sizeof(int)); priorityQ* pQ; pQ = createPriorityQ(); printf("Initial Input Values : "); for (i = 1; i < n; i++) { // 원소를 배열 a[]에 저장하고 프린트 a[i] = input[i-1]; // a[0]는 인덱스가 0이기 때문에 원소를 저장하지 않음 printf("%5d", a[i]); printf("\n"); priorityQsort(pQ, a, n); // 배열 a[]의 원소를 우선순위 큐 pQ를 이용하여 정렬 */ for (i = 1; i < n; i++) { // 정렬된 배열 a[]의 원소를 오름차순으로 프린트 free(a); // 배열 a[]에 할당된 메모리를 반환 freeQueue(pQ); // 우선순위 큐에 할당된 메모리를 반환 return 0;

선택 트리 (1) 개요 k개의 런에 나뉘어져 있는 n개의 원소들을 하나의 순서순차로 합병하는 경우 선택트리의 종류
런(run): 원소들이 정렬되어 있는 순서순차(ordered sequence) 각 런은 키(key)값에 따라 원소들을 오름차순으로 정렬 K개의 런 중에서 가장 작은 키값을 가진 원소를 계속적으로 순서순차로 출력 k개의 원소 중에서 가장 작은 키 값을 가진 원소를 선택: k-1번 비교 선택 트리(selection tree) 자료 구조 이용시: 비교횟수 줄임 선택트리의 종류 승자트리 패자트리

선택 트리 (2) 승자 트리(winner tree) 특징 런이 8개(k=8)인 경우 승자 트리 예 완전 이원트리
각 단말 노드는 각 런의 최소키 값 원소를 나타냄 내부 노드는 그의 두 자식 중에서 가장 작은 키 값을 가진 원소를 나타냄 런이 8개(k=8)인 경우 승자 트리 예

선택 트리 (3) 승자 트리 구축 과정 승자 트리의 표현 합병의 진행
가장 작은 키 값을 가진 원소가 승자로 올라가는 토너먼트 경기로 표현 트리의 각 내부 노드: 두 자식 노드 원소의 토너먼트 승자 루트 노드: 전체 토너먼트 승자, 즉 트리에서 가장 작은 키 값 가진 원소 승자 트리의 표현 승자트리는 완전 이원트리이기 때문에 순차 표현이 유리 인덱스 값이 i인 노드의 두 자식 인덱스는 2i와 2i+1 합병의 진행 루트가 결정되는 대로 순서순차에 출력 (여기선 7) 다음 원소 즉 키값이 13인 원소가 승자트리로 들어감 승자 트리를 다시 재구성 노드 11에서부터 루트까지의 경로를 따라가면서 형제 노드간 토너먼트 진행

선택 트리 (4) 다시 만들어진 승자트리의 예 이런 방식으로 순서 순차구축을 계속함

선택 트리 (5) 패자 트리(loser tree) 루트 위에 0번 노드가 추가된 완전 이원트리 성질
(1) 단말노드 :각 런의 최소 키값을 가진 원소 (2) 내부 노드 : 토너먼트의 승자대신 패자 원소 (3) 루트(1번 노드) : 결승 토너먼트의 패자 (4) 0번 노드 : 전체 승자(루트 위에 별도로 위치)

선택 트리 (6) 런이 8개(k=8)인 패자 트리의 예 23

선택 트리 (7) 패자 트리 구축 과정 합병의 진행 단말 노드: 각 런의 최소 키값 원소 내부 노드 1번 루트 노드
두 자식 노드들이 부모노드에서 토너먼트 경기를 수행 패자는 부모 노드에 남음 승자는 그 위 부모 노드로 올라가서 다시 토너먼트 경기를 계속 1번 루트 노드 마찬가지로 패자는 1번 루트 노드에 남음 승자는 전체 토너먼트의 승자로서 0번 노드로 올라가 순서순차에 출력됨 합병의 진행 출력된 원소가 속한 런 4의 다음 원소, 즉 키값이 13인 원소를 패자트리 노드 11에 삽입 패자 트리를 다시 재구성 토너먼트는 노드 11에서부터 루트 노드 1까지의 경로를 따라 경기를 진행 다만 경기는 형제 노드 대신 형식상 부모 노드와 경기를 함

선택 트리 (8) 모든 원소가 순서 순차에 출력될 때까지 이 과정을 반복 다시 만들어진 패자 트리의 예 10 13 11 21
4 18 50 6 9 15 5 7 3 2 1 8 12 14 16 런 22 28 24 26 30 20 52 59 19 출력 23

7장 이원 탐색 트리.

Similar presentations

Presentation on theme: "7장 이원 탐색 트리."— Presentation transcript:

Similar presentations

About project

지원

로그인

Auth with social network:

7장 이원 탐색 트리.

Similar presentations

Presentation on theme: "7장 이원 탐색 트리."— Presentation transcript:

Similar presentations

About project

지원