5장 - Heaps

Heap

• 최대 트리(max tree): 트리의 모든 노드에 대해 부모 데이터 값>자식 데이터 값
• 최대 힙(max heap): 최대 트리이면서 완전 이진 트리

 

• 최소 트리(min tree): 트리의 모든 노드에 대해 부모 데이터 값<자식 데이터 값
• 최소 힙(min heap): 최소 트리이면서 완전 이진 트리

 

우선 순위 큐(Priority Queues)

선입 선출이 아니라 우선순위의 순서대로 삭제되는 큐

 

우선순위 큐의 다양한 구현 방법들과 삽입,삭제시 시간복잡도

구현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
최대 힙	O(log2n)	O(log2n)

(숫자2는 로그의 밑임)

---

Max Heap 구현하기

Max Heap은 배열로 구현하는 것이 효과적이다.

완전 이진 트리이므로 인덱스를 사용하여 접근하는 것이 용이하기 때문임.

 

자료구조 선언

#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n==MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)

typedef struct {
	int key;
}element;
element heap[MAX_ELEMENTS];
int n = 0;

 

insert

void insert_max_heap(element item, int* n) {
	int i;
	if (HEAP_FULL(*n)) {
		fprintf(stderr, "THE HEAP IS FULL. \n");
		exit(1);
	}
	i = ++(*n);
	while ((i != 1) && (item.key > heap[i / 2].key)) {
		heap[i] = heap[i / 2];
	}
	heap[i] = item;
	
}

배열의 끝에 새로운 노드를 추가한다.==> ++(*n)

추가된 위치부터 parent노드를 한 단계씩 조사한다. 부모보다 값이 크다면 자리를 바꾸고, 부모보다 값이 작아지거나 root가 될 때까지 반복한다.

delete

element delete_max_heap(int* n) {
	int parent, child;
	element item, temp;

	if (HEAP_EMPTY(*n)) {
		fprintf(stderr, "THE HEAP IS EMPTY.\n");
		exit(1);
	}
	item = heap[1];//현재 루트의 값을 옮겨놓음
	temp = heap[(*n)--]; //제일 마지막 원소를 비교 대상으로 temp에 넣음
	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;

}

루트노드의 값을 빼내고, 제일 마지막 노드를 넣는다. 

자식보다 값이 클 때까지 한 칸씩 내린다.

---

이진 검색 트리

Heap에서 특정 데이터를 갖는 노드를 검색할 때, 시간복잡도는 O(n)이 된다.

이진 검색 트리는 트리 내에서 특정 데이터를 효율적으로 찾도록 한다.

• 모든 노드는 유일한 키 값을 가진다.
• 왼쪽 서브트리에 저장된 키 값<Root node 키 값 < 오른쪽 서브트리에 저장된 키 값
• 왼쪽/오른쪽 서브트리도 이진 검색 트리이다.

 

이진 검색 트리에서 검색 연산

• if (key==root->key) return (root)
• if (key < root->key) search(root->left_child)
• if (key > root->key) search(root->right_child)

이진 검색 트리는 완전이진트리가 아니므로 배열이 아닌 연결리스트로 구현하게 된다.

 

#include <stdio.h>
#include <stdlib.h>

struct node {
	int data;
	struct node* left_child;
	struct node* right_child;
};

노드는 left_child,right_child, data로 구성됨

 

recursive search

struct node* search(struct node* root, int key) {
	//key를 포함하고 있는 노드의 포인터를 return. 없는경우 NULL리턴
	if (!root) return NULL;
	if (key == root->data) return root;
	if (key < root->data)
		return search(root->left_child, key);
	return search(root->right_child, key);
}

iterative search

struct node* iterSearch(struct node* tree, int key) {
	while (tree != NULL) {
		if (key == tree->data) return tree;
		if (key < tree->data)
			tree = tree->left_child;
		else
			tree = tree->right_child;

	}
	return NULL;
}

재귀가 아닌 반복문으로 구현도 가능하다.

 

 

이진 검색 트리에 노드 추가하기

검색 알고리즘을 수행 후, 알고리즘이 종료되는 곳에 새로운 노드를 추가하면 된다.

struct node* modified_search(struct node* root, int key) {
	for (struct node* ptr = root; ptr != NULL;) {
		if (ptr->data == key)//기존에 존재하는 키를 입력하면 NULL리턴
			return NULL;
		if (key < ptr->data) {
			if (ptr->left_child == NULL) return ptr;//새 노드를 넣을 자리
			else ptr = ptr->left_child;//한칸더 내려감
		}
		else {
			if (ptr->right_child == NULL) return ptr;
			else ptr = ptr->right_child;
		}
	}
	return NULL;//root가 NULL인 경우
}

void insert_node(struct node** root, int num) {
	struct node* ptr, *parent = modified_search(*root, num);

	if (parent || !(*root)) {
		ptr = (struct node*)malloc(sizeof(struct node));//num을 키값으로하는 노드생성
		ptr->data = num;
		ptr->left_child = ptr->right_child = NULL;

		if (*root)//root!=NULL일 때, 부모노드와 새로 생성한 노드를 연결시킴
			if (num < parent->data)
				parent->left_child = ptr;
			else
				parent->right_child = ptr;
		else *root = ptr; //트리가 empty인 경우 root로 등록
	}
}

modify_search(struct node* root, int key)는 새 노드가 들어갈 위치를 찾아, 그 위치의 부모노드를 반환하는 함수이다.

insert_node(struct node** root,int num)는 num값을 키값으로 갖는 새 노드를 만들어 적절한 위치에 해당노드를 삽입한다.

 

이진 검색 트리에서 노드 삭제

리프노드인 경우: 간단히 해당노드 삭제 

child가 하나인 노드: 삭제된 자리에 child node를 위치

두 개의 children을 갖는 노드: 왼쪽 서브트리에서 가장 큰 노드나, 오른쪽 서브트리에서 가장 작은 노드를 삭제된 자리에 위치시킴

 

이진검색트리를 inorder traversal하면 크기순으로 찍힌다.

이진검색트리는 O(log2n) 시간복잡도임