이진 검색 트리(Binary Search Tree)

기본 이진 검색 트리

 

Declaration

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

typedef enum bool{ false, true } bool;

typedef enum eSelectMenu {
	selectInsert = 1,
	selectDelete,
	selectPrint,
	selectExit
} eSelectMenu;

typedef struct Node {
	int key_value;
	int count;
	struct Node* parent;
	struct Node* left;
	struct Node* right;
} Node;

 

Insert, Delete Node

void InsertNode(Node** root, int value) {
	Node* ptr, * parent;
	parent = ParentSearch(*root, value);

	if (parent != NULL || *root == NULL) {
		ptr = (Node*)malloc(sizeof(Node));
		if (ptr != NULL) {
			ptr->key_value = value;
			ptr->count = 1;
			ptr->parent = ptr->left = ptr->right = NULL;
		}
		else {
			fprintf(stderr, "Memory allocation failure\n");
		}

		if (*root != NULL) {	// root is not empty
			if (parent->key_value > value) parent->left = ptr;
			else parent->right = ptr;
			ptr->parent = parent;
			printf("Insert complete\n");
		}
		else {
			*root = ptr;	// empty
			printf("Create root node\n");
		}
	}
}

void DeleteNode(Node** root, int value) {
	if (*root == NULL) {
		printf("Empty root node\n");
		return;
	}

	Node* ptr = FindValue(*root, value);
	Node* temp_parent, * temp;

	if (ptr == NULL) {
		printf("Not found\n");
		return;
	}

	if (ptr == *root || (ptr->left && ptr->right)) {
		if (ptr->left == NULL && ptr->right == NULL) {	// root가 리프인 경우
			free(*root);
			*root = NULL;
		}
		else if (!(ptr->left && ptr->right)) {	// root이면서 child가 한개
			*root = (ptr->right == NULL) ? ptr->left : ptr->right;
			(*root)->parent = NULL;

			free(ptr);
		}
		else {	// root를 포함한 child 2개인 노드
			temp = InorderPredecessor(ptr);
			ptr->key_value = temp->key_value;	// 값 복사
            ptr->count = temp->count;
			temp_parent = temp->parent;
			ReStruct(temp_parent, temp->left, temp);

			free(temp);
		}
	}
	else {	// root가 아니고 child 1 이하인 노드
		temp_parent = ptr->parent;
		if (ptr->left != NULL) {
			ReStruct(temp_parent, ptr->left, ptr);
		}
		else if (ptr->right != NULL) {
			ReStruct(temp_parent, ptr->right, ptr);
		}
		else {	// leaf 노드
			NullChild(temp_parent, ptr);
		}
		free(ptr);
	}
	printf("Delete complete\n");
}

 

Method

/////////// insert 관련 method
Node* ParentSearch(Node* root, int value) {
	Node* ptr = root;

	while (ptr != NULL) {
		if (ptr->key_value == value) {	// 동일한 키값
			ptr->count += 1;
			printf("Already exist value. add count\n");
			return NULL;
		}
		else if (ptr->key_value > value) {
			if (ptr->left == NULL) return ptr;
			else ptr = ptr->left;
		}
		else {
			if (ptr->right == NULL) return ptr;
			else ptr = ptr->right;
		}
	}

	return NULL;	// root = NULL
}

/////////// delete 관련 method
Node* FindValue(Node* root, int value) {
	Node* ptr = root;

	while (ptr != NULL) {
		if (ptr->key_value == value) {
			return ptr;
		}
		else if (ptr->key_value > value) {
			ptr = ptr->left;
		}
		else {
			ptr = ptr->right;
		}
	}

	return NULL;
}

Node* InorderPredecessor(Node* root) {
	Node* ptr = root;
	ptr = ptr->left;

	while (ptr->right != NULL)
		ptr = ptr->right;

	return ptr;
}

void ReStruct(Node* parent, Node* child, Node* deleteNode) {
	if (child != NULL) child->parent = parent;
	if (deleteNode == parent->left) parent->left = child;
	else parent->right = child;
}

void NullChild(Node* parent, Node* child) {
	if (parent->left == child) parent->left = NULL;
	else parent->right = NULL;
}

/////////// print node value
void InorderPrint(Node* ptr) {
	if (ptr) {
		InorderPrint(ptr->left);
		printf("(val: %d, count: %d) ", ptr->key_value, ptr->count);
		InorderPrint(ptr->right);
	}
}

 

Main

int main(void) {
	int select;
	int value;
	Node* root = NULL;

	while (1) {
		printf("1. insert / 2. delete / 3. print / 4. exit\n");
		printf("select: ");
		scanf_s("%d", &select);
		switch (select) {
		case selectInsert:
			printf("Insert value: ");
			scanf_s("%d", &value);
			InsertNode(&root, value);
			puts("");
			break;
		case selectDelete:
			printf("Delete value: ");
			scanf_s("%d", &value);
			DeleteNode(&root, value);
			puts("");
			break;
		case selectPrint:
			if (root == NULL) {
				printf("Empty root node");
			}
			InorderPrint(root);
			puts("\n");
			break;
		case selectExit:
			printf("Exit Program\n");
			return 0;
		default:
			printf("re\n\n");
		}
		while (getchar() != '\n') {}
	}
}

 

실행 결과