Dog foot print

[DataStructure] max heap tree 삽입과 삭제 본문

C-language

[DataStructure] max heap tree 삽입과 삭제

개 발자국 2019. 10. 17. 21:58

시험 기간때문에 개인 프로젝트나, 포스팅이 전부 올 스탑이다. 적어도 이번 학기는 이런 상태가 지속 될 것 같아 걱정이다.

 

교수님이 주신 두번 째 과제는 max_heap_tree를 만들어 삭제와 삽입을 가능케 하는 것이다. 물론 배열이 아닌 연결리스트로 구현하라고 했기에 약간의 어려움이 존재하였다.  

 

max_heap_tree 는 가장 최대값을 우선순위로 하여, 삽입시 O(logn) , 삭제시 O(logn)의 시간 복잡도를 가지게 되는 자료구조입니다. 

 

max_heap_tree의 자세한 내용은 다음 링크 를 따라가셔서 확인하시도록 하세요. 

 

데이터 구조체

heapType

 

제 heap_tree는 nodeType을 가지고 있는 rootNode 필드가 있고, 삽입시 마지막 레벨 - 1 중 아직 다 채워지지 않은 노드를 빨리 찾기 위해 queue 필드가 있으며, 삭제 및 삽입시 log(1)의 시간으로 마지막 노드를 찾기위해 stack링크를 두었습니다.

 

nodeType

 

nodeType은 각각의 노드를 표현하기 위한 타입으로써 숫자를 가지고 있는 data 필드,  왼쪽과 오른쪽 자식 노드를 가리키는 left, right노드  , 삽입 및 삭제를 위한 parents 필드 , queue를 만들기 위한 queueLink,  삭제 될 순서대로 연결된 stackLink필드가 있습니다.

 

코드

 

typedef struct node{
	int data;
	struct node* left;
	struct node* right;
	struct node* parent;
	struct node* queueLink;
	struct node* stackLink;
}node;

typedef struct heapType{
	struct node* root;
	struct node* queue;
	struct node* stack;
	struct node* lastDeletedNode;
}heapType;

 

삽입

 

 

삽입 연산은 큐를 이용해야 하는데 ,먼저 heaptype의 queue필드가 가리키고 있는 노드의 자식노드를 검사한 뒤 왼쪽 자식이 없다면, 해당 노드의 왼쪽 자식링크에 새로운 노드를 연결시켜준다. 만약 노드의 왼쪽 자식 노드가 있고 , 오른쪽 자식 노드가 없다면 해당 노드의 오른쪽 자식 링크필드에 새로운 노드를 입력한다. 만약 둘다 노드가 존재한다면 heap type -> queue = heaptype -> queue -> quelink 로 다음 링크필드를 가리 킬수 있도록 한다. 

 

void insertNode(heapType* heap ,int data) {
	
	node * newNode = (node *)malloc(sizeof(node));

	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
	newNode->parent = NULL;
	newNode->queueLink = NULL;
	newNode->stackLink = NULL;
	node *sp = heap->stack;
	if (!(heap->root)) {
		heap->root = newNode;
		heap->queue = newNode;
		heap->stack = newNode;
		heap->lastDeletedNode = NULL;
	}
	else {
		if (!(heap->queue->left)) {
			heap->queue->left = newNode;
			newNode->parent = heap->queue;
			
			compareWithParents(newNode);

			newNode->stackLink = heap->stack;
			heap->stack->queueLink = newNode;
			heap->stack = newNode;
			
		}
		else if (heap->queue->right == NULL && heap->queue->left != NULL) {
			heap->queue->right = newNode;
			newNode->parent = heap->queue;

			compareWithParents(newNode);

			newNode->stackLink = heap->stack;
			heap->stack->queueLink = newNode;
			heap->stack = newNode;
		}
		else if ((heap->queue->left) && (heap->queue->right)) {
			heap->queue = heap->queue->queueLink;

			heap->queue->left = newNode;
			newNode->parent = heap->queue;

			compareWithParents(newNode);

			newNode->stackLink = heap->stack;
			heap->stack->queueLink = newNode;
			heap->stack = newNode;
		}
	}
}

 

힙트리의 삽입은 완전이진트리에 맞게 삽입되기 때문에 새롭게 생성된 노드는 우선순위가 부모보다 높을수도 낮을수도 있다. 이를 교정하기위하여 새롭게 생성된 노드와 부모노드의 우선순위를 비교하며 자식노드가 부모노드보다 우선순위가 높지 않도록 데이터를 스왑하는 과정을 거쳐야한다. 

 

void compareWithParents(node *newNode) {
	node * tempPointer = newNode;
	while (tempPointer->parent != NULL && tempPointer->data > tempPointer->parent->data) {
		int temp;
		temp = tempPointer->data;
		tempPointer->data = tempPointer->parent->data;
		tempPointer->parent->data = temp;
		tempPointer = tempPointer->parent;
	}
}

 

삭제

 

삭제는 tree의 root노드가 삭제되며, 마지막에 삽입되었던 노드가 root노드로 이동해야 한다. 그러나 실제로 노드를 이동 시키는 행위는 끊어진 필드를 전부 다시 연결해야하는 번거로움이 있어, 실제로는 마지막으로 삽입되었던 노드의 데이터만 root노드로 옮기는 작업을 하고 필드를 변경하는 작업은 마지막 노드에서만 이루어진다. 해주어야 하는 작업은 다음과 같다.

 

1. heaptype의 queue필드의 끝을 마지막으로 삽입 된 노드보다 먼저 삽입된 노드로 변경한다.

 

2. heaptype의 stack필드의 포인터를 한칸 옮긴다.

 

3. 마지막으로 삽입된 노드의 부모노드와 edge를 해제한다. 

 

4. free함수로 메모리영역을 해제한다. 

 

int deleteNode(heapType* heap) {
	
	int rootNodeData = heap->root->data;
	int lastInsertedNodeData = heap->stack->data;

	heap->root->data = lastInsertedNodeData;

	node * temp = heap->stack;
	heap->stack = heap->stack->stackLink;
	heap->stack->queueLink = NULL;
	
	if (temp->parent->right == temp) {
		temp->parent->right = NULL;
	}
	else {
		temp->parent->left = NULL;
	}
	free(temp);

	compareWithChilde(heap->root);

	return rootNodeData;
}

heapType * resetHeapType(heapType * heap) {
	heapType * newHeap = (heapType *)malloc(sizeof(heapType));
	newHeap->root = NULL;
	newHeap->queue = NULL;
	newHeap->stack = NULL;
	newHeap->lastDeletedNode = NULL;

	return newHeap;
}

 

삭제 연산에서 root로 옮겨진 데이터는 가장 우선순위가 낮을 것이다. 그렇기에 자식노드들과 비교하며 우선순위를 재조정 하는 작업을 거쳐야 한다. 

 

void compareWithChilde(node * root) {
	int temp;
	node * tempPointer = root;
	while (tempPointer->left) {
		if (tempPointer->left && tempPointer->right) {
			if (tempPointer->left->data > tempPointer->right->data && tempPointer->data < tempPointer->left->data) {
				temp = tempPointer->data;
				tempPointer->data = tempPointer->left->data;
				tempPointer->left->data = temp;
				tempPointer = tempPointer->left;
			}
			else if (tempPointer->left->data < tempPointer->right->data && tempPointer->data < tempPointer->right->data) {
				temp = tempPointer->data;
				tempPointer->data = tempPointer->right->data;
				tempPointer->right->data = temp;
				tempPointer = tempPointer->right;

			}
		}
		else if (tempPointer->left && !(tempPointer->right)) {
			if (tempPointer->left->data > tempPointer->data) {
				temp = tempPointer->data;
				tempPointer->data = tempPointer->left->data;
				tempPointer->left->data = temp;
			}
			else {
				break;
			}
		}
		else {
			break;
		}
	}
}

 

전체

 

#define _CRT_SECURE_NO_WARNINGS


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

typedef struct node{
	int data;
	struct node* left;
	struct node* right;
	struct node* parent;
	struct node* queueLink;
	struct node* stackLink;
}node;

typedef struct heapType{
	struct node* root;
	struct node* queue;
	struct node* stack;
	struct node* lastDeletedNode;
}heapType;

void compareWithParents(node *newNode) {
	node * tempPointer = newNode;
	while (tempPointer->parent != NULL && tempPointer->data > tempPointer->parent->data) {
		int temp;
		temp = tempPointer->data;
		tempPointer->data = tempPointer->parent->data;
		tempPointer->parent->data = temp;
		tempPointer = tempPointer->parent;
	}
}

void compareWithChilde(node * root) {
	int temp;
	node * tempPointer = root;
	while (tempPointer->left) {
		if (tempPointer->left && tempPointer->right) {
			if (tempPointer->left->data > tempPointer->right->data && tempPointer->data < tempPointer->left->data) {
				temp = tempPointer->data;
				tempPointer->data = tempPointer->left->data;
				tempPointer->left->data = temp;
				tempPointer = tempPointer->left;
			}
			else if (tempPointer->left->data < tempPointer->right->data && tempPointer->data < tempPointer->right->data) {
				temp = tempPointer->data;
				tempPointer->data = tempPointer->right->data;
				tempPointer->right->data = temp;
				tempPointer = tempPointer->right;

			}
		}
		else if (tempPointer->left && !(tempPointer->right)) {
			if (tempPointer->left->data > tempPointer->data) {
				temp = tempPointer->data;
				tempPointer->data = tempPointer->left->data;
				tempPointer->left->data = temp;
			}
			else {
				break;
			}
		}
		else {
			break;
		}
	}
}

void insertNode(heapType* heap ,int data) {
	
	node * newNode = (node *)malloc(sizeof(node));

	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
	newNode->parent = NULL;
	newNode->queueLink = NULL;
	newNode->stackLink = NULL;
	node *sp = heap->stack;
	if (!(heap->root)) {
		heap->root = newNode;
		heap->queue = newNode;
		heap->stack = newNode;
		heap->lastDeletedNode = NULL;
	}
	else {
		if (!(heap->queue->left)) {
			heap->queue->left = newNode;
			newNode->parent = heap->queue;
			
			compareWithParents(newNode);

			newNode->stackLink = heap->stack;
			heap->stack->queueLink = newNode;
			heap->stack = newNode;
			
		}
		else if (heap->queue->right == NULL && heap->queue->left != NULL) {
			heap->queue->right = newNode;
			newNode->parent = heap->queue;

			compareWithParents(newNode);

			newNode->stackLink = heap->stack;
			heap->stack->queueLink = newNode;
			heap->stack = newNode;
		}
		else if ((heap->queue->left) && (heap->queue->right)) {
			heap->queue = heap->queue->queueLink;

			heap->queue->left = newNode;
			newNode->parent = heap->queue;

			compareWithParents(newNode);

			newNode->stackLink = heap->stack;
			heap->stack->queueLink = newNode;
			heap->stack = newNode;
		}
	}
}



int deleteNode(heapType* heap) {
	
	int rootNodeData = heap->root->data;
	int lastInsertedNodeData = heap->stack->data;

	heap->root->data = lastInsertedNodeData;

	node * temp = heap->stack;
	heap->stack = heap->stack->stackLink;
	heap->stack->queueLink = NULL;
	
	if (temp->parent->right == temp) {
		temp->parent->right = NULL;
	}
	else {
		temp->parent->left = NULL;
	}
	free(temp);

	compareWithChilde(heap->root);

	return rootNodeData;
}

heapType * resetHeapType(heapType * heap) {
	heapType * newHeap = (heapType *)malloc(sizeof(heapType));
	newHeap->root = NULL;
	newHeap->queue = NULL;
	newHeap->stack = NULL;
	newHeap->lastDeletedNode = NULL;

	return newHeap;
}


int main() {

	FILE * inputFile = NULL;
	int data;
	heapType * heap = NULL;

	heap = resetHeapType(heap);

	if (!(inputFile = fopen("./input.txt", "r+"))) {
		printf("file is not open");
		return EXIT_FAILURE;
	}
	rewind(inputFile);
	while ((fscanf(inputFile, "%d", &data)) != EOF) {
		insertNode(heap, data);
	}

	for (int i = 0; i < 3; i++) {
		deleteNode(heap);

	}

	fclose(inputFile);
	printf("helloworld");
	return 0;
}

 

반응형

'C-language' 카테고리의 다른 글

[C-language] quick-sort (median, left,right)  (0) 2019.12.05
[DataStructure] 완전이진트리 삽입과 삭제 light 버전  (0) 2019.10.23
[DataStructure] 완전이진트리의 삽입과 합계  (0) 2019.09.22
'C-language' Related Articles more
Comments