[Algorithm] 이진 탐색 트리

이번글은 이진 탐색 트리(Binary Search Tree)에 대해 알아보고 구현을 해보도록 하겠습니다.

이번글의 BST는 균형의 개념이 안 들어간 BST입니다.

(다음글에 균형잡는 AVL 트리를 이어서 적도록 하겠습니다.)

---

먼저 이진탐색 트리의 개념부터 살펴보도록 하겠습니다.

BST는 이진트리의 확장된 버전입니다.

(힙도 이진트리의 일종이지만 힙은 "완전 이진 트리"입니다.)

이진트리는 자식노드를 두개를 가지는 자료구조입니다. 이진트리를 기반으로 구현되어 있고 데이터를 빠르게 찾는데에 최적화 되어 있습니다. O(Log 2)를 탐색하는데 가집니다.

 

BST의 핵심은 "삽입", "탐색", "삭제"입니다.

 

삽입의 핵심로직을 살펴보면 Root보다 값이 작다면 왼쪽에 데이터를 삽입하고 Root보다 값이 크다면 오른쪽에 삽입합니다. Root의 왼쪽으로 가야하는데 왼쪽에 자식노드가 있다면 왼쪽 자식노드와 비교를 진행합니다.

오른쪽도 마찬가지입니다. 위의 핵심 로직을 "재귀적"으로 진행합니다.

 

탐색의 핵심로직은 찾으려고하는 값 target과 Root를 비교하여 Root보다 작다면 왼쪽자식 노드와 비교하고 Root보다 크다면 오른쪽 자식 노드와 비교를 진행합니다.

삽입과 마찬가지로 재귀적으로 반복합니다.

 

그다음으로 가장 까다로운 삭제의 핵심로직입니다.

삭제의 경우 상황이 3가지로 나뉩니다.

상황1 : 삭제하려는 노드의 자식이 하나도 존재하지 않는 경우

상황2 : 삭제하려는 노드의 자식이 하나만 존재하는 경우

상황3 : 삭제하려는 노드의 자식이 둘다 존재하는 경우

이렇게 3가지로 나눌 수 있습니다.

 

상황1의 경우 그냥 바로 삭제하려는 노드를 삭제를 해버리면됩니다.

상황2의 경우 삭제하려는 노드의 자식 노드를 삭제하려는 노드의 부모노드와 삭제후 연결하여 줍니다.

상황3의 경우에는 고려해야 할 부분이 조금 있는데...삭제할 노드를 삭제한 후에 누가 대체제가 될지를 선택해야하는 문제가 있습니다.

상황1, 2, 3이든 삭제후에도 완전이진트리 구조를 유지해야 하기 때문에 상황3의 경우에는

1. 왼쪽 서브트리에서 가장 큰값을 삭제할 노드의 대체자로 삼는다.

2. 오른쪽 서브트리에서 가장 작은 값을 삭제할 노드의 대체자로 삼는다.

위 처럼 두가지의 "유효"한 방법이 있습니다.

 

저는 2번 오른쪽 서브트리에서 가장 작은 값을 가지는 노드를 삭제할 노드의 대체자로 삼는 방법을 선택해서 BST의 삭제함수를 구현하도록 하겠습니다.

또한 중요한게 구현의 편의성을 위해 삭제할 노드를 바로 delete하지 않고 대체노드의 값을 삭제할 노드의 값에 "대입"하는 식으로 구현한뒤 대체노드를 return하여 호출한 쪽에서 메모리를 delete하도록 하였습니다.(코드에서는 deleteNode입니다 대체노드가)

(Effective C++을 읽으면 이런식의 구조는 좋지 않다고 나와있는데 구현의 편의를 위해 일단을 이렇게 하도록 하겠습니다.)

 

이진탐색트리는 이진트리의 확장된 버젼이기 때문에 이진트리를 먼저 구현해야하지만 제가 직접 구현한 아래의 링크를 통해서 이진트리의 코드를 확인해주시기 바랍니다 :)

https://www.notion.so/BinaryTree3-a300583fe53f4353b41bb1e4f5c40c48

 

위의 이진트리를 기반으로 이진탐색트리를 구현하도록 하겠습니다.

 

먼저 헤더파일 입니다.

BST2.h

#pragma once
#include "BinaryTree3.h"
namespace BST2
{
	typedef BT3::BTData BSTData;
	typedef BT3::BTN BTreeNode;

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

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

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

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

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

	void ShowIntData(int data);

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

BinaryTree의 BT3::BTN을 typedef로 걸어두었습니다.

그리고 각 함수의 설명은 주석을 보시면 될거같습니다.

 

BST2.cpp

 

먼저 아래는 삽입함수입니다.

로직은 간단합니다.

루트노드부터 시작해서 어디에 데이터가 저장될지 저장될 위치를 while을 통해서 찾습니다.

찾았다면 노드를 생성한뒤 해당 위치에 데이터를 집어넣습니다.

그리고 부모 노드에 자식으로 연결하여 줍니다.

(마지막에 루트노드인 경우의 예외처리도 있습니다.)

void BST2::BSTInsert(BTreeNode** pRoot, BSTData data)
{
	BTreeNode* parentNode = nullptr;
	BTreeNode* currentNode = *pRoot;
	BTreeNode* newNode = nullptr;

	// 새로운 노드가 (새 데이터가 담긴 노드가) 추가될 위치를 찾는다.
	while (currentNode != nullptr)
	{
		// 데이터의 중복을 허용하지 않는다.
		if (data == BT3::GetData(currentNode)) return;

		parentNode = currentNode;

		if (BT3::GetData(currentNode) > data) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	// parentNode의 자식노드로 추가할 새 노드의 생성
	newNode = BT3::MakeBTreeNode(); // 새 노드 생성
	SetData(newNode, data);			// 새노드에 데이터 저장
	
	// parentNode의 자식 노드로 새 노드르 추가
	if (parentNode != nullptr)
	{
		if (data < BT3::GetData(parentNode)) BT3::MakeLeftSubTree(parentNode, newNode);
		else BT3::MakeRightSubTree(parentNode, newNode);
	}
	// 새 노드가 루트 노드라면은
	else
	{
		*pRoot = newNode;
	}
}

 

그다음은 탐색 함수입니다.

BST2::BTreeNode* BST2::BSTSearch(BTreeNode* bst, BSTData target)
{
	BTreeNode* currentNode = bst;
	BSTData cd; // currentData

	while (currentNode != nullptr)
	{
		cd = BT3::GetData(currentNode);

		if (target == cd) return currentNode;
		else if (target < cd) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	return nullptr;
}

삽입과 로직이 비슷합니다. 현재 target의 값을 루트 노드부터 비교하여 줍니다. 일치하는 데이터가 있다면 반환합니다.

 

마지막으로 삭제함수 입니다.

BST2::BTreeNode* BST2::BSTRemove(BTreeNode** pRoot, BSTData target)
{
	// 삭제 대상이 루트 노드인 경우를 별도로 고려해야함.
	BTreeNode* pvRoot = BT3::MakeBTreeNode(); // 가상 루트 노드
	BTreeNode* parentNode = pvRoot; // parentNode
	BTreeNode* currentNode = *pRoot;
	BTreeNode* deleteNode = nullptr;

	// 루트 노드를 pvRoot가 가르키는 노드의 오른족 자식 노드가 되게한다.
	BT3::ChangeRightSubTree(pvRoot, *pRoot);

	// 삭제 대상인 노드를 탐색
	while (currentNode != nullptr && BT3::GetData(currentNode) != target)
	{
		parentNode = currentNode;
		if (target < BT3::GetData(currentNode)) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	// 찾을 대상이 존재하지 않는다면
	if (currentNode == nullptr) return nullptr;
	
	// 삭제 대상을 deleteNode가 가르키게 한다.
	deleteNode = currentNode;

	// 첫번째 경우 : 삭제 대상이 단말 노드인경우
	if (BT3::GetLeftSubTree(deleteNode) == nullptr && BT3::GetRightSubTree(deleteNode) == nullptr)
	{
		if (BT3::GetLeftSubTree(parentNode) == deleteNode) BT3::RemoveLeftSubTree(parentNode);
		else BT3::RemoveRightSubTree(parentNode);
	}
	// 두번째 경우 : 삭제 대상이 하나의 자식 노드를 갖는경우
	else if (BT3::GetLeftSubTree(deleteNode) == nullptr || BT3::GetRightSubTree(deleteNode) == nullptr)
	{
		// 삭제 대상의 자식 노드를 가르킴
		BTreeNode* deleteChildNode = nullptr;

		if (BT3::GetLeftSubTree(deleteNode) != nullptr) deleteChildNode = BT3::GetLeftSubTree(deleteNode);
		else deleteChildNode = BT3::GetRightSubTree(deleteNode);

		if (BT3::GetLeftSubTree(parentNode) == deleteNode) BT3::ChangeLeftSubTree(parentNode, deleteChildNode);
		else BT3::ChangeRightSubTree(parentNode, deleteChildNode);
	}
	// 세번째 경우 : 두 개의 자식 노드를 모두 갖는 경우
	else
	{
		// 대체 노드를 가르킴
		BTreeNode* mNode = BT3::GetRightSubTree(deleteNode);
		
		// 대체 노드의 부모 노드를 가르킴
		BTreeNode* mpNode = deleteNode;
		int delData = -1;
		
		// 삭제 대상의 대체 노드를 찾는다.
		while (BT3::GetLeftSubTree(mNode) != nullptr)
		{
			mpNode = mNode;
			mNode = BT3::GetLeftSubTree(mNode);
		}

		// 대체 노드에 저장된 값을 삭제할 노드에 대입한다.
		delData = BT3::GetData(deleteNode);				// 대입전 데이터 백업
		BT3::SetData(deleteNode, BT3::GetData(mNode));	// 대입 진행

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

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

	// 삭제된 노드가 루트 노드인 경우에 대한 추가적인 처리
	if (BT3::GetRightSubTree(pvRoot) != *pRoot) *pRoot = BT3::GetRightSubTree(pvRoot); // 루트 노드의 변경을 반영

	delete pvRoot;
	return deleteNode;
}

한가지 살펴볼 부분은 가상루트 노드의 개념이 들어가 있는데 이는 만약 삭제하려는 노드가 루트 노드인경우에 대한 예외 처리용으로 만들어놓은 가상루트 노드입니다.

 

루트를 삭제하는 경우에도 어쨋든 오른쪽 서브트리에서 가장 작은 값을 찾아 대체노드를 삼은뒤 이를 루트노드에 값을 대입하여야 합니다. 이또한 구현의 편의를 위해 만들어 놓은 함수입니다.

저도 처음에 가상루트노드의 개념이 이해가 안갔는데 그림을 그리며 이해를 하니 이해가 되었던거 같습니다.ㅎㅎ

 

아래는 BST2.cpp전체 코드입니다.

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

void BST2::BSTMakeAndInit(BTreeNode** pRoot)
{
	*pRoot = nullptr;
}

BST2::BSTData BST2::BSTGetNodeData(BTreeNode* bt)
{
	return BT3::GetData(bt);
}

void BST2::BSTInsert(BTreeNode** pRoot, BSTData data)
{
	BTreeNode* parentNode = nullptr;
	BTreeNode* currentNode = *pRoot;
	BTreeNode* newNode = nullptr;

	// 새로운 노드가 (새 데이터가 담긴 노드가) 추가될 위치를 찾는다.
	while (currentNode != nullptr)
	{
		// 데이터의 중복을 허용하지 않는다.
		if (data == BT3::GetData(currentNode)) return;

		parentNode = currentNode;

		if (BT3::GetData(currentNode) > data) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	// parentNode의 자식노드로 추가할 새 노드의 생성
	newNode = BT3::MakeBTreeNode(); // 새 노드 생성
	SetData(newNode, data);			// 새노드에 데이터 저장
	
	// parentNode의 자식 노드로 새 노드르 추가
	if (parentNode != nullptr)
	{
		if (data < BT3::GetData(parentNode)) BT3::MakeLeftSubTree(parentNode, newNode);
		else BT3::MakeRightSubTree(parentNode, newNode);
	}
	// 새 노드가 루트 노드라면은
	else
	{
		*pRoot = newNode;
	}
}

BST2::BTreeNode* BST2::BSTSearch(BTreeNode* bst, BSTData target)
{
	BTreeNode* currentNode = bst;
	BSTData cd; // currentData

	while (currentNode != nullptr)
	{
		cd = BT3::GetData(currentNode);

		if (target == cd) return currentNode;
		else if (target < cd) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	return nullptr;
}

BST2::BTreeNode* BST2::BSTRemove(BTreeNode** pRoot, BSTData target)
{
	// 삭제 대상이 루트 노드인 경우를 별도로 고려해야함.
	BTreeNode* pvRoot = BT3::MakeBTreeNode(); // 가상 루트 노드
	BTreeNode* parentNode = pvRoot; // parentNode
	BTreeNode* currentNode = *pRoot;
	BTreeNode* deleteNode = nullptr;

	// 루트 노드를 pvRoot가 가르키는 노드의 오른족 자식 노드가 되게한다.
	BT3::ChangeRightSubTree(pvRoot, *pRoot);

	// 삭제 대상인 노드를 탐색
	while (currentNode != nullptr && BT3::GetData(currentNode) != target)
	{
		parentNode = currentNode;
		if (target < BT3::GetData(currentNode)) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	// 찾을 대상이 존재하지 않는다면
	if (currentNode == nullptr) return nullptr;
	
	// 삭제 대상을 deleteNode가 가르키게 한다.
	deleteNode = currentNode;

	// 첫번째 경우 : 삭제 대상이 단말 노드인경우
	if (BT3::GetLeftSubTree(deleteNode) == nullptr && BT3::GetRightSubTree(deleteNode) == nullptr)
	{
		if (BT3::GetLeftSubTree(parentNode) == deleteNode) BT3::RemoveLeftSubTree(parentNode);
		else BT3::RemoveRightSubTree(parentNode);
	}
	// 두번째 경우 : 삭제 대상이 하나의 자식 노드를 갖는경우
	else if (BT3::GetLeftSubTree(deleteNode) == nullptr || BT3::GetRightSubTree(deleteNode) == nullptr)
	{
		// 삭제 대상의 자식 노드를 가르킴
		BTreeNode* deleteChildNode = nullptr;

		if (BT3::GetLeftSubTree(deleteNode) != nullptr) deleteChildNode = BT3::GetLeftSubTree(deleteNode);
		else deleteChildNode = BT3::GetRightSubTree(deleteNode);

		if (BT3::GetLeftSubTree(parentNode) == deleteNode) BT3::ChangeLeftSubTree(parentNode, deleteChildNode);
		else BT3::ChangeRightSubTree(parentNode, deleteChildNode);
	}
	// 세번째 경우 : 두 개의 자식 노드를 모두 갖는 경우
	else
	{
		// 대체 노드를 가르킴
		BTreeNode* mNode = BT3::GetRightSubTree(deleteNode);
		
		// 대체 노드의 부모 노드를 가르킴
		BTreeNode* mpNode = deleteNode;
		int delData = -1;
		
		// 삭제 대상의 대체 노드를 찾는다.
		while (BT3::GetLeftSubTree(mNode) != nullptr)
		{
			mpNode = mNode;
			mNode = BT3::GetLeftSubTree(mNode);
		}

		// 대체 노드에 저장된 값을 삭제할 노드에 대입한다.
		delData = BT3::GetData(deleteNode);				// 대입전 데이터 백업
		BT3::SetData(deleteNode, BT3::GetData(mNode));	// 대입 진행

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

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

	// 삭제된 노드가 루트 노드인 경우에 대한 추가적인 처리
	if (BT3::GetRightSubTree(pvRoot) != *pRoot) *pRoot = BT3::GetRightSubTree(pvRoot); // 루트 노드의 변경을 반영

	delete pvRoot;
	return deleteNode;
}

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

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

 

 

감사합니다.

틀린 부분이 있다면 바로 고치도록 하겠습니다!

(해당 구현은 윤성우의 열혈 자료구조 C를 참고하였습니다)