쌩으로 혼자 구현해본 이진 탐색 트리

1. 프롤로그

Ch 11 개념을 강의로 들으면서 비교 기준이 되는 노드보다 더 큰 수는 오른쪽 서브트리, 더 작은 수는 왼쪽 서브트리에 저장한다는 것을 알았다.

그러나 나머지 개념을 가르쳐주지 않고 강의에서 바로 코드로 들어가서 설명을 하는데 이가 마음에 들지 않아 쌩으로 한번 이진 탐색 트리를 구현해보기로 마음을 먹었다.

2. 알고리즘

우선 강의에서 설명을 해주지 않은 바, 나는 중복된 데이터를 어떻게 처리할까 고민했고 비교되는 데이터와 같은 데이터들은 해당 노드의 오른쪽 서브트리에 저장하기로 했다.

그리고

개념에서 저 정도밖에 얘기해주지 않아서 내가 생각해낸 이진탐색트리의 알고리즘대로이면 이런 문제점이 나타날 것이라 생각하여 이를 개선할 방법을 생각해내고자 했는데, 이는 일반적인 이진탐색트리의 가장 큰 문제점이라는 것을 알게 되어 이 부분의 개선은 생각치 않고 넘어가기로 했다.

그리고 이 구현은

처음에 명령의 개수를 입력하고
그 다음줄부터 1과 정수를 입력하면 해당 정수를 이진탐색트리에 저장
2와 정수를 입력하면 해당 정수가 저장된 노드를 이진탐색트리에서 삭제
3을 입력하면 PreOrder, InOrder, PostOrder로 트리를 출력하는 것을 구현의 목표로 삼았다.

이 때 가장 고민된 부분이 삭제인데

일단 저렇게 두가지
삭제된 데이터의 자리를 메꾸는 데이터는
1. 부모 노드의 왼쪽 자식이라면 부모 노드보다 작고, 부모 노드의 오른쪽 자식이라면 부모 노드보다 커야 한다

-> 이는 삭제된 데이터의 서브트리들이 모두 성립하는 조건이므로 삭제된 데이터의 서브트리에서 데이터를 가져와야한다.

2. 자리를 메꾸는 노드는 삭제된 노드의 왼쪽 자식 노드보다 데이터가 크고 오른쪽 자식 노드보다 데이터가 작아야 한다

이 때 2번 조건을 만족시키는게 매우 어려웠다.

그래서 처음에는

저렇게 삭제된 데이터의 왼쪽 자식 노드의 오른쪽 노드 혹은 오른쪽 자식 노드의 왼쪽 노드를 가져오려고 했으나, 이는 조건은 만족할지언정 계속해서 자리를 메꿀 노드를 찾아서 가져와야 하는데다 구현이 힘들어보여 다른 방법을 찾게 되었다.

그러던 와중 한 노드를 삭제하면 자식 노드 중 아무거나 올려도 2. 조건이 성립한다는 것을 생각해내어 이를 이용하기로 마음먹었다.

그런데 문제가 있다면 자식 노드 중 오른쪽 노드를 올리기로 마음 먹었는데
오른쪽 노드의 오른쪽 서브 트리는 그대로 두면 되나, 왼쪽 서브트리를 삭제된 노드의 왼쪽 서브 트리로 바꾸면 왼쪽 서브트리는 갈 길을 잃어(?)버리게 되므로 왼쪽 서브트리는 따로 위치를 찾아주기로 하였다.
(위치만 찾아주면 서브트리는 이진 탐색 트리의 조건을 어차피 만족하므로 신경쓸 필요 X)

//지금 생각해보면 삽입하는 노드의 서브트리는 그대로 두고 삭제된 노드의 왼쪽 서브트리를 위치를 찾아주는게 가독성이 더 좋았을 것 같다.

그리고 삭제하고 다른 노드를 삽입할 때 부모 노드의 주소가 필요하다는 것을 깨닫고 트리의 노드 구조체에 mommy라는 성분을 추가하였다.

이후 몇번의 디버깅을 거쳐

다음의 코드를 완성하였다.

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

typedef struct btreenode
{
	int data;
	struct btreenode* left;
	struct btreenode* right;
	struct btreenode* mommy;
}BTreeNode;

BTreeNode* Route;

void Insert(BTreeNode* pNode, int data)
{
	if (data < pNode->data)
	{
		if (pNode->left == NULL)
		{
			pNode->left = malloc(sizeof(BTreeNode));
			pNode->left->data = data;
			pNode->left->left = NULL;
			pNode->left->right = NULL;
			pNode->left->mommy = pNode;
		}
		else Insert(pNode->left, data);
	}

	else//나는 데이터가 같으면 그 데이터의 오른쪽 서브트리에 저장하기로 마음 먹었다
	{
		if (pNode->right == NULL)
		{
			pNode->right = malloc(sizeof(BTreeNode));
			pNode->right->data = data;
			pNode->right->left = NULL;
			pNode->right->right = NULL;
			pNode->right->mommy = pNode;
		}
		else Insert(pNode->right, data);
	}
}

void FindSeat(BTreeNode* pNode, BTreeNode* missingNode)
{
	if (missingNode == NULL) return;
	if (missingNode->data < pNode->data)
	{
		if (pNode->left == NULL)
		{
			pNode->left = missingNode;
			missingNode->mommy = pNode;
		}
		else FindSeat(pNode->left, missingNode);
		return;
	}

	else
	{
		if (pNode->right == NULL)
		{
			pNode->right = missingNode;
			missingNode->mommy = pNode;
		}
		else FindSeat(pNode->right, missingNode);
		return;
	}
}

void Delete(BTreeNode* pNode, int data)
{
	BTreeNode* temp;
	BTreeNode* Mommy;
	BTreeNode* OriginalLeft;
	if (pNode == NULL)
	{
		printf("없는걸 왜 찾니 ㅠㅠ\n");
		return;
	}
	if (data == pNode->data)
	{
		if (pNode == Route)
		{
			temp = Route;
			if (Route->right == NULL)
			{
				Route = temp->left;
				free(temp);
			}
			else
			{
				OriginalLeft = Route->right->left;
				Route = temp->right;
				Route->left = temp->left;
				if (temp->left != NULL)
				{
					temp->left->mommy = Route;
				}
				free(temp);
				FindSeat(Route, OriginalLeft);
				return;
			}
		}
		else
		{
			temp = pNode;
			Mommy = pNode->mommy;
			if (temp->right == NULL)
			{
				if (Mommy->left == temp)
				{
					Mommy->left = temp->left;
					if (temp->left != NULL)
					{
						temp->left->mommy = Mommy;
					}
					free(temp);
				}
				else
				{
					Mommy->right = temp->left;
					if (temp->left != NULL)
					{
						temp->left->mommy = Mommy;
					}
					free(temp);
				}
			}
			else
			{
				OriginalLeft = pNode->right->left;
				if (Mommy->left == temp)
				{
					Mommy->left->right->left = temp->left;
					if (temp->left != NULL)
					{
						temp->left->mommy = Mommy->left->right;
					}
					Mommy->left = temp->right;
					if (temp->right != NULL)
					{
						temp->right->mommy = Mommy;
					}
					free(temp);
					FindSeat(Route, OriginalLeft);
					return;
				}
				else
				{
					Mommy->right->right->left = temp->left;
					if (temp->left != NULL)
					{
						temp->left->mommy = Mommy->right->right;
					}
					Mommy->right = temp->right;
					if (temp->right != NULL)
					{
						temp->right->mommy = Mommy;
					}
					free(temp);
					FindSeat(Route, OriginalLeft);
					return;
				}
			}	
		}
	}
	else if (data < pNode->data)
	{
		Delete(pNode->left, data);
		return;
	}
	else
	{
		Delete(pNode->right, data);
		return;
	}
}

void PreOrder(BTreeNode* tree)
{
	if (tree == NULL) return;
	printf("%d ", tree->data);
	PreOrder(tree->left);
	PreOrder(tree->right);
	return;
}

void InOrder(BTreeNode* tree)
{
	if (tree == NULL) return;
	InOrder(tree->left);
	printf("%d ", tree->data);
	InOrder(tree->right);
	return;
}

void PostOrder(BTreeNode* tree)
{
	if (tree == NULL) return;
	PostOrder(tree->left);
	PostOrder(tree->right);
	printf("%d ", tree->data);
	return;
}


int main()
{
	int i, N;
	int x, data;
	int NumOfData = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d", &x);
		if (x == 1)
		{
			scanf("%d", &data);
			if (NumOfData == 0)
			{
				Route = malloc(sizeof(BTreeNode));
				Route->data = data;
				Route->left = NULL;
				Route->right = NULL;
				NumOfData++;
			}
			else
			{
				Insert(Route, data);
				NumOfData++;
			}
		}

		else if (x == 2)
		{
			scanf("%d", &data);
			if (NumOfData == 0)
			{
				printf("이 트리엔 아무것도 없단다\n");
				exit(-1);
			}
			else
			{
				Delete(Route, data);
				NumOfData--;//없는 것도 삭제하라고 하려나, 그러면 안된다.
			}
		}
		else
		{
			InOrder(Route);
			printf("\n");
		}
	}
	return 0;
}

몇 개의 테스트 케이스를 집어넣어 봤는데
그 중 한 테스트 케이스를 예상한 결과와 실재 출력된 값이다.

결과의 가독성을 위해 위의 코드에서 몇줄을 추가하였다.

(그 뒤에 채점을 쉽게 하기 위해 중위순회만 출력하고, 다른 테스트 케이스에서 틀린 것을 몇번 더 찾아내어 디버깅을 한 결과 위의 최종적인 코드가 만들어졌다.)