January 19, 2024 18 min to read

자료구조(11) - 완전 이진 트리의 이진 탐색 트리의 구현

완전 이진 트리와 이진 탐색 트리의 ADT 작성 및 구현

🔚 짧게 하는 복습

✅ 1. 트리의 노드를 구조체로 만드는 방법을 안다.

✅ 2. 재귀 함수와 부분 문제를 이해한다.

✅ 3. 트리 생성을 재귀 함수를 통해 할 수 있다.

✅ 4. 트리 순회를 재귀 함수를 통해 할 수 있고, 각 순회를 알 수 있다.

혹시 기억이 안 난다면, 다시 돌아가자

지금까지 용어부터, 성질, 재귀 함수까지 다양한 이진 트리를 다루기 위한 기초를 닦았다.

이제부터는 진짜 본격적인 다양한 이진 트리의 ADT 작성 및 구현에 대해 다루어 보겠다.

알다시피 포화 이진 트리(FBT)는 한 노드가 삽입되거나 제거되면 더 이상 FBT가 아니므로, 순회나 수정을 제외하고는 특별한 ADT가 없다. (FBT의 순회나 원소 수정은 과제로 넘기겠다.)

그렇기에 완전 이진 트리(CBT)와 이진 검색 트리(BST)의 ADT와 구현을 집중해서 다루어 보겠다.

완전 이진 트리(CBT) ADT

자료 : 정수

기능1 삽입 : 원소를 CBT에 삽입한다.

기능2 삭제 : 원소를 CBT에서 삭제한다.

기능3 조회 : 원소를 CBT에서 조회한다.

기능4 수정 : 원소를 입력받아, 그 값이 있다면 기존의 값을 입력받은 값으로 수정한다.

기능5 순회 : CBT의 모든 원소를 처음부터 출력한다.

역시나 ADT는 요구에 맞게 작성되는 것이기에, 절대적인 것이 아니라 필요에 맞게 수정할 수 있다.

완전 이진 트리(CBT) 구현

우리는 트리를 만들기 전에, CBT의 성질을 다시 한번 복습할 필요가 있다.

마지막 level을 제외한 모든 level의 노드가 2개의 자식을 가졌으며, 마지막 level에서 노드가 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리를 완전 이진 트리(Complete Binary Tree)라고 한다.

이러한 성질 때문에, 완전 이진 트리를 만들려면 왼쪽 위부터 아래쪽 하단까지 순서대로 노드를 삽입하면 된다.

자, 중요한 말이라서 반복하자면, CBT는 원소의 입력 위치가 정해져 있다. 가장 오른쪽 아래.

그리고 이를 그림으로 그리면

삽입 순서를 인덱스로, 배열로 표현할 수 있다.

인덱싱으로 표현하면 A(0) B(1) C(2) D(3) E(4) F(5) G(6) H(7) I(8) J(9) K(10) L(11)이다.

또, i번째 노드의 2i+1은 왼쪽 자식 노드, 2i+2는 오른쪽 자식 노드임을 알 수 있다.

자 이제, CBT의 구현은 단순 배열로 바뀌었다.

심지어, 입력과 삭제의 위치가 맨 마지막 위치이다…? 맨 마지막에 들어온 원소가 맨 처음 나간다…?

LIFO…? 그렇다. CBT는 사실 스택의 구조를 그대로 가진다.

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

/*
자료 : 정수
기능1 삽입 : 원소를 CBT에 삽입한다.
기능2 삭제 : 입력 받은 원소가 있다면, 그 값을 CBT에서 삭제한다.
기능3 조회 : 입력 받은 원소가 있다면, 그 값이 CBT에 있는지 조회한다.
기능4 수정 : 원소를 입력받아, 그 값이 있다면 기존의 값을 입력받은 값으로 수정한다.
기능5 순회 : CBT의 모든 원소를 처음부터 출력한다.
*/

typedef int* CBT; //typedef를 통한 변환

//+ empty한지 확인

int is_empty(const int num_of_nodes) {
	if (num_of_nodes == 0) {
		return 1; //비었으면 참
	}
	else {
		return 0;//아니면 거짓
	}
}

//기능1 삽입
int insert(CBT* st, const int value, int* num_of_nodes) {
	if (is_empty(*num_of_nodes)) {
		*st = (CBT)malloc(sizeof(int) * (*num_of_nodes + 1));
	}//원소가 없으면 할당
	else {
		CBT new_st = (CBT)realloc(*st, sizeof(int) * (*num_of_nodes + 1));
		*st = new_st;
	}//재할당

	*(*st + *num_of_nodes) = value;
	printf("%d is pushed into CBT!\n\n", value);
	*num_of_nodes += 1;
	//대입
	//num_of_nodes 증가

	return 0;
}


//기능2 제거
int Delete(CBT* st, int* num_of_nodes) {
	if (is_empty(*num_of_nodes)) {
		printf("CBT is empty!\n\n");
		return -1;
	}//원소가 없으면 오류

	*num_of_nodes -= 1;// num_of_nodes 감소
	int ret = *(*st + *num_of_nodes);// ret값을 미리 저장(재할당을 위해)

	if (*num_of_nodes == 0) {
		*st = NULL;
	}//비었으면 NULL
	else {
		CBT new_st = (CBT)realloc(*st, sizeof(int) * (*num_of_nodes));
		*st = new_st;
	}//아니면 재할당

	return ret;// Delete한 원소 리턴
}

//기능3 조회
int search(CBT st, const int value, const int num_of_nodes) {
	if (is_empty(num_of_nodes)) {
		printf("CBT is empty!\n\n");
		return -1;
	}//원소가 없으면 오류

	for (int i = 0; i < num_of_nodes; i++) {
		if (st[i] == value) {
			printf("There is %d in CBT\n\n", value);
			return 0;
		}
	}

	printf("There is no %d in CBT\n\n", value);
	return -1;
}

//기능4 수정
int update(CBT st, const int value, const int new_value, const int num_of_nodes) {
	if (is_empty(num_of_nodes)) {
		printf("CBT is empty!\n\n");
		return -1;
	}//원소가 없으면 오류

	for (int i = 0; i < num_of_nodes; i++) {
		if (st[i] == value) {
			st[i] = new_value;
			printf("%d is changed with %d\n\n", value, new_value);
			return 0;
		}
	}
	printf("There is no %d in CBT\n\n", value);
	return -1;
}

//기능5 순회(Level_order_traversal)
int level_order_traversal(CBT st, const int num_of_nodes) {
	if (is_empty(num_of_nodes)) {
		printf("CBT is empty!\n\n");
		return -1;
	}//원소가 없으면 오류

	for (int i = 0; i < num_of_nodes; i++) {
		printf("%d ", st[i]);
	}
	printf("\n\n");
	return 0;
}


int main(void) {
	CBT st = NULL; // 동적 배열을 통한 스택 구현

	int num_of_nodes = 0;
	/*
	배열 구현에서 cur_size 역할, 즉 스택에 얼마나 많은 원소가 있는지를 나타냄
	또한, 가장 최근에 입력된 원소의 인덱스 값이기도 함.
	*/

	insert(&st, 1, &num_of_nodes);
	insert(&st, 2, &num_of_nodes);
	insert(&st, 3, &num_of_nodes);

	level_order_traversal(st, num_of_nodes); // 1 2 3

	insert(&st, 4, &num_of_nodes);
	insert(&st, 5, &num_of_nodes);

	level_order_traversal(st, num_of_nodes); // 1 2 3 4 5

	update(st, 3, 6, num_of_nodes);
	level_order_traversal(st, num_of_nodes); // 1 2 6 4 5

	Delete(&st, &num_of_nodes);
	Delete(&st, &num_of_nodes);
	Delete(&st, &num_of_nodes);
	level_order_traversal(st, num_of_nodes); // 1 2
	Delete(&st, &num_of_nodes);
	Delete(&st, &num_of_nodes);

	Delete(&st, &num_of_nodes);//오류, -1 반환

	free(st);
}

스택의 구조를 그대로 가져오고, traversal은 CBT의 장점을 살려 level_order을 이용하면 쉽게 구현할 수 있다.

결과창

is pushed into CBT!

is pushed into CBT!

is pushed into CBT!

2 3

is pushed into CBT!

is pushed into CBT!

2 3 4 5

is changed with 6

2 6 4 5

2

CBT is empty!

이진 검색 트리(BST) ADT

자료 : 정수

기능1 삽입 : 원소를 BST에 삽입한다.

기능2 삭제 : 원소를 BST에서 삭제한다.

기능3 조회 : 원소를 BST에서 조회한다.

기능4 순회 : BST의 모든 원소를 출력한다.

역시나 ADT는 요구에 맞게 작성되는 것이기에, 절대적인 것이 아니라 필요에 맞게 수정할 수 있다.

이진 검색 트리(BST)의 구현

BST의 삽입과 조회, 순회는 간단하다. 그냥 큰지, 작은지 비교하며 따라가서 삽입, 순회하면 된다. (구현의 디테일에 주목하도록 하자)

사실 BST의 구현에서 가장 어려운 것은 제거인데, 아마 자료구조에서 다룬 내용 중 가장 어려운 게 아닐까 싶다.

제거는 3가지 경우로 나뉜다는 점을 알아야 한다.

자식 노드가 없는 경우: 해당 노드를 삭제
자식 노드가 하나일 때: 해당 노드를 삭제하고, 자식 노드를 삭제된 노드의 부모 노드에 연결한다.
자식 노드가 둘일 때: 삭제할 노드를 삭제하고, 그 자리에 삭제된 노드보다 큰 값 중 가장 작은 노드나 삭제된 노드보다 작은 값 중 가장 큰 노드를 가져와야 한다.

3번에 대한 간략한 증명은 구현 이후에 하겠다.

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

/*
자료 : 정수
기능1 삽입 : 원소를 BST에 삽입한다.
기능2 삭제 : 원소를 BST에서 삭제한다.
기능3 조회 : 원소를 BST에서 조회한다.
기능4 순회 : BST의 모든 원소를 출력한다.
*/

typedef struct Node* treePointer;

typedef struct Node {
	int data;               // 자료 값
	treePointer left_child;       // 첫째 자식 노드를 가리키는 포인터
	treePointer right_child;       // 둘째 자식 노드를 가리키는 포인터
} node;                     // 노드


// + 노드를 만드는 함수
treePointer make_node(const int data) {
	treePointer new_node = (treePointer)malloc(sizeof(node));
	new_node->data = data;
	new_node->left_child = NULL;
	new_node->right_child = NULL;

	return new_node;
}

//기능1 삽입 : 원소를 BST에 삽입한다.
treePointer insert(treePointer root, int data) {
	//void나 int 대신 treePointer를 쓰면 코드를 간결하게 작성할 수 있다.

	if (root == NULL) return make_node(data);
	// 삽입될 위치를 찾을 때까지 따라가다가, leaf에서 삽입

	if (data < root->data)
		root->left_child= insert(root->left_child, data);
	else if (data > root->data)
		root->right_child = insert(root->right_child, data);

	return root;
}

treePointer findMin(treePointer root) {
	while (root->left_child != NULL)
		root = root->left_child;
	return root;
}// Delete를 위한 함수, 서브트리의 최소값을 찾음

/*
기능2 삭제 : 원소를 BST에서 삭제한다.
1. 자식 노드가 없는 경우: 해당 노드를 삭제

2. 자식 노드가 하나인 경우: 해당 노드를 삭제하고,
자식 노드를 삭제된 노드의 부모 노드에 연결한다.

3. 자식 노드가 둘인 경우: 삭제할 노드를 삭제하고,
그 자리에 삭제된 노드보다 큰 값 중 가장 작은 노드, 또는
삭제된 노드보다 작은 값 중 가장 큰 노드를 가져와야한다.
*/

treePointer Delete(treePointer root, int data) {
	//void나 int 대신 treePointer를 쓰면 코드를 간결하게 작성할 수 있다.

	if (root == NULL) return root;

	// 삭제할 노드 찾기
	if (data < root->data)
		root->left_child = Delete(root->left_child, data);
	else if (data > root->data)
		root->right_child = Delete(root->right_child, data);
	else {
		// 삭제할 노드를 찾았을 때
		if (root->left_child == NULL) {
			// 삭제할 노드가 자식이 0개 혹은 1개인 경우

			treePointer temp = root->right_child;
			// Null과 반대 방향 자식을 가리키기를 동시 처리.

			free(root);
			return temp;
		}
		else if (root->right_child == NULL) {
			// 삭제할 노드가 1개의 자식을 가지는 경우

			treePointer temp = root->left_child;
			free(root);
			return temp;
		}

		// 삭제할 노드가 두 개의 자식을 가지는 경우
		treePointer temp = findMin(root->right_child);
		root->data = temp->data;
		root->right_child = Delete(root->right_child, temp->data);
	}
	return root;
}

// BST의 성질을 이용한 조회의 핵심 기능
int rec_search(treePointer root, const int data) {
    if (root == NULL) {
        return 0; // 찾지 못한 경우 0 반환
    }

    if (data < root->data) {
        return rec_search(root->left_child, data);
		// data가 루트의 값보다 작으면 왼쪽

	} else if (data > root->data) {
        return rec_search(root->right_child, data);
		// 아니면 오른쪽 이동

	} else {
        return 1;
		// 찾은 경우 1 반환
    }
}

// 기능3 조회 : 원소를 BST에서 조회한다.
void search(treePointer root, const int data) {
    if (rec_search(root, data)) {
        printf("There is %d in BST\n\n", data);
    } else {
        printf("There is no %d in BST\n\n", data);
    }
}


// 기능4 순회 : BST의 모든 원소를 출력한다.
void preorder(treePointer root) {// 전위 순회(preorder, VLR)
	if (root == NULL) {
		return;
	}
	printf("%d ", root->data); //V
	preorder(root->left_child); // L
	preorder(root->right_child); // R
}

void inorder(treePointer root) {// 중위 순회(inorder, LVR)
	if (root == NULL) {
		return;
	}
	inorder(root->left_child); // L
	printf("%d ", root->data); //V
	inorder(root->right_child); // R
}

void postorder(treePointer root) {// 후위 순회(postorder, LRV)
	if (root == NULL) {
		return;
	}
	postorder(root->left_child); // L
	postorder(root->right_child); // R
	printf("%d ", root->data); //V
}

int main(void) {
	treePointer root = make_node(12);

	insert(root, 4);
	insert(root, 16);
	insert(root, 2);
	insert(root, 6);
	insert(root, 14);
	insert(root, 18);
	insert(root, 17);

	search(root, 18);
	search(root, 15);

	printf("Preorder : ");
	preorder(root);
	printf("\n\n");

	printf("inorder : ");
	inorder(root);
	printf("\n\n");

	printf("postorder : ");
	postorder(root);
	printf("\n\n");

	Delete(root, 16);

	printf("inorder : ");
	inorder(root);
	printf("\n\n");

	Delete(root, 14);

	printf("inorder : ");
	inorder(root);
	printf("\n\n");

}

아마 구현으로도 벅찼을 텐데, 제거에서 3번째 경우가 어떻게 저 알고리즘이 BST 구조가 유지되는지 이해가 안 될 것이다.

이는 간략한 증명을 하자면,

우선 트리의 inorder 순회를 하면 위에서 정사영한 모습이 나온다.

그리고 특히, BST에서 inorder 순회를 하면 원소가 정렬된 상태로 나온다.

3번에서 삭제될 값이 대체될 자리에 들어갈 것이, 삭제될 노드의 왼쪽 서브 트리 중 가장 큰 값 혹은 오른쪽 서브 트리 중 가장 작은 값이라고 했다.

이는 inorder 순회를 했을 때, 그 노드의 바로 왼쪽 혹은 오른쪽 값이라는 뜻이다.

그렇기에 그들 중 어떤 값으로 대체해도 BST의 정렬 구조가 깨지지 않는 것이다.

(그래도 정 이해가 안 된다면 트리를 직접 그려보자)

결과창

There is 18 in BST

There is no 15 in BST

Preorder : 12 4 2 6 16 14 18 17

inorder : 2 4 6 12 14 16 17 18

postorder : 2 6 4 14 17 18 16 12

inorder : 2 4 6 12 14 17 18

inorder : 2 4 6 12 17 18

📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

✅ 1. CBT와 스택 구조의 공통점을 이해하고 ADT를 구현할 수 있다.

✅ 2. BST의 제거 알고리즘을 이해한다.

✅ 3. BST의 ADT를 구현할 수 있다.

⚠️ BST의 제거 알고리즘 및 전체 재귀 구현이 몹시 어렵다. 연습하며 따라가려고 노력하자.

💣 과제,

FBT의 순회, 수정을 구현해보자(난이도 下)
BST 안의 구현들을 완벽히 이해하도록 노력하자

Minflix v3.1.2

자료구조(11) - 완전 이진 트리의 이진 탐색 트리의 구현

🔚 짧게 하는 복습

완전 이진 트리(CBT) ADT

완전 이진 트리(CBT) 구현

결과창

이진 검색 트리(BST) ADT

이진 검색 트리(BST)의 구현

결과창

📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

자료구조(12) - 힙의 ADT와 구현

Minsu Choi

Comments

자료구조(11) - 완전 이진 트리의 이진 탐색 트리의 구현

🔚 짧게 하는 복습

완전 이진 트리(CBT) ADT

완전 이진 트리(CBT) 구현

결과창

이진 검색 트리(BST) ADT

이진 검색 트리(BST)의 구현

결과창

📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

자료구조(12) - 힙의 ADT와 구현

Don't go yet!

객체지향프로그래밍(30) - 강의를 마무리 하며

객체지향프로그래밍(29) - 이론적 배경(2) - 객체지향의 SOLID 원칙

Share

Minsu Choi

Comments