[자료구조] 힙(Heaps)

if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.

 

우선순위 큐(Priority Queue)

- 우선 순위가 가장 높은/낮은 원소를 먼저 삭제

- 임의의 우선순위를 가진 원소 삽입 가능

- 추상 데이터 타입 MaxPriorityQueue

 

무순서(unordered): 선형 리스트로 구현(가장 간단)

- IsEmpty() : O(1) // linked list가 null인지 검사

- push(): O(1) //임의의 위치에 노드 삽입

- top(): Θ(n) //list 전체 검사(n개 노드)

- pop() : Θ(n) // top()을 검사 후 삭제(n개 노드)

 

최대 힙(max heap)으로 구현

- IsEmpty: O(1)

- top() : O(1)

- push() - O(log n)

- pop : O(log n)

 

최대 힙의 정의(def.)

최대/최소 트리: 각 노드의 키 값이 그 자식의 키 값보다 작지(크지) 않은 트리.

최대 힙: 최대 트리이면서 완전 이진 트리

최소 힙: 최소 트리이면서 완전 이진 트리

 

최대 힙에서의 삽입(Insertion)

- 삽입 후에도 최대 힙 유지: push()

새로 삽입된 원소는 부모 원소와 비교하면서 최대 힙이 되는 것이 확인될 때까지 위로 올라감

void push(element item, int *n)
{
	int i;
    if(HEAP_FULL(*n)){
    	fprintf(stderr, "The heap is Full. \n");
        exit(EXIT_FAILURE);
    }
	i = ++(*n);
    while((i != 1) && (item.key > heap[i/2].key)){
    	heap[i] = heap[i/2];
        i /=2;
    }
    heap[i] = item;
}

 

최대 힙에서의 삭제(Deletion)

루트 삭제: pop()

루트와 마지막 위치의 노드 교환 후 완전 이진 트리로 재구성.

루트와 왼쪽 자식, 오른쪽 자식을 비교하여 가장 큰 것을 루트로.

element pop(int *n)
{
	int parent, child;
    element item, temp;
    if(HEAP_EMPTY(*n)){
    	fprintf(stderr, "The heap is empty\n");
        exit(EXIT_FAILURE);
    }
    item = heap[1];
    temp = heap[(*n)--];
    parent = 1;
    child = 2;
    while(child <= *n){
    	if(child < *n) && (heap[child].key < heap[child+1].key) child++;
        if(temp.key >= heap[child].key) break;
        heap[parent] = heap[child];
        parent = child;
        child *=2;
    }
    heap[parent] = temp;
    return item;
}

 

이원 탐색 트리(Binary Search Tree)

정의: pair<키, 원소>의 집합

 

이원 탐색 트리는 공백 가능하고, 만약 공백이 아니라면

1) 모든 원소는 서로 다른 키를 갖는다.

2) 왼쪽 서브트리의 키들은 그 루트의 키보다 작다

3) 오른쪽 서브트리의 키들은 그 루트의 키보다 크다.

4) 왼쪽과 오른쪽 서브트리도 이원 탐색 트리이다.(재귀적 정의)

Binary는 맞으나 complete나 search Tree는 아님.

 

이원 탐색 트리의 탐색

- k = 루트의 key: 성공적 종료

- k < 루트의 key: 왼쪽 서브트리 탐색

- k > 루트의 key: 오른쪽 서브트리 탐색

element* search(treePointer tree, int key)
{
	if(!tree) return NULL;
    if(key == tree->data) return tree;
    if(key < tree->data) return search(tree->left_child, key);
    return search(tree->right_child, key);
}

//반복적 탐색
treePointer iterSearch(treePointer tree, int key)
{
	while(tree) {
    	if(key == tree->data) return tree;
        if(key < tree->data) tree = tree->left_child;
        else tree = tree->right_child;
    }
    return NULL;
}

 

이원 탐색 트리에서의 삽입

- x의 key값을 가진 노드를 탐색

- 탐색이 성공하면 이 키에 연관된 원소를 변경: pair(key, data)

- 탐색이 실패하면 탐색이 끝난 지점에 삽입

void insert (treePointer *node, int k, iType theItem)
{ 
	/* 트리내의 노드가 k를 가리키고 있으면 아무 일도 하지 않음;
    그렇지 않은 경우는 data=(k, theItem)인 새 노드를 첨가 */
    
    treePointer ptr, temp = modifiedSearch(*node, k);
    if(temp || !(*node)) {
        /* k is not in the tree */
        MALLOC(ptr, sizeof(*ptr));
        ptr->data.key = k;
        ptr->data.item = theItem;
        ptr->leftChild = ptr->rightChild = NULL;
        if(*node) /* insert as child of temp */
            if(k<temp->data.key) temp->leftChild = ptr;
            else temp->rightChild = ptr;
        else *node = ptr;
    }
}

 

이원탐색 트리에서의 삭제

- 리프 원소의 삭제: 부모의 자식 필드에 0을 삽입, 삭제된 노드 반환

- 하나의 자식을 가진 비리프 노드의 삭제: 삭제된 노드의 자식을 삭제된 노드의 자리에 위치

- 두개의 자식을 가진 비리프 노드의 삭제: 왼쪽 서브트리에서 가장 큰 원소나 오른쪽 서브트리에서 가장 작은 원소로 대체

 

이원 탐색 트리의 조인과 분할

threeWayJoin(small, mid, big)

-이원 탐색 트리 small과 big에 있는 쌍들과 쌍 mid로 구성되는 이원 탐색 트리를 생성

- 새로운 노드를 하나 얻어서

• 데이터 필드 = mid
• 왼쪽 자식 = small.root
• 오른쪽 자식 = big.root

-O(1)

 

twoWayJoin(small, big)

-이원 탐색 트리 small과 big에 있는 쌍들을 포함하는 이원 탐색 트리를 생성

- small이나 big이 공백인 경우, 공백이 아닌 것이 이원 탐색 트리

- 둘다 공백이 아니면

• small에서 가장 큰 키 값을 가진 mid 쌍 삭제
• ThreeWayJoin(small, mid, big) 수행

- O(height(small)

 

split(k, small, mid, big)

- 이원 탐색 트리 *theTree를 세 부분으로 분할

- small 은 *theTree의 원소 중 키 값이 k보다 작은 모든 쌍 포함

- mid 은 *theTree의 원소 중 키 값이 k보다 같은 모든 쌍 포함

- big 은 *theTree의 원소 중 키 값이 k보다 큰 모든 쌍 포함

 

- k = root->data.key인 경우(=key)

• small = *theTree의 왼쪽 서브트리
• mid = 루트에 있는 쌍
• big = *theTree의 오른쪽 서브 트리

- k<root->data.key인 경우

• big ⊇ 루트, 오른쪽 서브 트리

 

- k> root->data.key인 경우

• big ⊇ 루트, 왼쪽 서브 트리

void split (nodePointer *theTree, int k, nodePinter *small, element *mid, nodePointer *big)
{/* split the binary search tree with respect to key k */
    if (!theTree) {
    	*small = *big = 0;
    	(*mid).key = -1; return ; /* empty tree */
    }
        
    nodePointer sHead, bHead, s, b, currentNode;
    
    /* create header nodes for small and big */
    MALLOC(sHead, sizeof(*sHead));
    MALLOC(BHead, sizeof(*bHead));
    s = sHead; b = bHead;
    
    /*do the split */
    currentNode = *theTree;
    while (currentNode){
        if(k < currentNode->data.key){ //big에 추가
            b->leftChild = currentNode;
            b = currentNode; currentNode = currentNode->leftChild;
        }
        else if (k > currentNode->data.key){ //small에 추가
            s->rightChild = currentNode;
            s = currentNode; currentNode = currentNode->rightChild;
        }
        else { //현재 노드에서 split
            s->rightChild = currentNode->leftChild;
            b->leftChild = currentNode->rightChild;
            *small = sHead->rightChild; free(sHead);
            *big = bHead->leftChild; free(bHead);
            (*mid).item = currentNode->data.item;
            (*mid).key = currentNode->data.key;
            free(currentNode);
            return;
        }
    }
    /* no pair with key k */
    s->rightChild = b->leftChild = 0;
    *small = sHead->rightChild; free(sHead);
    *big = bHead->leftChild; free(bHead);
    (*mid).key = -1;
    return;
}

 

 

이원 탐색 트리(n)의 높이 =>탐색 시간과 관련

원소 수: n

최악의 경우: 높이 n

평균 O(log n)

균형 탐색 트리(balanced search tree)

- 최악의 경우에도 높이가 O(log n)이 되는 트리

- 탐색/삽입/삭제의 시간 복잡도: O(h) = O(log n)

- AVL, 2-3, 2-3-4, 레드-블랙, B트리, B+트리 등

 

 

선택 트리(Selection Trees)

: 단말 노드부터 시작해서, 큰 값 또는 작은 값을 찾아 부모로 올려서 root에 가장 큰/작은 값을 올리는 방식

Complete Binary Tree이다.

승자트리, 패자트리, 토너먼트 트리 등

 

run: 합병될 k개의 순서 순차(single ordered sequence)

각 런은 key 필드에 다라 비감소 순서로 정렬

 

merge(합병)

- 정렬된 데이터 리스트 k개를 하나의 리스트로 만드는 과정

- 일반적으로 데이터 리스트가 k개인 경우 k-1번 비교

- 선택 트리를 이용하여 비교 횟수를 줄일 수 있음

 

승자 트리(winner trees)

- 각 노드가 자식 노드 중 더 작은 노드를 나타내는 완전 이진 트리

- 루트 노드: 트리에서 가장 작은 노드

- 리프 노드: 각 런의 첫 번째 레코드(data)

- 비리프 노드: 토너먼트의 승자

- 이진 트리에 대한 순차 할당 기법으로 표현

 

문제점

- 재구성 할 때 루트가지의 경로를 따라 형제 노드들 사이에 토너먼트 발생

- 형제 노드는 전에 시행되었던 토너먼트의 패자들

 

패자 트리(loser tree)

- 비리프 노드가 패자 레코드에 대한 포인터 유지

- 전체 토너먼트의 승자를 표현하기 위한 노드 0 첨가

- 토너먼트는 부모와 비교

- 형제 노드에는 접근하지 않음

 

포리스트(Forest)

:  n(>=0)개의 분리(disjoint) 트리(tree)들의 집합

 

포리스트를 이진 트리로 변환

- 각 트리를 이진 트리로 변환

- 변환된 모든 이진 트리들을 루트의 rightChild로 연결

 

정의: T1,T2,... Tn 트리로 구성된 포리스트에 대응하는 이진 트리, B(T1,T2...Tn)은

1) n=0이면 공백

2) B의 루트 = T1의 루트

-왼쪽 서브트리=B(T11,T12,...T1m), T11~T1m는 T1의 루트의 서브트리

-오른쪽 서브트리 = B(T2,...Tn)

 

포리스트 순회

포리스트 전위(forest preorder)

-F가 공백이면 복귀

-F의 첫번째 트리의 루트 방문

-첫 번째 트리의 서브트리들을 포리스트 전위 순회

-F의 나머지 트리들을 포리스트 전위로 순회

 

포리스트 중위(forest inorder)

-F가 공백이면 복귀

-F의 첫번째 트리의 서브트리를 포리스트 중위로 순회

-첫번째 트리의 루트 방문

-나머지 트리들을 포리스트 중위로 순회

 

포리스트 후위(forest postorder)

- F가 공백이면 귀환

-F의 첫 트리의 서브트리를 포리스트 후위로 순회

- 나머지 트리들을 포리스트 후위로 순회

- F의 첫 트리의 루트를 방문

 

포리스트 레벨 순서 순회(level order traversal)

-포리스트의 가 루트부터 시작, 레벨 순으로 방문

-레벨 내에서는 왼쪽에서 오른쪽으로 차례로 방문

 

 

이진 트리의 개수 계산(Counting Binary Trees)

상이한 이진 트리

- n=2일 때 서로 다른 이진 트리는 2개

- n=3일 때 서로 다른 이진 트리는 5개

-일반화하면 n개의 노드를 가진 서로 다른 이진 트리의 개수는 bn = (2n)!/n!(n+1)!

 

스택 순열

-전위 순열: 이진 트리를 전위 순회에 따라 방문한 노드들의 순서

-중위 순열: 이진 트리를 중위 순회에 따라 방문한 노드들의 순서

모든 이진트리는 유일한 전위-중위 순서 상을 가짐

 

stack operations

-push(): 빈 노드를 만들고 왼쪽으로

- pop(): 빈 노드에 값을 채우고 오른쪽으로.

 

행렬 곱셈(Matrix Multiplcation)

n개 행렬을 곱하는 방법의 수 bn = Σb_i*b_(n-i), n>1

b_n이 n개의 노드를 가진 서로 다른 이진 트리의 수라고 하면

- 루트, 노드 수가 b_i, b_(n-i-1)인 서브트리로 된 이진트리들

 

상이한 이진 트리의 수

(엄청 복잡하므로 생략..?)