[자료구조, C] 이진 탐색 트리(Binary Search Tree) 구현

<이진 탐색 트리(Binary Search Tree) 구현>

https://sevenshards.tistory.com/7

[자료구조, C] 양방향 연결 리스트 기반 이진 트리 구현

기존에 구현했던 이진 트리를 이용하되, 추가된 함수들이 있으므로 코드를 추가로 수록.

 

[BinaryTree.h]

/*
* 비선형 자료구조 - 연결 리스트 기반 이진 트리
* 파일명: BinaryTree.h
* 파일 버전: 0.3
* 작성자: Sevenshards
* 작성 일자: 2023-11-28
* 이전 버전 작성 일자: 2023-11-23
* 버전 내용: 왼쪽, 오른쪽 자식 노드 연결 변경 함수 추가 및 왼쪽, 오른쪽 자식 노드 제거 함수 추가
* 이전 버전 내용: 전위, 중위 순회 추가 및 순회 시 할 일을 결정할 수 있도록 함수 포인터 사용.
*/
// 저자의 표현을 빌리자면, 이진 트리를 구현"할 수 있는 도구"를 만드는 과정이다.
// 어디다 갖다 쓸 것인가는 나중에 생각하자.
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData; // 이진 트리의 데이터. 자료형은 편의상 int

// 이진 트리의 노드 구조체. 이중 연결 리스트 구조.
// 그리고 이 자체가 Tree다.
// 이전 선형 자료 구조에서는 리스트나 스택, 큐와 같은 경우는 노드 따로, 리스트, 스택, 큐를 따로 구조체를 정의하였다.
// 하지만 이건 노드임과 동시에 트리가 된다.
typedef struct _bTreeNode
{
	BTData data;
	struct _bTreeNode* left;
	struct _bTreeNode* right;
} BTreeNode;

// 노드의 생성 및 데이터 저장과 조회
BTreeNode* MakeBTreeNode(void); // 이진 트리의 노드 생성
BTData GetData(BTreeNode* bt); // 이진 트리 노드의 데이터를 반환 (Getter)
void SetData(BTreeNode* bt, BTData data); // 이진 트리 노드에 데이터를 저장 (Setter)

BTreeNode* GetLeftSubTree(BTreeNode* bt); // 왼쪽 서브 트리의 주소 값(왼쪽 서브 트리의 루트 노드)을 반환
BTreeNode* GetRightSubTree(BTreeNode* bt); // 오른쪽 서브 트리의 주소 값(오른쪽 서브 트리의 루트 노드)을 반환


// 노드의 연결 및 변경 (메모리 할당 해제 과정 포함)
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub); // 매개변수 sub로 전달된 트리 또는 노드를 매개변수 main의 왼쪽 서브트리로 연결
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub); // 매개 변수 sub로 전달된 트리 또는 노드를 매개변수 main의 오른쪽 서브트리로 연결

// 11.28 추가
// 메모리 소멸을 수반하지 않고 왼쪽, 오른쪽 자식 노드 변경
void ChangeLeftSubTree(BTreeNode* main, BTreeNode* sub); // 매개변수 sub로 전달된 트리 또는 노드를 매개변수 main의 왼쪽 서브트리로 연결
void ChangeRightSubTree(BTreeNode* main, BTreeNode* sub); // 매개 변수 sub로 전달된 트리 또는 노드를 매개변수 main의 오른쪽 서브트리로 연결

// 순회 (재귀를 이용하여 구현한다!)
// 함수 포인터를 선언 -> 이 부분에 대한 설명이 좀 더 필요하다.
typedef void VisitFuncPtr(BTData data);
// typedef void (*VisitFuncPtr)(BTData data); -> 이거랑 동일하다.
// 여기에 대해서 내용을 추가 정리해두겠다.
// typedef 선언이 없었다고 치면 현재 반환형은 void에 매개변수는 BTData형의 data를 받는 함수가 되고, 함수의 이름은 VisitFuncPtr이 된다.
// 그런데 여기서 typedef 선언이 추가되면, 함수의 이름이 아니라 "함수 포인터"로 인지를 하게 된다.
// 마치 배열이 연산식에 사용되면 포인터가 되는 것처럼 decay된다는 개념과 비슷하다.
// 그렇기 때문에 VisitFuncPtr이라는 이름을 자료형처럼 쓸 수 있는 것이다.

// 중위 순회 1)왼쪽 서브 트리 -> 2)루트 노드 -> 3)오른쪽 서브 트리
void InorderTraversal(BTreeNode* bt, VisitFuncPtr action);
// 전위 순회 1)루트 노드 -> 2)왼쪽 서브 트리 -> 3)오른쪽 서브 트리
void PreorderTraversal(BTreeNode* bt, VisitFuncPtr action);
// 후위 순회 1)왼쪽 서브 트리 -> 2)오른쪽 서브트리 -> 3)루트 노드
void PostorderTraversal(BTreeNode* bt, VisitFuncPtr action);

// 트리의 모든 노드 삭제
void DeleteTree(BTreeNode* bt);

// 11.28 추가
// 노드 삭제 부분
BTreeNode* RemoveLeftSubTree(BTreeNode* bt); // 왼쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소값 반환
BTreeNode* RemoveRightSubTree(BTreeNode* bt); // 오른쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소값 반환

#endif

 

[BinaryTree.c]

/*
* 비선형 자료구조 - 연결 리스트 기반 이진 트리
* 파일명: BinaryTree.c
* 파일 버전: 0.3
* 작성자: Sevenshards
* 작성 일자: 2023-11-28
* 이전 버전 작성 일자: 2023-11-23
* 버전 내용: 왼쪽, 오른쪽 자식 노드 연결 변경 함수 추가 및 왼쪽, 오른쪽 자식 노드 제거 함수 추가
* 이전 버전 내용: 전위, 중위 순회 추가 및 순회 시 할 일을 결정할 수 있도록 함수 포인터 사용.
*/
// 저자의 표현을 빌리자면, 이진 트리를 구현"할 수 있는 도구"를 만드는 과정이다.
// 어디다 갖다 쓸 것인가는 나중에 생각하자.
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"

// 노드의 생성 및 데이터 저장과 조회
BTreeNode* MakeBTreeNode(void) // 이진 트리의 노드 생성
{
	BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
	node->left = NULL;
	node->right = NULL;
	return node;
}

BTData GetData(BTreeNode* bt) // 이진 트리 노드의 데이터를 반환 (Getter)
{
	return bt->data;
}

void SetData(BTreeNode* bt, BTData data) // 이진 트리 노드에 데이터를 저장 (Setter)
{
	bt->data = data;
}

BTreeNode* GetLeftSubTree(BTreeNode* bt) // 왼쪽 서브 트리의 주소 값(왼쪽 서브 트리의 루트 노드)을 반환
{
	return bt->left;
}
BTreeNode* GetRightSubTree(BTreeNode* bt) // 오른쪽 서브 트리의 주소 값(오른쪽 서브 트리의 루트 노드)을 반환
{
	return bt->right;
}

// 노드의 연결 및 변경 (메모리 할당 해제 과정 포함)
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub) // 매개변수 sub로 전달된 트리 또는 노드를 매개변수 main의 왼쪽 서브트리로 연결
{
	if (main->left != NULL) // 이미 왼쪽에 연결된 트리나 노드가 있다면
		free(main->left); // 할당된 메모리를 해제한다.

	main->left = sub; // 그리고 새로 왼쪽에 연결한다.
}

void MakeRightSubTree(BTreeNode* main, BTreeNode* sub) // 매개 변수 sub로 전달된 트리 또는 노드를 매개변수 main의 오른쪽 서브트리로 연결
{
	if (main->right != NULL) // 이미 오른쪽에 연결된 트리나 노드가 있다면
		free(main->right); // 할당된 메모리를 해제한다.

	main->right = sub; // 그리고 새로 오른쪽에 연결한다.
}

// 11.28 추가
// 메모리 소멸을 수반하지 않고 왼쪽, 오른쪽 자식 노드 변경
void ChangeLeftSubTree(BTreeNode* main, BTreeNode* sub) // 매개변수 sub로 전달된 트리 또는 노드를 매개변수 main의 왼쪽 서브트리로 연결
{
	main->left = sub;
}

// 메모리 할당 해제 없이 main의 오른쪽 자식 노드를 변경
void ChangeRightSubTree(BTreeNode* main, BTreeNode* sub) // 매개 변수 sub로 전달된 트리 또는 노드를 매개변수 main의 오른쪽 서브트리로 연결
{
	main->right = sub;
}

// 순회 (재귀를 이용하여 구현한다!)
// 중위 순회 1)왼쪽 서브 트리 -> 2)루트 노드 -> 3)오른쪽 서브 트리
void InorderTraversal(BTreeNode* bt, VisitFuncPtr action)
{
	if (bt == NULL) // 만약 공집합 노드(NULL)이라면? 재귀의 탈출 조건이 된다.
		return;

	InorderTraversal(bt->left, action); // 1) 왼쪽 서브 트리를 순회
	action(bt->data); // 2) 루트 노드를 방문
	InorderTraversal(bt->right, action); // 3) 오른쪽 서브 트리를 순회
}
// 전위 순회 1)루트 노드 -> 2)왼쪽 서브 트리 -> 3)오른쪽 서브 트리
void PreorderTraversal(BTreeNode* bt, VisitFuncPtr action)
{
	if (bt == NULL) // 만약 공집합 노드(NULL)이라면? 재귀의 탈출 조건이 된다.
		return;

	action(bt->data); // 1) 루트 노드를 방문
	PreorderTraversal(bt->left, action); // 2) 왼쪽 서브 트리를 순회
	PreorderTraversal(bt->right, action); // 3) 오른쪽 서브 트리를 순회
}
// 후위 순회 1)왼쪽 서브 트리 -> 2)오른쪽 서브트리 -> 3)루트 노드
void PostorderTraversal(BTreeNode* bt, VisitFuncPtr action)
{
	if (bt == NULL) // 만약 공집합 노드(NULL)이라면? 재귀의 탈출 조건이 된다.
		return;

	PostorderTraversal(bt->left, action); // 1) 왼쪽 서브 트리를 순회
	PostorderTraversal(bt->right, action); // 2) 오른쪽 서브 트리를 순회
	action(bt->data); // 3) 루트 노드를 방문
}
// 트리의 모든 노드 삭제
void DeleteTree(BTreeNode* bt)
{
	if (bt == NULL) // 공집합 노드(NULL)이라면 재귀 탈출.
		return;

	// 후위 순회를 통해 왼쪽, 그리고 오른쪽, 마지막으로 루트 노드를 비우는 형태로 진행.
	DeleteTree(bt->left);
	DeleteTree(bt->right);

	printf("delete tree node data: %d\n", bt->data);
	free(bt);
}

// 11.28 추가
// 노드 삭제 부분
// 여기서 바로 free를 하는 것이 아니라, 해당 함수를 호출한 영역에서 free를 통해 할당한 메모리를 해제.
// 그래서 주소값을 반환하게 한 것.
BTreeNode* RemoveLeftSubTree(BTreeNode* bt) // 왼쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소값 반환
{
	BTreeNode* dNode = NULL; // 삭제될 노드, 일부 컴파일러에서는 초기화하지 않으면 에러를 띄우므로 NULL로 초기화

	if (bt != NULL) // 대상 노드가 있다면 (NULL이 아니라면)
	{
		dNode = bt->left; // 제거될 노드를 현재 노드의 왼쪽 자식 노드로
		bt->left = NULL; // 왼쪽 자식 노드는 NULL로 바꾸어 아무것도 가리키지 않는다
	}

	return dNode;
}

BTreeNode* RemoveRightSubTree(BTreeNode* bt) // 오른쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소값 반환
{
	BTreeNode* dNode = NULL; // 삭제될 노드, 일부 컴파일러에서는 초기화하지 않으면 에러를 띄우므로 NULL로 초기화

	if (bt != NULL) // 대상 노드가 있다면 (NULL이 아니라면)
	{
		dNode = bt->right; // 제거될 노드를 현재 노드의 왼쪽 자식 노드로
		bt->right = NULL; // 왼쪽 자식 노드는 NULL로 바꾸어 아무것도 가리키지 않는다
	}

	return dNode;
}

 

추가된 함수는 4개이며 다음과 같다.

// 메모리 할당 해제 없이 main의 왼쪽 자식 노드 변경
void ChangeLeftSubTree(BTreeNode* main, BTreeNode* sub)
{
	main->left = sub;
}

// 메모리 할당 해제 없이 main의 오른쪽 자식 노드를 변경
void ChangeRightSubTree(BTreeNode* main, BTreeNode* sub)
{
	main->right = sub;
}

// 노드 삭제 부분
// 여기서 바로 free를 하는 것이 아니라, 해당 함수를 호출한 영역에서 free를 통해 할당한 메모리를 해제.
// 그래서 주소값을 반환하게 한 것.
// 왼쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소값 반환
BTreeNode* RemoveLeftSubTree(BTreeNode* bt){
	BTreeNode* dNode = NULL; // 삭제될 노드, 일부 컴파일러에서는 초기화하지 않으면 에러를 띄우므로 NULL로 초기화

	if (bt != NULL) // 대상 노드가 있다면 (NULL이 아니라면)
	{
		dNode = bt->left; // 제거될 노드를 현재 노드의 왼쪽 자식 노드로
		bt->left = NULL; // 왼쪽 자식 노드는 NULL로 바꾸어 아무것도 가리키지 않는다
	}

	return dNode;
}

// 오른쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소값 반환
BTreeNode* RemoveRightSubTree(BTreeNode* bt){
	BTreeNode* dNode = NULL; // 삭제될 노드, 일부 컴파일러에서는 초기화하지 않으면 에러를 띄우므로 NULL로 초기화

	if (bt != NULL) // 대상 노드가 있다면 (NULL이 아니라면)
	{
		dNode = bt->right; // 제거될 노드를 현재 노드의 왼쪽 자식 노드로
		bt->right = NULL; // 왼쪽 자식 노드는 NULL로 바꾸어 아무것도 가리키지 않는다
	}

	return dNode;
}

 

왼쪽, 오른쪽 자식 노드 변경과 자식 노드를 트리에서 제거하되 주소값을 반환하는 방식을 추가하였다.

주소값을 반환하는 방식을 썼다는 것은 함수를 호출한 곳에서 할당 해제를 처리한다는 뜻이다.

 

[BinarySearchTree.h]

/*
* 비선형 자료구조 - 연결 리스트 기반 이진 탐색 트리
* 파일명: BinarySearchTree.h
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-28
* 이전 버전 작성 일자: 2023-11-28
* 버전 내용: 삭제 기능, 트리 전체 조회 추가로 구현
* 이전 버전 내용: 간단한 이진 탐색 트리 구현.
*/

#ifndef __BINARY_SEARCH_TREE_H__
#define __BINARY_SEARCH_TREE_H__

#include "BinaryTree.h"

typedef BTData BSTData; // 이진 트리에서 사용하는 데이터형 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

[BinarySearchTree.c]

/*
* 비선형 자료구조 - 연결 리스트 기반 이진 탐색 트리
* 파일명: BinarySearchTree.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-28
* 이전 버전 작성 일자: 2023-11-28
* 버전 내용: 삭제 기능, 트리 전체 조회 추가로 구현
* 이전 버전 내용: 간단한 이진 탐색 트리 구현.
*/
#include <stdlib.h>
#include "BinarySearchTree.h"

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

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode* bst)
{
	return bst->data;
}

// 이진 탐색 트리를 대상으로 데이터 저장 (노드 생성 포함)
void BSTInsert(BTreeNode** pRoot, BSTData data)
{
	BTreeNode* pNode = NULL; // 현재 노드 기준의 부모 노드
	BTreeNode* cNode = *pRoot; // 현재(current) 가리키는 노드, 루트 노드에서부터 시작하므로 루트 노드의 주소값으로 초기화
	BTreeNode* newNode = NULL; // 새로 생성될 노드

	// 새로 생성될 노드(새 데이터가 담길 노드)가 추가될 위치를 찾기
	while (cNode != NULL) // 현재 노드가 NULL이 아닐 때까지, 다시 말해서 새로운 노드가 추가될 위치를 찾을 때까지
	{
		if (data == GetData(cNode)) // 현재 노드의 데이터가 입력된 데이터와 같다면
			return; // 데이터(키)의 중복을 허용하지 않으므로 return

		// 데이터 중복 검사가 끝난 후
		pNode = cNode; // 현재 노드 위치를 현재 위치한 노드의 부모 노드로 갱신

		if (data < GetData(cNode)) // 추가할 데이터가 현재 노드의 데이터보다 작다면
			cNode = GetLeftSubTree(cNode); // 왼쪽으로 이동
		else // 추가할 데이터가 현재 노드의 데이터보다 크다면
			cNode = GetRightSubTree(cNode); // 오른쪽으로 이동
	}

	// 위치를 찾은 후, 해당 위치에 새로운 노드 생성하고 추가
	newNode = MakeBTreeNode(); // 새로운 노드를 생성
	SetData(newNode, data); // 새로운 노드에 데이터 저장

	// 새로 생성될 위치(cNode)의 부모노드(pNode)의 자식 노드로 추가
	if (pNode != NULL) // 새로 생성될 노드가 루트 노드(루트 노드는 부모 노드가 없으므로)가 아니라면
	{
		if (data < GetData(pNode)) // 부모 노드가 가진 데이터보다 새로운 노드의 데이터가 작다면
			MakeLeftSubTree(pNode, newNode); // 왼쪽으로 새 노드를 연결
		else // 부모 노드가 가진 데이터보다 새로운 노드의 데이터가 크다면
			MakeRightSubTree(pNode, newNode); // 오른쪽으로 새 노드를 연결
	}
	else // 만약 새로 생성되는 노드가 루트 노드라면
		*pRoot = newNode; // 새로운 노드가 루트 노드가 된다.
}

// 이진 탐색 트리를 대상으로 데이터 탐색
BTreeNode* BSTSearch(BTreeNode* bst, BSTData target)
{
	BTreeNode* cNode = bst; // 현재(current) 가리키는 노드, 트리의 주소값(루트 노드의 주소값)부터 시작한다.
	BSTData cData; // 현재 가리키는 노드의 데이터 값

	// 현재 가리키는 노드가 NULL이 아닐때까지
	while (cNode != NULL)
	{
		cData = GetData(cNode);

		if (target == cData) // 대상을 찾았다면
			return cNode; // 현재 가리키는 노드의 주소값 반환
		else if (target < cData) // 찾는 값이 현재 노드의 데이터보다 작다면
			cNode = GetLeftSubTree(cNode); // 왼쪽으로 이동
		else // 찾는 값이 현재 노드의 데이터보다 크다면
			cNode = GetRightSubTree(cNode);
	}

	return NULL; // 탐색 대상이 아예 없는 경우, NULL을 반환
}

// 트리에서 노드를 제거하고 제거된 노드의 주소값을 반환
BTreeNode* BSTRemove(BTreeNode** pRoot, BSTData target)
{
	// 삭제 대상이 루트 노드일 경우도 고려하여 진행
	BTreeNode* pVRoot = MakeBTreeNode(); // 가상 루트 노드 (Virtual Root Node) - 저자가 쓴 꼼수(?)
	BTreeNode* pNode = pVRoot; // 현재 가리키는 노드의 부모 노드, 초기화 하면서 가상의 루트 노드를 가리킨다
	BTreeNode* cNode = *pRoot; // 현재(current) 가리키는 노드, 초기화 하면서 루트 노드를 가리킨다
	BTreeNode* dNode = NULL; // 지워질 대상의 노드, 일부 컴파일러에서는 초기화하지 않으면 에러를 띄우므로 NULL로 초기화

	// 루트 노드를 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; // NULL을 return

	dNode = cNode; // 삭제 대상을 dNode가 가리키게 함

	// 1번 케이스: 삭제 대상이 단말 노드라면
	if (GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL) // 양쪽에 자식 노드가 둘 다 없으므로
	{
		if (GetLeftSubTree(pNode) == dNode) // 만약 삭제할 노드의 부모 노드의 왼쪽 노드라면
			RemoveLeftSubTree(pNode); // 부모 노드의 왼쪽 노드를 삭제
		else // 오른쪽 노드라면
			RemoveRightSubTree(pNode); // 부모 노드의 오른쪽 노드를 삭제
	}

	// 2번 케이스: 삭제 대상이 자식 노드를 하나 갖는 경우
	else if (GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL) // 삭제할 노드의 왼쪽 또는 오른쪽에 자식 노드가 있다면
	{
		BTreeNode* dcNode; // 삭제 대상 노드의 자식(child) 노드를 가리키기 위해 사용할 BTreeNode* 변수

		if (GetLeftSubTree(dNode) != NULL) // 삭제할 노드의 왼쪽에 자식 노드가 있다면
			dcNode = GetLeftSubTree(dNode); // dcNode가 삭제할 노드의 왼쪽 자식을 가리키게 한다.
		else // 삭제할 노드의 오른쪽에 자식 노드가 있다면
			dcNode = GetRightSubTree(dNode); //dcNode가 삭제할 노드의 오른쪽 자식을 가리키게 한다.

		if (GetLeftSubTree(pNode) == dNode) // 만약 삭제할 노드의 부모 노드의 왼쪽 노드라면
			ChangeLeftSubTree(pNode, dcNode); // 부모 노드의 왼쪽을 삭제할 노드의 자식 노드로 바꾼다.
		else // 오른쪽 노드라면
			ChangeRightSubTree(pNode, dcNode); // 부모 노드의 오른쪽을 삭제할 노드의 자식 노드로 바꾼다.
	}

	// 3번 케이스: 삭제 대상이 양쪽 다 자식 노드를 갖는 경우
	// 이 경우에는 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 지니는 노드를 찾는다.
	// 그리고 가장 작은 값을 지니는 노드를 삭제할 노드를 대체한다.
	else
	{
		BTreeNode* mNode = GetRightSubTree(dNode); // 대체할 노드를 가리킨다. 오른쪽 서브트리에서 가장 작은 값을 찾아야 하니 오른쪽 자식 노드 값으로 초기화
		BTreeNode* mpNode = dNode; // 대체할 노드의 부모 노드. 삭제할 노드를 가리키는 것으로 초기화
		int delData; // 삭제할 노드의 데이터를 받기 위한 변수

		// 삭제 노드를 대체할 노드를 찾는다.
		while (GetLeftSubTree(mNode) != NULL) // 가장 작은 값을 찾는 것이므로 계속 왼쪽 서브트리만 찾으면 됨. 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; // 삭제 노드의 주소값 반환
}

// int형 데이터의 출력을 위한 함수
void ShowIntData(int data)
{
	printf("%d ", data);
}

// 이진 탐색 트리에 저장된 모든 노드의 데이터 출력
void BSTShowAll(BTreeNode* bst)
{
	InorderTraversal(bst, ShowIntData);
}

[BinarySearchTreeMain.c]

/*
* 비선형 자료구조 - 연결 리스트 기반 이진 탐색 트리
* 파일명: BinarySearchTreeMain.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-28
* 이전 버전 작성 일자: 2023-11-28
* 버전 내용: 삭제 기능, 트리 전체 조회 추가로 구현
* 이전 버전 내용: 간단한 이진 탐색 트리 구현.
*/

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

int main()
{
	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;
}

 

[탐색에 효율적인 이진 트리]

이진 트리는 탐색에 효율적인 자료 구조이다.
이진 트리의 경우에는 데이터의 저장이나 탐색, 삭제의 시간 복잡도가 $O(log_2n)$이므로 굉장히 효율적이다.
쉽게 예를 들면 데이터가 10억개 저장되어 있는 연결 리스트와 이진 트리가 있다고 가정해보면 바로 비교가 가능하다.
내가 찾고자 하는 데이터가 5억번째에 있다는 사실을 알고 있다면, 연결 리스트는 약 5억개의 노드를 지나야 한다.
하지만, 이진 트리는 위치를 알고 있다면 단말 노드까지 30개 정도의 노드만 지나는 과정에서 값을 찾을 수 있다.

[이진 탐색 트리의 이해]

이진 탐색 트리는 ‘탐색에 효율적인 자료구조’이다.
이름만 봐도 알 수 있을만큼 ‘이진 탐색 트리’는 ‘이진 트리’의 일종이며, 탐색에 특화된 자료구조다.
“이진 탐색 트리는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.”
쉽게 말하면 [이진 탐색 트리 = 이진 트리 + 데이터 저장 규칙] 이라고 볼 수 있다.

 

데이터가 저장되는 규칙은 다음과 같다.
열혈 C 자료구조의 저자도 편의상 탐색 키는 정수라고 가정했고, 탐색 키를 간단히 키(key)라고 표현했다.

1) 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
2) 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
3) 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리다.

 

1의 규칙은 키가 중복이 안됨을 뜻하며, 데이터베이스에서의 Primary Key와 같은 개념이라고 이해하면 될 것 같다.
2와 3의 규칙에 의해서

[왼쪽 서브 트리의 모든 키 < 루트 노드의 키 < 오른쪽 서브 트리의 모든 키]
[왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키]

가 항상 일치하게 된다.
그리고 4의 규칙으로 재귀적인 구조를 가진다는 것을 알 수 있다.

[이진 탐색 트리에서의 삽입과 탐색]

이진 탐색 트리에서 삽입과 탐색은 굉장히 단순하다.
[작으면 왼쪽, 크면 오른쪽으로]라는 룰만 따르면 된다.
그래서 노드를 삽입할 때에는 루트 노드부터 비교를 시작해서 자기 자리를 찾으면 된다.
탐색 또한 루트 노드부터 시작해서 위의 룰만 따라 원하는 값을 찾아가면 된다.
하지만, 삭제 부분은 좀 신경을 써야하는 부분이 많으므로 상대적으로 어렵다.

[이진 탐색 트리에서의 삭제]

이진 탐색 트리에서 노드의 삭제가 어려운 이유는 바로 이거다.
“이진 탐색 트리에서 임의의 노드를 삭제하는 경우, 삭제 후에도 이진 탐색 트리가 유지되도록 빈 자리를 채워야 한다.”
이전에 힙에서도 힙의 구조를 유지하기 위해 삽입과 삭제 부분에서 신경을 썼었다.
힙은 루트 노드의 값(또는 우선 순위)이 가장 커야(작아야) 하고, 모든 노드는 자식 노드보다 값이 커야(작아야)한다.
그래서 힙의 삽입과 삭제 과정에서 구조를 유지하는 것을 중점으로 구현을 했었다.
여기서는 삽입과 탐색은 크게 걸리는 부분이 없다.
하지만 삭제의 경우에는 크게 세 가지의 경우를 놓고 삭제를 진행해야 한다.

1) 삭제할 노드가 단말 노드(자식 노드가 아예 없는 경우)
2) 삭제할 노드에 자식 노드가 하나 있는 경우 (왼쪽 혹은 오른쪽)
3) 삭제할 노드에 자식 노드가 둘 다 있는 경우 (왼쪽과 오른쪽 둘 다)

그리고 루트 노드를 삭제하게 되는 경우까지 따지면 최대 6가지의 경우의 수를 가지게 된다.
열혈 C 자료구조의 저자는 약간의 꼼수(?)를 통해서 3가지 케이스만 가지고 일반화를 시켰다.
해당 부분은 코드에 주석으로 달아뒀으니 천천히 이해하면 좋을 것 같다.
특히 그림을 그려가면서 이해하는 것이 가장 좋다.

1) 삭제할 노드가 단말 노드(자식 노드가 아예 없는 경우)

가장 편한 케이스다.
이 때는 그냥 단말 노드만 삭제하면 끝이 나기 때문이다.
별 다른 조건을 확인할 필요가 없다.

2) 삭제할 노드에 자식 노드가 하나 있는 경우 (왼쪽 혹은 오른쪽)

여기서부터는 약간 머리를 써야한다.
삭제할 대상 노드를 기준으로 삭제할 대상 노드의 부모 노드의 왼쪽 자식이었는지, 오른쪽 자식이었는지를 알 필요가 있다.
그리고 삭제할 대상 노드가 가지고 있던 자식 노드는 삭제할 대상 노드를 대체하게 된다.
이때 부모 노드의 왼쪽 자식이었다면 왼쪽으로, 오른쪽 자식이었다면 오른쪽 자식 노드로 대체된다.
삭제 대상의 자식 노드가 삭제 대상을 기준으로 왼쪽 자식이었는지 오른쪽 자식이었는지는 중요하지 않다.
삭제될 노드를 대체하면서 삭제 대상의 부모 노드 입장에서 어느쪽 자식이었는지를 기준으로 하기 때문이다.

3) 삭제할 노드에 자식 노드가 둘 다 있는 경우 (왼쪽과 오른쪽 둘 다)

이제 진짜로 신경을 써야하는 부분이다.
가장 먼저 대체할 노드를 대체할 후보로 무엇을 정할 것인가부터 정해야 한다.
여기서도 두 가지 경우로 나뉜다.

- 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 값(서브 트리의 가장 오른쪽 자식 노드 값)으로 대체
- 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 값(서브 트리의 가장 왼쪽 자식 노드 값)으로 대체

어느 쪽을 택하더라도 이진 탐색 트리의 구조는 유지가 된다.
책의 저자는 후자의 방법을 택했으므로, 나도 후자의 방법을 채택했다.

그리고 삭제가 이뤄지는 방식은 다음과 같다.

 

1 - 삭제 대상이 되는 노드를 대체할 노드를 찾는다.
2 - 삭제 대상이 되는 노드에 대체가 되는 노드의 값을 대입한다.
3 - 대체할 노드의 부모 노드와 대체할 노드의 자식 노드(실제로 노드가 있거나, NULL이거나)를 연결한다.

여기서 포인트는 대체할 노드의 자식 노드는 ‘항상 오른쪽에 있다’는 것이다.
그 이유는 ‘삭제 대상의 노드의 오른쪽 서브 트리에서 가장 작은 값’을 택했기 때문이다.
그래서 만약 자식노드가 있다면 오른쪽에 있을 수 밖에 없다.
추가로 실제 구현 부분에서는 삭제 함수에서 가상의 루트 노드를 만들어서 사용한다.
그리고 가상의 루트 노드에 실제 루트 노드를 오른쪽 자식으로 만들고 진행하게 된다.
이렇게 되면 루트 노드를 삭제하는 경우에도 일반적인 노드 삭제와 동일하게 일반화하여 진행할 수 있다.