탐색(Search) 1

1. 탐색의 이해

이번 이야기의 주제는 탐색! 다시 말해서 '데이터를 찾는 방법'이다.

따라서 오래전에 소개한 '순차 탐색(linear serach)'이나 '이진 탐색(binary serach)'과 같은 탐색 알고리즘의 소개가 주를 이룰 것으로 생각하기 쉽다.

하지만 먼저 한 가지 사실을 밝히고 시작하고자 한다.

"탐색은 앞서 소개한 트리의 뒷이야기에 해당합니다"

굳이 따지자면 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다.

이유는 다음과 같다.

"효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안 된다."

"그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'를 우선 고민해야 한다."

그런데 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다.

때문에 지금부터 시작할 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여있다.

다시 말해서 트리에 대한 이해가 부족하다면 트리를 다시 한번 공부해야 이어서 소개하는 내용을 어렵지 않게 공부할 수 있다.

참고로 다음 챕터에서 소개하는 '테이블과 해쉬'도 탐색과 관련 있는 내용이다.

뿐만 아니라 앞서 소개한 정렬도 탐색을 목적으로 하는 경우가 대부분일 만큼 탐색은 자료구조에서, 아니 컴퓨터 공학에서 매우 중요한 위치를 차지하고 있다.

---

2. 이진 탐색 트리

이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있다.

이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 트리의 높이는 30을 넘지 않기 때문이다.

그렇다면 이것이 탐색에 있어서 어떤 의미를 지니겠는가?

예를 들어서 연결 리스트에 10억 개의 데이터가 저장되어 있다고 가정해보자.

그리고 우리가 찾는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정하자.

이는 분명 유용한 정보이다.

하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 한다.

반면 이진 트리의 경우에는 위치를 알고 있다면, 다시 말해서 데이터에 이르는 길을 알고 있다면 루트 노드에서부터 단말 노드에 이르기까지 총 30개의 노드를 지나는 과정에서 원하는 데이터를 찾을 수 있다.

물론 여기에는 다음과 같은 가정이 존재한다.

"이진 트리는 단말 노드에 이르는 길의 갈래가 매우 많다."

"따라서 찾는 데이터가 존재하는 제대로 된 길을 선택할 수 있어야 한다."

---

자! 그럼 이번에 소개하는 '이진 탐색 트리'는 어떠한 특성의 트리인지 대략 짐작이 가능할 것이다.

여러분의 짐작대로 이진 탐색 트리는 다음과 같은 특성을 지닌다.

"이진 탐색 트리에는 데이터를 저장하는 규칙이 있다."

"그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다."

쉽게 말해서 '이진 트리'에 '데이터의 저장 규칙'을 더해놓은 것이 '이진 탐색 트리'이다.

그럼 이어서 이진 탐색 트리가 되기 위한 조건을 나열하겠다.

참고로 '탐색 키'는 정수라 가정하였으며, 이러한 탐색 키를 간단히 키(key)로 표현하였다.

- 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.

- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

앞서 '키(key)'에는 유일하다는 의미가 포함되어 있음을 언급하였다.

그럼 위의 조건을 만족하는 트리의 예를 그림으로 보이겠다.

위 그림에서 보이듯이 루트 노드의 왼쪽 서브 트리에 저장된 값들은 12보다 작고, 오른쪽 서브 트리에 저장된 값들은 12보다 크다.

그런데 위의 그림을 통해서 다음 수식이 어디서나 만족함을 알 수 있다.

왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

그리고 이 수식이 이진 탐색 트리의 구현에 더 직접적으로 도움이 되는 결론이다!

그럼 위 그림의 이진 탐색 트리를 대상으로 숫자 10을 저장한다고 가정해보자.

그러면 루트 노드를 시작으로 하여 다음의 과정을 거쳐서 저장될 위치를 결정하게 된다.

- 1단계: 10 < 12 이므로 왼쪽 자식 노드로 이동

- 2단계: 10 > 8 이므로 오른쪽 자식 노드로 이동

- 3단계: 10 > 9 이므로 오른쪽 자식 노드로 이동

- 4단꼐: 오른쪽에 아무것도 없으니 그 위치에 저장!

따라서 숫자 10은 다음 그림에서 보이듯이 숫자 9의 오른쪽 자식 노드로 저장이 된다.

이렇듯 이진 탐색 트리는 '작으면 왼쪽으로, 크면 오른쪽으로'라는 원칙을 기준으로 데이터를 삽입한다.

따라서 탐색의 과정에서도 이를 그대로 따르면 된다.

찾는 키의 값이 비교대상보다 작으면 왼쪽 자식 노드로, 찾는 키의 값이 비교대상보다 크면 오른쪽 자식 노드로 이동하는 것이다.

때문에 이진 탐색 트리는 탐색의 과정에서 길을 잃을 일이 없다.

그리고 몇 단계 지나지 않아서 탐색 대상을 찾을 수 있다.

그러니 탐색의 효율은 두말할 필요가 없지 않은가!

---

우리는 이진 트리의 구현경험을 갖고 있다.

따라서 앞서 정의한 헤더파일을 활용해서 이진 탐색 트리의 코드를 완성할 것이다.

BinaryTree2.h, BinaryTree.c 가 우리가 활용할 파일들이다.

시간이 지났으니 이 둘에 대해서 기억이 나지 않을 수도 있다.

그렇다고 소스파일을 열어보는 행동은 하지 말자.

헤더파일에 선언된 함수들만 보고도 이진 탐색 트리를 구현할 수 있어야 하고, 또 그것이 가능한 수준으로 우리는 이진 트리를 구현했으니 말이다.

그럼 헤더파일 BinaryTree2.h에 선언된 함수들에 대해서 간단히 설명을 하겠다.

위 함수들을 보면서 앞서 다음과 같이 했던 말이 기억나지 않았는가?

"위에서 소개한 함수들은 이진 트리를 만드는 도구로써 정의된 것이다."

"도구인 이 함수들을 이용해서 이진 트리를 구성해야 하는 것이지, 이진 트리가 자동으로 만들어지는 것이 아니다."

그럼 위의 도구를 이용해서 이진 트리의 일종인 이진 탐색 트리를 구현해보자.

그리고 그 첫 번째 단계로 헤더파일을 정의하겠다.

---

BinarySearchTree.h

#ifndef __BINARY_SEARCH_TREE_H__
#define __BINARY_SEARCH_TREE_H__

#include "BinaryTree2.h"

typedef BTData	BSTData;

// BST의 생성 및 초기화
void BSTMakeAndInit(BTreeNode ** pRoot);

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode * bst);

// BST를 대상으로 데이터 저장(노드의 생성과정 포함)
void BSTInsert(BTreeNode ** pRoot, BSTData data);

// BST를 대상으로 데이터 탐색
BTreeNode * BSTSearch(BTreeNode * bst, BSTData target);

#endif

이진 탐색 트리의 핵심 연산 세 가지는 다른 자료구조들과 마찬가지로 삽입, 삭제 그리고 탐색이다.

그런데 삭제는 별도로 고민해야 할 문제이기 때문에, 우선 삽입과 탐색에 대한 함수를 각각 다음과 같이 정의하고자 한다.

• 삽입

void BSTInsert(BTreeNode ** pRoot, BSTData data)

• 탐색

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)

그럼 간단한 main 함수를 통해서 위의 두 함수와 헤더파일에 선언된 또 다른 함수의 사용방법을 보이도록 하겠다.

int main(void)
{
	BTreeNode * bstRoot; // bstRoot는 BST의 루트 노드를 가리킨다
	BTreeNode * sNode;    // search node

	BSTMakeAndInit(&bstRoot); // Binary Search Tree의 생성 및 초기화

	BSTInsert(&bstRoot, 1); // bstRoot에 1을 저장
	BSTInsert(&bstRoot, 2); // bstRoot에 2를 저장
	BSTInsert(&bstRoot, 3); // bstRoot에 3을 저장

    // 탐색! 1이 저장된 노드를 찾아서!
	sNode = BSTSearch(bstRoot, 1);
	if(sNode == NULL)
		printf("탐색 실패 \n");
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

	return 0;
}

위의 main 함수에서 보이듯이 다음과 같이 BSTMakeAndInit 함수가 호출되고 나면, 이진 탐색 트리의 생성 및 초기화가 완료된 것으로 간주한다.

BSTMakeAndInit(&bstRoot); // Binary Search Tree의 생성 및 초기화

이때부터 bstRoot는 생성된 이진 탐색 트리를 지칭하는 이름이 된다.

그래서 트리에 데이터를 추가할 때는 다음과 같이 함수를 호출한다.

BSTInsert(&bstRoot, 1); // bstRoot가 가리키는 트리에 1을 저장

위 문장에서 보이듯이, 이진 탐색 트리에 데이터를 저장하기 위해서 직접 노드를 생성할 필요가 없다.

노드의 생성과 위치의 선정 및 저장은 BSTInsert 함수 안에서 이뤄지기 때문이다.

그리고 다음 문장에서 보이듯이 데이터의 탐색도 유사한 방식으로 진행된다.

sNode = BSTSearch(bstRoot, 1);

탐색의 결과, 목표한 대상을 찾았다면 이를 저장하고 있는 노드의 주소 값이 반환된다.

그리고 main 함수에서 보였듯이 BSTGetNodeData 함수를 통해서 노드의 저장된 값을 얻을 수도 있다.

---

이진 트리의 삽입과 탐색은 어렵지 않다.

먼저 세 개의 노드로 구성된 트리에 숫자 11과 10의 추가과정을 순서대로 보이겠다.

위 그림을 통해서 비교대상보다 값이 작으면 왼쪽 자식 노드로, 값이 크면 오른쪽 자식 노드로 이동한다는 기본적인 사실 이외에 강조하고픈 것이 하나 있는데, 그것은 다음과 같다.

"비교대상이 없을 때까지 내려간다."

"그리고 비교대상이 없는 그 위치가 새 데이터가 저장될 위치이다."

위 그림에 이어서 29와 22를 저장하는 예를 하나 더 보이겠으니, 이를 기반으로 위의 내용을 다시 한번 확인하기 바란다.

이제 충분히 이해가 되었을 테니, 새 데이터의 저장을 담당하는 BSTInsert 함수를 보이도록 하겠다.

참고로 이는 지금껏 설명한 과정을 그대로 코드로 옮긴 결과이다.

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	BTreeNode * pNode = NULL;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * nNode = NULL;    // new node

	// 새로운 노드가 추가될 위치를 찾는다.
	while(cNode != NULL)
	{
		if(data == GetData(cNode))
			return;    // 키의 중복을 허용하지 않음

		pNode = cNode;

		if(GetData(cNode) > data)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}
	
	// pNode의 서브 노드에 추가할 새 노드의 생성
	nNode = MakeBTreeNode();    // 새 노드의 생성
	SetData(nNode, data);    // 새 노드에 데이터 저장

	// pNode의 서브 노드에 새 노드를 추가
	if(pNode != NULL)    // 새 노드가 루트 노드가 아니라면,
	{
		if(data < GetData(pNode))
			MakeLeftSubTree(pNode, nNode);
		else
			MakeRightSubTree(pNode, nNode);
	}
	else    // 새 노드가 루트 노드라면,
	{
		*pRoot = nNode;
	}
}

주석 이외의 내용을 조금 더 언급하겠다.

BSTInsert 함수에서 pRoot를 더블 포인터 형으로 받은 이유를 알겠는가?

main 함수에서 생성한 BTreeNode형 포인터 변수 bstRoot는 루트 노드를 가리켜야 한다.

그런데 이진 트리 노드의 생성은 main 함수에서 이뤄지는 것이 아니라 BSTInsert 내부에서 이뤄진다.

따라서 루트 노드의 생성과 마찬가지인 첫 노드의 생성 때, main 함수의 bstRoot에 새로 생성된 노드의 주소값을 넘겨주어 bstRoot가 루트 노드를 가리키게 하려는 것이다.

---

이어서 탐색을 담당하는 BSTSearch 함수를 보이겠다.

탐색의 과정은 삽입의 과정을 근거로 하기에 별도의 설명이 필요 없을 것이다.

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
	BTreeNode * cNode = bst;    // current node
	BSTData cd;    // current data

	while(cNode != NULL)
	{
		cd = GetData(cNode);

		if(target == cd)
			return cNode;
		else if(target < cd)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	return NULL; // 탐색대상이 저장되어 있지 않음
}

위 함수에 삽입된 while문에서도 비교대상의 노드보다 값이 작으면 왼쪽 자식 노드로, 값이 크면 오른쪽 자식 노드로 이동하고 있다.

그리고 이렇게 이동을 하면, 탐색을 위한 길을 제대로 가는 것이다.

그런데도 불구하고 더 이상 이동할 자식 노드가 없다면(NULL을 만났다면), 이는 찾는 데이터가 존재하지 않는 상황이다.

그래서 이를 바탕으로 while 문의 탈출조건이 구성되어 있다.

이렇게 해서 이진 탐색 트리의 삽입과 탐색에 대한 설명이 끝이 났다.

하지만 여기까지가 이진 탐색 트리의 반에 해당한다.

아직 삭제에 대해서 설명하지 않았기 때문이다.

그래도 여기까지의 구현을 바탕으로 BinarySearchTree 파일과 main 코드를 구성해보겠다.

---

BinarySerachTree.c

#include <stdio.h>
#include "BinaryTree2.h"
#include "BinarySearchTree.h"

void BSTMakeAndInit(BTreeNode ** pRoot)
{
	*pRoot = NULL;
}

BSTData BSTGetNodeData(BTreeNode * bst)
{
	return GetData(bst);
}

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	BTreeNode * pNode = NULL;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * nNode = NULL;    // new node

	// 새로운 노드가 추가될 위치를 찾는다.
	while(cNode != NULL)
	{
		if(data == GetData(cNode))
			return;    // 키의 중복을 허용하지 않음

		pNode = cNode;

		if(GetData(cNode) > data)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}
	
	// pNode의 서브 노드에 추가할 새 노드의 생성
	nNode = MakeBTreeNode();    // 새 노드의 생성
	SetData(nNode, data);    // 새 노드에 데이터 저장

	// pNode의 서브 노드에 새 노드를 추가
	if(pNode != NULL)    // 새 노드가 루트 노드가 아니라면,
	{
		if(data < GetData(pNode))
			MakeLeftSubTree(pNode, nNode);
		else
			MakeRightSubTree(pNode, nNode);
	}
	else    // 새 노드가 루트 노드라면,
	{
		*pRoot = nNode;
	}
}

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
	BTreeNode * cNode = bst;    // current node
	BSTData cd;    // current data

	while(cNode != NULL)
	{
		cd = GetData(cNode);

		if(target == cd)
			return cNode;
		else if(target < cd)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	return NULL;
}

---

BinarySearchTreeMain.c

#include <stdio.h>
#include "BinarySearchTree.h"

int main(void)
{
	BTreeNode * bstRoot;
	BTreeNode * sNode;    // search node

	BSTMakeAndInit(&bstRoot);

	BSTInsert(&bstRoot, 9);
	BSTInsert(&bstRoot, 1);
	BSTInsert(&bstRoot, 6);
	BSTInsert(&bstRoot, 2);
	BSTInsert(&bstRoot, 8);
//	BSTInsert(&bstRoot, 4);
	BSTInsert(&bstRoot, 3);
	BSTInsert(&bstRoot, 5);
//	BSTInsert(&bstRoot, 7);

	sNode = BSTSearch(bstRoot, 1);
	if(sNode == NULL)
		printf("탐색 실패 \n");
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode)); // 출력

	sNode = BSTSearch(bstRoot, 4);
	if(sNode == NULL)
		printf("탐색 실패 \n"); // 출력
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

	sNode = BSTSearch(bstRoot, 6);
	if(sNode == NULL)
		printf("탐색 실패 \n");
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode)); // 출력

	sNode = BSTSearch(bstRoot, 7);
	if(sNode == NULL)
		printf("탐색 실패 \n"); // 출력
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

	return 0;
}

---

이제 이진 탐색 트리의 삭제에 대해 배워볼 차례인데, 사실 이진 탐색 트리의 삭제는 단순하지 않다.

자! 그럼 다음그림을 통해서 삭제의 과정이 복잡한 이유부터 알아보자.

위 그림의 이진 탐색 트리에서 8이 담긴 노드를 삭제한다고 가정해보자.

이 상황에서 그냥 이 노드만 삭제하면 그만인가? 아니다!

그 자리를 누군가 대신 채워야만 이진 탐색 트리가 유지된다.

즉 이진 탐색 트리의 삭제가 어려운 이유는 다음과 같다.

"이진 탐색 트리에서 임의의 노드를 삭제하는 경우, 삭제 후에도 이진 탐색 트리가 유지되도록 빈 자리를 채워야 한다."

물론 모든 삭제의 경우에 있어서 이 문제를 고민해야 하는 것은 아니다.

삭제 대상이 단말 노드라면 그 노드만 삭제하면 그만이다.

하지만 단말 노드가 아니라면 위에서 말한 것처럼 삭제할 노드를 무엇으로 대신할지 고민해야 한다.

그럼 이진 탐색 트리의 삭제에 대한 경우의 수를 정리해 보겠다.

- 상황 1: 삭제할 노드가 단말 노드인 경우

- 상황 2: 삭제할 노드가 하나의 자식 노드를(하나의 서브 트리를) 갖는 경우

- 상황 3: 삭제할 노드가 두 개의 자섹 노드를(두 개의 서브 트리를) 갖는 경우

이렇듯 삭제에 대한 경우의 수는 세 가지이다.

하지만 구현방법에 따라서, 삭제 대상이 루트 노드인 경우와 그렇지 않은 경우를 나눠야 하기 때문에 삭제에 대한 경우의 수는 최대 여섯 가지로 구분할 수도 있다.

그럼 상황별 삭제방법에 대해 이야기하겠다.

---

먼저 단말 노드를 삭제하는 '상황 1'에서의 삭제방법을 그림을 통해 보이겠다.

위 그림에서 보이듯이 '상황 1'에서는 삭제 대상인 단말 노드를 삭제하는 것으로 삭제의 과정이 완료된다.

따라서 다음과 같이 코드를 구성하면 된다.

// dNode와 PNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
if(삭제할 노드가 단말 노드이다!)
{
	if(GetLeftSubTree(pNode) == dNode) // 삭제할 노드가 왼쪽 자식 노드라면
		RemoveLeftSubTree(pNode); // 왼쪽 자식 노드 트리에서 제거
	else // 삭제할 노드가 오른쪽 자식 노드라면
		RemoveRightSubTree(pNode); // 오른쪽 자식 노드 트리에서 제거
}

위에서 호출하고 있는 Remove 로 시작하는 두 함수는 아직 정의한 바 없는 함수들인데, 이들에 대해서는 잠시 후에 선언 및 정의하기로 하고, 우선 각각의 함수호출이 의미하는 바만 간단히 정리하겠다.

RemoveLeftSubTree(pNode); // pNode가 가리키는 노드의 왼쪽 자식 노드 트리에서 제거
RemoveRightSubTree(pNode); // pNode가 가리키는 노드의 오른쪽 자식 노드 트리에서 제거

그리고 GetLeftSubTree 함수는 BinaryTree2.h에 선언된 함수이니 위의 코드가 어떠한 흐름으로 구성되었는지는 이해할 수 있을 것이다.

---

이어서 '상황 2'에서의 삭제방법을 소개하겠다.

그런데 이 역시 어렵지 않다.

다음 그림에서 보이듯이 부모 노드와 자식 노드를 연결하는 작업만 추가하면 된다.

이렇듯 '상황 2'에서는 부모 노드와 자식 노드를 연결하는 것이 관건이다.

하지만 여기에도 한가지 주의할 사항이 있다.

"위 그림에서, 10이 저장된 노드가 삭제할 노드의 왼쪽 자식 노드이건 오른쪽 자식 노드이건, 

이에 상관없이 10이 저장된 노드는 8이 저장된 노드의 오른쪽 자식 노드가 되어야 한다."

이유가 무엇인가?

이는 10이 저장된 노드가 9가 저장된 노드를 대신하는 관계이기 때문이다.

그러니까 그냥 9가 저장된 노드를 대신한다고 생각하면 된다.

그리고 이러한 이유 때문에 아래에서 보이는 '상황 2'를 처리하는 코드에는 두 개의 if~else문이 등장한다.

// dNode와 pNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
{
	BTreeNode * dcNode;    // 삭제 대상의 자식노드를 가리키는 포인터 변수
		
    // 삭제 대상의 자식 노드를 찾는다
    if(GetLeftSubTree(dNode) != NULL) // 자식 노드가 왼쪽에 있다면
		dcNode = GetLeftSubTree(dNode);
	else // 자식 노드가 오른쪽에 있다면
		dcNode = GetRightSubTree(dNode);

    // 삭제 대상의 부모 노드와 자식 노드를 연결한다 
    if(GetLeftSubTree(pNode) == dNode) // 삭제 대상이 왼쪽 자식 노드이면
		ChangeLeftSubTree(pNode, dcNode); // 왼쪽으로 연결
	else // 삭제 대상이 오른쪽 자식 노드이면
		ChangeRightSubTree(pNode, dcNode); // 오른쪽으로 연결
}

위의 노드에도 처음보는 함수가 호출되고 있는데 그 둘은 다음과 같다.

- ChangeLeftSubTree: MakeLeftSubTree 함수와 유사한 함수

- ChangeRightSubTree: MakeRightSubTree 함수와 유사한 함수

이들에 대해서도 잠시 후에 별도로 정의하고 설명한다.

그러니 일단은 왼쪽 자식 노드(왼쪽 서브 트리) 혹은 오른쪽 자식 노드(오른쪽 서브 트리)를 교체하는 함수 정도로 이해하기 바란다.

참고로 조금만 더 언급하면, 위의 두 함수와 BinaryTree2.h에 선언된 Make~로 시작하는 두 함수와 유일한 차이점은, 기존 자식 노드의 메모리 소멸 과정을 동반하느냐 동반하지 않느냐에 있다.

---

이제 마지막으로 '상황 3'에서의 삭제방법을 이야기할 차례이다.

다음 그림을 보면서 삭제로 인해 비는 위치를 무엇으로 채울지 고민해보자.

위의 트리에서 8을 삭제하는 경우 이를 대체할 후보로 다음 두 개의 노드를 꼽을 수 있다.

- 8이 저장된 노드의 왼쪽 서브 트리에서 가장 큰 값인 7을 저장한 노드

- 8이 저장된 노드의 오른쪽 서브 트리에서 가장 작은 값인 9를 저장한 노드

위 그림에서 삭제 대상을 7 또는 9를 저장한 노드로 각각 대체했을 때의 결과는 다음과 같다.

이 그림에서 대체 후에도 이진 탐색 트리가 유지됨에 주목하자.

이렇듯 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 값이나, 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 저장한 노드로 대체하면 된다.

물론 서브 트리에서 가장 큰 값이나 가장 작은 값을 저장한 노드를 찾는 것은 어렵지 않은데, 다음 그림을 통해서 그 방법을 보이겠다.

위 그림에서 보이듯이 한 트리에서 가장 큰 값을 찾을 때는 NULL을 만날 때까지 계속해서 오른쪽 자식 노드로 이동하면 되고, 가장 작은 값을 찾을 때는 NULL을 만날 때까지 계속해서 왼쪽 자식 노드로 이동하면 된다.

다시 본론으로 돌아와서 '상황 3'에서는 삭제 대상을 '왼쪽 서브 트리에서 가장 큰 값을 저장한 노드'나 '오른쪽 서브 트리에서 가장 작은 값을 저장한 노드'로 대체하면 된다.

어느 것으로 대체해도 이진 탐색 트리의 유지에는 지장이 없으므로 우리는 다음의 방법을 선택하기로 했다.

"삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 지니는 노드를 찾아서 이것으로 삭제할 노드를 대체한다."

자! 그럼 위의 내용을 기준으로, 앞서 보인 이진 탐색 트리의 삭제 전과 후의 모습을 보면서 삭제의 방법을 고민해보겠다.

위 그림에서 보이는 삭제의 결과를 이루기 위해 해야할 일은 다음과 같다.

"삭제가 되는 8이 저장된 노드를 9가 저장된 노드로 대체한다."

"그리고 이로 인해서 생기는 빈 자리는 9가 저장된 노드의 자식 노드로 대체한다."

그리고 이를 위해서 다음의 방법을 적용하고자 한다.

위 그림에서는 8이 저장된 노드의 위치에 9가 저장된 노드를 가져다 놓지 않고, 값의 대입을 통해 노드의 교체를 대신하고 있다.

우선 이 방법이 여러모로 편리하다.

이 방법을 사용할 경우, 삭제 대상인 8이 저장된 노드의 부모 노드와 자식 노드의 연결을 유지하기 위해서 별도로 코드를 삽입할 필요가 없기 때문이다.

"그럼 위 그림에서 제안하는 방법과 달리, 10이 저장된 노드의 값도 부모 노드에 그냥 대입해버리면 간단한 것 아닌가요?"

"새로운 연결을 구성할 필요 없이요!"

멋진 생각이긴 하지만 10을 저장하고 있는 자식 노드의 값을 단순히 대입만하면 문제가 발생할 수 있는데, 그 이유는 다음과 같다.

"10을 저장하고 있는 자식 노드가 단말 노드가 아닌 경우를 생각해야 한다."

"단말 노드가 아니라면 단순 대입으로 노드의 대체를 대신할 수 없다."

위 말대로 단말 노드가 아니라면, 그 밑에 있는 모드 노드 들을 하나씩 위로 대입하는 과정을 거쳐야 하는데 이는 매우 번거롭다.

그럼 지금까지 설명한 내용을 바탕으로 '상황 3'에서의 삭제과정을 정리해 보겠다.

- 단계 1: 삭제할 노드를 대체할 노드를 찾는다.

- 단계 2: 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.

- 단계 3: 대체할 노드의 부모 노드와 자식 노드를 연결한다.

그럼 위의 세 단계를 코드로 옮겨보자.

생각보다 코드가 조금 긴 편이다.

하지만 우리가 그림을 통해서 한 이야기를 코드로 옮긴 것 뿐이니 천천히 살펴서 이해하자.

// dNode와 pNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
else
{
	BTreeNode * mNode = GetRightSubTree(dNode);    // mNode는 대체 노드
	BTreeNode * mpNode = dNode;    // mpNode는 대체 노드의 부모 노드
	
    ...

    // 단계 1. 삭제 대상의 대체 노드를 찾는다
	while(GetLeftSubTree(mNode) != NULL)
	{
		mpNode = mNode;
		mNode = GetLeftSubTree(mNode);
	}
	
	// 단계 2. 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
	SetData(dNode, GetData(mNode));

	// 단계 3. 대체할 노드의 부모 노드와 자식 노드를 연결한다.
	if(GetLeftSubTree(mpNode) == mNode) // 대체할 노드가 왼쪽 자식 노드라면
        // 대체할 노드의 자식 노드를 부모 노드의 왼쪽에 연결
		ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
	else // 대체할 노드가 오른쪽 자식 노드라면
        // 대체할 노드의 자식 노드를 부모 노드의 오른쪽에 연결
		ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
	
    ...
}

위의 코드는 잠시 후에 보일 실제 구현의 결과와 약간의 차이가 있지만, 위의 코드를 이해했다면 이로써 이진 탐색 트리에서의 삭제와 그 구현을 대부분 이해한 것으로 볼 수 있다.

"그런데 단계 3에 해당하는 코드가 조금 잘못된 것 같은데요."

"GetRightSubTree 함수를 호출하는 부분이요."

위의 문장에서 이상하다고 언급한 부분은 다음과 같다.

// 단계 3. 대체할 노드의 부모 노드와 자식 노드를 연결한다.
if(GetLeftSubTree(mpNode) == mNode) // 대체할 노드가 왼쪽 자식 노드라면
    // 대체할 노드의 자식 노드를 부모 노드의 왼쪽에 연결
	ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
else // 대체할 노드가 오른쪽 자식 노드라면
    // 대체할 노드의 자식 노드를 부모 노드의 오른쪽에 연결
	ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

GetRightSubTree 함수가 두 번 호출되었으니, 아무래도 이 중 하나는 GetLeftSubTree 함수의 호출로 대체해야 뭔가 짝이 맞을 것 같은 생각이 들 수 있다.

하지만 이는 잘못되지 않았다.

대체할 노드의 자식 노드는 항상 오른쪽에(오른쪽 자식 노드로) 존재하기 때문이다.

그 이유가 무엇인지 알겠는가?

앞서 했던 다음 결정이 바로 그 이유이다.

"삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 지니는 노드를 찾아서 이것으로 삭제할 노드를 대체한다."

가장 작은 값을 지니는 노드를 찾으려면 NULL을 만날 때까지 왼쪽 자식 노드로 계속해서 이동해야 한다.

NULL전까지 마지막 왼쪽 자식 노드를 찾으러 이동했으니 왼쪽 자식 노드는 더이상 없을 것 아닌가?

그러니 자식 노드가 있다면 그것은 오른쪽 자식 노드이기 때문에 GetRightSubTree 함수만 사용한 것이다.

---

삭제를 포함한 이진 탐색 트리의 완성을 위해서 우선 BinaryTree2.h와 BinaryTree2.c에 다음 네 개의 함수를 추가로 선언 및 정의하고자 한다.

이 네 개의 함수들의 내부는 다음과 같다.

void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub) 
{
	main->left = sub;
}
 
void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	main->right = sub;
}

메모리의 소멸을 수반하지 않고 main의 왼쪽 혹은 오른쪽 자식 노드를 변경한다.

// 왼쪽 자식 노드 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode * RemoveLeftSubTree(BTreeNode * bt)
{
	BTreeNode * delNode;

	if(bt != NULL) {
		delNode = bt->left;
		bt->left = NULL;
	}
	return delNode;
}

// 오른쪽 자식 노드 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode * RemoveRightSubTree(BTreeNode * bt)
{
	BTreeNode * delNode;

	if(bt != NULL) {
		delNode = bt->right;
		bt->right = NULL;
	}
	return delNode;
}

보통 '삭제' 또는 '제거'라고 하면 반드시 메모리의 해제까지 담당해야 하는 것으로 오해하는 경우가 많다.

하지만 '삭제'와 '메모리의 해제'는 별개의 것이다.

삭제과정에서 메모리의 해제를 포함하는 경우도 있지만, 반드시 필요한 것은 아니며 오히려 포함해서는 안 되는 경우도 존재한다.

솔직히 말하면 삭제과정에서 메모리의 해제를 포함하지 않는 것이 더 일반적이다.

그래서 위의 두 함수도 단순히 왼쪽 자식 노드와 오른쪽 자식 노드를 트리에서 제거할 뿐, 메모리의 해제까지 이뤄지도록 정의하지 않았다.

대신에 주소 값의 반환을 통해서 메모리의 해제에 대한 책임을 함수를 호출한 영역으로 넘기고 있다.

그럼 새롭게 정의된 위의 네 함수는 어디에 넣어야겠는가?

우리는 이진 트리를 구성하기 위한 도구를 다음 두 파일에 담아 두었다.

그리고 이 도구를 이용해서 이진 탐색 트리를 구성하였다.

BinaryTree2.h, BinaryTree2.c

그런데 함수의 성격을 보아 알겠지만, 앞서 보인 네 함수는 이진 트리의 구성에 관련된 도구의 일부이다.

따라서 위의 두 파일에 추가하는 것이 옳다.

그래서 위의 두 파일에 네 개의 함수를 추가한 결과로 파일의 이름을 다음과 같이 변경하고자 한다.

BinaryTree3.h, BinaryTree3.c

처음부터 네 개의 함수를 추가하는 것이 좋지 않았겠냐고 물을지도 모르겠다.

하지만 처음부터 필요로 할 모든 것을 완벽히 예측해서 도구를 만드는 것은 쉽지 않다.

그리고 그것이 옳은 것만은 아니다.

오히려 필요에 따라서 도구를 확장하고 수정해 나가는 것이 현명한 방법이다.

그래서 그 과정을 함께 경험하고자 트리 챕터에서 넣지 않고 이번 챕터에서 구현하게 된 것이다.

그럼 BinaryTree3.h와 BinaryTree3.c를 보이도록 하겠다.

---

BinaryTree3.h

#ifndef __BINARY_TREE3_H__
#define __BINARY_TREE3_H__

typedef int BTData;

typedef struct _bTreeNode
{
	BTData data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode * bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

typedef void VisitFuncPtr(BTData data);

void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);

// 왼쪽 자식 노드 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode * RemoveLeftSubTree(BTreeNode * bt);

// 오른쪽 자식 노드 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode * RemoveRightSubTree(BTreeNode * bt);

// 메모리 소멸을 수반하지 않고 main의 왼쪽 자식 노드를 변경한다. 
void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub);

// 메모리 소멸을 수반하지 않고 main의 오른쪽 자식 노드를 변경한다. 
void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub);

#endif

---

BinaryTree3.c

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

BTreeNode * MakeBTreeNode(void)
{
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

	nd->left = NULL;
	nd->right = NULL;
	return nd;
}

BTData GetData(BTreeNode * bt)
{
	return bt->data;
}

void SetData(BTreeNode * bt, BTData data)
{
	bt->data = data;
}

BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
	return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt)
{
	return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->left != NULL)
		free(main->left);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->right != NULL)
		free(main->right);

	main->right = sub;
}

void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
	if(bt == NULL)
		return;

	action(bt->data);
	PreorderTraverse(bt->left, action);
	PreorderTraverse(bt->right, action);
}

void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
	if(bt == NULL)
		return;

	InorderTraverse(bt->left, action);
	action(bt->data);
	InorderTraverse(bt->right, action);
}

void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
	if(bt == NULL)
		return;

	PostorderTraverse(bt->left, action);
	PostorderTraverse(bt->right, action);
	action(bt->data);
}

BTreeNode * RemoveLeftSubTree(BTreeNode * bt)
{
	BTreeNode * delNode;

	if(bt != NULL) {
		delNode = bt->left;
		bt->left = NULL;
	}
	return delNode;
}

BTreeNode * RemoveRightSubTree(BTreeNode * bt)
{
	BTreeNode * delNode;

	if(bt != NULL) {
		delNode = bt->right;
		bt->right = NULL;
	}
	return delNode;
}

void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub) 
{
	main->left = sub;
}
 
void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	main->right = sub;
}

---

이번에는 삭제기능을 추가한 이진 탐색 트리의 완전한 구현 결과를 보이기 위해서 다음 두 개의 파일을 보이겠다.

BinarySearchTree2.h, BinarySearchTree2.c

위의 두 파일은 앞서 소개한 BinarySearchTree.h와 BinarySearchTree.c를 확장한 결과이다.

당시에는 없었던 '노드의 삭제'와 더불어 '트리에 저장된 모든 데이터의 출력'을 위해 정의된 함수가 추가되었다.

그럼 두 파일을 보이겠다.

---

BinarySearchTree2.h

#ifndef __BINARY_SEARCH_TREE2_H__
#define __BINARY_SEARCH_TREE2_H__

#include "BinaryTree3.h"

typedef BTData	BSTData;

// 이진 탐색 트리의 생성 및 초기화
void BSTMakeAndInit(BTreeNode ** pRoot);

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode * bst);

// 이진 탐색 트리를 대상으로 데이터 저장(노드의 생성과정 포함)
void BSTInsert(BTreeNode ** pRoot, BSTData data);

// 이진 탐색 트리를 대상으로 데이터 탐색
BTreeNode * BSTSearch(BTreeNode * bst, BSTData target);

// 트리에서 노드를 제거하고 제거된 노드의 주소 값을 반환한다. 
BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target);

// 이진 탐색 트리에 저장된 모든 노드의 데이터를 출력한다.
void BSTShowAll(BTreeNode * bst);

#endif

---

BinarySearchTree2.c

#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree3.h"
#include "BinarySearchTree2.h"

void BSTMakeAndInit(BTreeNode ** pRoot)
{
	*pRoot = NULL;
}

BSTData BSTGetNodeData(BTreeNode * bst)
{
	return GetData(bst);
}

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	BTreeNode * pNode = NULL;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * nNode = NULL;    // new node

	// 새로운 노드가 추가될 위치를 찾는다.
	while(cNode != NULL)
	{
		if(data == GetData(cNode))
			return;    // 키의 중복을 허용하지 않음

		pNode = cNode;

		if(GetData(cNode) > data)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}
	
	// pNode의 서브 노드에 추가할 새 노드의 생성
	nNode = MakeBTreeNode();    // 새 노드의 생성
	SetData(nNode, data);    // 새 노드에 데이터 저장

	// pNode의 서브 노드에 새 노드를 추가
	if(pNode != NULL)    // 새 노드가 루트 노드가 아니라면,
	{
		if(data < GetData(pNode))
			MakeLeftSubTree(pNode, nNode);
		else
			MakeRightSubTree(pNode, nNode);
	}
	else    // 새 노드가 루트 노드라면,
	{
		*pRoot = nNode;
	}
}

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
	BTreeNode * cNode = bst;    // current node
	BSTData cd;    // current data

	while(cNode != NULL)
	{
		cd = GetData(cNode);

		if(target == cd)
			return cNode;
		else if(target < cd)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	return NULL;
}

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
	// 삭제 대상이 루트 노드인 경우를 별도로 고려해야 한다.

	BTreeNode * pVRoot = MakeBTreeNode();    // 가상 루트 노드;

	BTreeNode * pNode = pVRoot;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * dNode;    // delete node

	// 루트 노드를 pVRoot가 가리키는 노드의 오른쪽 서브 노드가 되게 한다.
	ChangeRightSubTree(pVRoot, *pRoot);
	
	// 삭제 대상을 저장한 노드 탐색
	while(cNode != NULL && GetData(cNode) != target)
	{
		pNode = cNode;

		if(target < GetData(cNode))
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	if(cNode == NULL)    // 삭제 대상이 존재하지 않는다면,
		return NULL;

	dNode = cNode;    // 삭제 대상을 dNode가 가리키게 한다.

	// 첫 번째 경우: 삭제할 노드가 단말 노드인 경우
	if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
	{
		if(GetLeftSubTree(pNode) == dNode)
			RemoveLeftSubTree(pNode);
		else
			RemoveRightSubTree(pNode);
	}

	// 두 번째 경우: 하나의 자식 노드를 갖는 경우
	else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
	{
		BTreeNode * dcNode;    // delete node의 자식 노드

		if(GetLeftSubTree(dNode) != NULL)
			dcNode = GetLeftSubTree(dNode);
		else
			dcNode = GetRightSubTree(dNode);

		if(GetLeftSubTree(pNode) == dNode)
			ChangeLeftSubTree(pNode, dcNode);
		else
			ChangeRightSubTree(pNode, dcNode);
	}

	// 세 번째 경우: 두 개의 자식 노드를 모두 갖는 경우
	else
	{
		BTreeNode * mNode = GetRightSubTree(dNode);    // mininum node
		BTreeNode * mpNode = dNode;    // mininum node의 부모 노드
		int delData;

		// 삭제할 노드를 대체할 노드를 찾는다.
		while(GetLeftSubTree(mNode) != NULL)
		{
			mpNode = mNode;
			mNode = GetLeftSubTree(mNode);
		}
		
		// 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
		delData = GetData(dNode);    // 대입 전 데이터 백업
		SetData(dNode, GetData(mNode));

		// 대체할 노드의 부모 노드와 자식 노드를 연결한다.
		if(GetLeftSubTree(mpNode) == mNode)
			ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
		else
			ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

		dNode = mNode;
		SetData(dNode, delData);    // 백업 데이터 복원
	}

	// 삭제된 노드가 루트 노드인 경우에 대한 처리
	if(GetRightSubTree(pVRoot) != *pRoot)
		*pRoot = GetRightSubTree(pVRoot);

	free(pVRoot);
	return dNode;
}

void ShowIntData(int data)
{
	printf("%d ", data);
}

void BSTShowAll(BTreeNode * bst)
{
	InorderTraverse(bst, ShowIntData);
}

이어서 노드의 삭제를 담당하는 함수인 BSTRemove를 한 번 살펴보자.

먼저 다음 포인터 변수의 선언과 그 참조관계를 살펴보자.

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
	// 삭제 대상이 루트 노드인 경우를 별도로 고려해야 한다.
	BTreeNode * pVRoot = MakeBTreeNode();    // 가상 루트 노드;

	BTreeNode * pNode = pVRoot;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * dNode;    // delete node

	// 루트 노드를 pVRoot가 가리키는 노드의 오른쪽 서브 노드가 되게 한다.
	ChangeRightSubTree(pVRoot, *pRoot);

    ...
}

위의 함수가 다음과 같이 호출되었다고 가정하자.

그러면 첫 번째 매개변수인 pRoot에는 '루트 노드를 가리키는 포인터 변수의 주소 값'이 담기게 된다.

BSTRemove(&bstRoot, 7); // bstRoot에 루트 노드의 주소 값이 담겨 있다.

그리고 인자 전달에 이어서 ChangeRightSubTree 함수의 호출까지 실행되면, 다음의 상태가 된다.

위 그림에서 보이듯이 V라는 노드를 하나 생성해서, 실제 루트 노드인 R이 V의 오른쪽 자식 노드가 되게 하고 있다.

이렇듯 가상 루트 노드를 둔 이유는 다음과 같다.

"삭제할 노드가 루트 노드인 경우의 예외적인 삭제흐름을 일반화하기 위함이다."

그럼 위 문장이 의미하는 바를 설명하겠다.

앞서 우리는 삭제할 노드가 '단말 노드인 경우', '자식 노드를 하나 갖는 경우' 그리고 '자식 노드를 두 개 갖는 경우'로 구분하였다.

그런데 단말 노드는 루트 노드일 수 있다.

마찬가지로 자식 노드를 하나 또는 두 개 갖는 노드도 루트 노드일 수 있다.

그런데 이렇듯 삭제 대상이 루트 노드인 경우 삭제의 방법을 조금 달리해야 한다.

"루트 노드를 삭제하는 경우에는 뭐가 달라지는 거죠?"

위 그림을 보면 cNode가 가리키는 노드의 부모 노드를 pNode가 가리키고 있는데, 이 관계는 삭제과정 내내 유지되어야 한다.

이렇듯 cNode와 pNode의 관계를 유지해야 하는 이유는 다음과 같다.

"삭제할 노드를 cNode가 가리키게 되는데, 삭제의 과정에서는 cNode의 부모와 자식을 연결시키는 과정이 등장하는 경우가 있습니다."

"때문에 cNode의 부모 노드를 언제든 가리키고 있어야 하지요."

삭제의 과정에서 삭제할 노드의 부모와 자식을 연결시키는 경우가 있음을 기억할 것이다.

그런데 문제는 루트 노드에 부모 노드가 존재하지 않는다는데 있다.

따라서 루트 노드의 삭제과정은 조금 달라질 수밖에 없다.

하지만 위에서 보이듯이 가상의 루트 노드를 둔다면, 루트 노드를 삭제하는 경우에도 위 함수의 if-else 구문을 그대로 활용할 수 있다.

---

그럼 이어서 ChangeRightSubTree 함수호출에 이어서 등장하는 다음 반복문을 보자.

이 반복문을 통해서 삭제의 대상을 찾는 과정이 진행된다.

// 삭제 대상을 저장한 노드 탐색
while(cNode != NULL && GetData(cNode) != target)
{
	pNode = cNode;

	if(target < GetData(cNode))
		cNode = GetLeftSubTree(cNode);
	else
		cNode = GetRightSubTree(cNode);
}

위의 반복문을 보면서 다음과 같은 생각을 잠깐이나마 했을지 모르겠다.

사실 이러한 생각을 했다는 것 자체가 매우 긍정적이라고 생각한다.

"노드의 탐색을 위한 BSTSearch 함수가 정의되어 있는데, 왜 이 함수를 사용하지 않고 별도로 반복문을 구성한거지?"

위의 반복문을 실행하게 되면 cNode는 삭제할 노드를 가리키게 되는데, 이것이 전부라면 위의 반복문을 대신해서 다음과 같이 문장을 구성해도 된다.

cNode = BSTSearch(*pRoot, target);

하지만 이렇게 해서는 cNode의 부모 노드를 pNode가 가리키게 할 수 없다.

즉 pNode가 가리키는 대상의 갱신을 위해서 별도의 반복문을 구성해야 한다.

---

그럼 삭제과정의 마지막을 담당하는, if-else 구문 뒤에 등장하는 다음 if문에 대해서 설명하겠다.

// 삭제된 노드가 루트 노드인 경우에 대한 처리
if(GetRightSubTree(pVRoot) != *pRoot)
	*pRoot = GetRightSubTree(pVRoot);

삭제 대상이 루트 노드인 경우, 루트 노드는 다른 노드로 대체되기도 한다.

이렇듯 루트 노드가 대체되고나면, 매개면수인 pRoot가 가리키는 포인터 변수는 더 이상 이진 탐색 트리의 루트 노드를 가리키지 않게 된다.

하지만 삭제 연산 후에도 이 포인터 변수는 루트 노드를 가리켜야 한다.

바로 이 때문에 마지막 부분에서 위의 문장을 삽입한 것이다.

---

이제 새로 추가된 두 번째 함수를 보이겠다.

이는 이진 탐색 트리에 저장된 모든 데이터를 출력하기 위해 정의된 함수인데, 이진 트리의 InorderTraverse 함수를 활용한 형태이니 별도의 설명은 생략하겠다.

void ShowIntData(int data)
{
	printf("%d ", data);
}

void BSTShowAll(BTreeNode * bst)
{
	InorderTraverse(bst, ShowIntData);
}

위의 함수와 같이, 이진 탐색 트리를 대상으로 중위 순회를 할 경우, 정렬된 순서로 데이터를 참조 및 출력할 수 있다.

자! 마지막으로 완성된 이진 탐색 트리의 확인을 위한 main 함수를 소개하겠다.

그리고 이로써 이진 탐색 트리에 대한 길었던 이야기를 마무리하고자 한다.

---

BinarySearchTreeDelMain.c

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

int main(void)
{
	BTreeNode * bstRoot;
	BTreeNode * sNode;    // search node

	BSTMakeAndInit(&bstRoot);

	BSTInsert(&bstRoot, 5);
	BSTInsert(&bstRoot, 8);
	BSTInsert(&bstRoot, 1);
	BSTInsert(&bstRoot, 6);
	BSTInsert(&bstRoot, 4);
	BSTInsert(&bstRoot, 9);
	BSTInsert(&bstRoot, 3);
	BSTInsert(&bstRoot, 2);
	BSTInsert(&bstRoot, 7);

	BSTShowAll(bstRoot); printf("\n");
	sNode = BSTRemove(&bstRoot, 3);
	free(sNode);

	BSTShowAll(bstRoot); printf("\n");
	sNode = BSTRemove(&bstRoot, 8);
	free(sNode);

	BSTShowAll(bstRoot); printf("\n");
	sNode = BSTRemove(&bstRoot, 1);
	free(sNode);

	BSTShowAll(bstRoot); printf("\n");
	sNode = BSTRemove(&bstRoot, 6);
	free(sNode);

	BSTShowAll(bstRoot); printf("\n");
	return 0;
}