[자료구조] 이진 탐색 트리 (2)

CS/자료구조

[자료구조] 이진 탐색 트리 (2) - 구현

nowkoes 2023. 4. 20. 00:00

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

구현

　위의 검색 / 삽입 / 삭제의 특성을 가지는 BST를 구현하는 시간을 가지도록 하자.

#include <iostream>
using namespace std;

struct Node
{
	int _data;
	Node* _left, * _right;
};

　트리에 사용될 노드 구조체 Node를 선언한다.

class BST
{
	Node* _root;

public:
	BST() : _root(nullptr) {}

　이진 탐색 트리 클래스 BST를 선언하고, 기본 생성자를 통해 루트 노드를 nullptr로 초기화해 준다.

class BST
{
	...
	Node* Find_Implementation(Node* node, int value)
	{
		if (!node) // node가 존재하지 않는 경우
			return NULL;

		if (node->_data == value) // value를 찾은 경우
		{
			cout << value << "를 찾았습니다\n";
			return node;
		}

		if (value < node->_data) // value 값이 노드의 왼쪽에 있는 경우
		{
			cout << node->_data << "에서 왼쪽으로 이동\n";
			return Find_Implementation(node->_left, value);
		}

		cout << node->_data << "에서 오른쪽으로 이동\n"; // value 값이 노드의 오른쪽에 있는 경우
		return Find_Implementation(node->_right, value);
	}

public:
	
	...
	Node* Find(int value)
	{
		return Find_Implementation(_root, value);
	}

　주어진 원소를 찾는 Find() 함수다. 위의 탐색에서 알 수 있듯이, 원소 검색은 재귀적으로 동작하기 때문에 실제 구현 함수인 Find_Implementation() 함수를 private으로 선언하여 외부에서 직접 호출할 수 없도록 하였다.

　실제 구현 함수는 주어진 원소를 찾을 때까지 찾아야 할 원소와 현재 노드의 값을 비교하며 왼쪽 혹은 오른쪽으로 타고 내려가게 구현하였다.

class BST
{
	...
	void Insert_Implementation(Node* node, int value)
	{
		if (value < node->_data) // value가 왼쪽으로 가야 하는 경우
		{
			if (!node->_left) // node의 왼쪽 자식이 없을 때
				node->_left = new Node{ value, NULL, NULL };

			else // node의 왼쪽 자식이 있을 때
				Insert_Implementation(node->_left, value);
		}

		else // value가 오른쪽으로 가야하는 경우
		{
			if (!node->_right) // node의 오른쪽 자식이 비었을 때
				node->_right = new Node{ value, NULL, NULL };

			else
				Insert_Implementation(node->_right, value);
		}
	}

public:
	...
	void Insert(int value)
	{
		if (!_root) // 루트 노드가 없는 경우
			_root = new Node{ value, NULL, NULL };
		else
			Insert_Implementation(_root, value);
	}
};

　이번엔 값을 삽입하는 Insert() 함수다. 이 함수도 Find() 함수와 마찬가지로 재귀적으로 호출하기 때문에 실제로 구현한 함수 Insert_Implementation()은 private 멤버로 숨겼다.

　Insert_Implementation() 함수는 삽입할 값이 노드의 왼쪽 자식인지, 오른쪽 자식인지 판단하여 재귀적으로 호출하며, 값을 삽입할 노의 자식이 없을 경우 해당 자식 노드를 생성하여 값을 삽입하게 구현하였다.

class BST
{
	...
	void InOrder_Implementation(Node* node)
	{
		if (!node) // node가 존재하지 않는 경우
			return;

		// 중위 순회는 왼쪽 → 현재 → 오른쪽 순으로 방문
		InOrder_Implementation(node->_left);
		cout << node->_data << ' ';
		InOrder_Implementation(node->_right);
	}

public:
	...
	void InOrder()
	{
		InOrder_Implementation(_root);
	}

　다음은 왼쪽 노드, 현재 노드, 오른쪽 노드 순으로 순회하는 중위 순회를 구현한 InOrder(), InOrder_Implementation() 함수다. 순회에 대한 내용은 이전에 작성한 포스팅을 참고하도록 하자.

class BST
{
	...
	Node* Find_Successor_Implemetation(Node* node)
	{
		auto current = node->_right; // 후손 노드는 항상 오른쪽에서 시작

		while (current && current->_left) // 오른쪽 서브트리의 가장 왼쪽 노드를 찾을 때까지
			current = current->_left;

		return current;
	}

public:
	...
	Node* Find_Successor(Node* node)
	{
		return Find_Successor_Implemetation(node);
	}

　다음은 후손 노드를 찾는 함수다. 후손 노드의 정의에 따라 현재 노드의 오른쪽 서브트리로 이동한 후, 가장 작은 값이 되도록 찾아주면 된다.

class BST
{
	...
	Node* Delete_Implementation(Node* node, int value)
	{
		if (!node)
			return NULL;

		if (value < node->_data) // 왼쪽 노드인 경우 왼쪽으로 타고 들어가게 재귀 호출
			node->_left = Delete_Implementation(node->_left, value);

		else if (value > node->_data) // 오른쪽 노드인 경우 오른쪽으로 타고 들어가게 재귀 호출
			node->_right = Delete_Implementation(node->_right, value);

		else // 삭제하려는 노드를 찾았을 때
		{
			if (!node->_left) // 자식 노드가 없거나 왼쪽 자식만 없는 경우
			{
				auto tmp = node->_right;
				delete node;
				return tmp;
			}

			if (!node->_right) // 오른쪽 자식만 없는 경우
			{
				auto tmp = node->_left;
				delete node;
				return tmp;
			}

			auto successor = Find_Successor_Implemetation(node); // 후속 노드 찾기
			node->_data = successor->_data;

			// 오른쪽 서브 트리에서 후속 노드를 찾아 삭제
			node->_right = Delete_Implementation(node->_right, successor->_data);
		}

		return node;
	}

public:
	...
	void Delete(int value)
	{
		_root = Delete_Implementation(_root, value);
	}
};

　마지막으로 원소 삭제를 구현한 Delete() 함수다. 특정 노드를 삭제하고, 해당 노드의 부모 노드 포인터를 조정하는 방식이다.

int main()
{
	BST bst;
	bst.Insert(15);
	bst.Insert(13);
	bst.Insert(8);
	bst.Insert(14);
	bst.Insert(5);
	bst.Insert(10);
	bst.Insert(3);
	bst.Insert(7);
	bst.Insert(19);
	bst.Insert(17);
	bst.Insert(16);
	bst.Insert(18);
	bst.Insert(25);
	bst.Insert(30);
	
	cout << "중위 순회: "; bst.InOrder(); cout << endl;

	cout << "원소 3 찾기: ";
	bst.Find(3);

	cout << "원소 9 삽입 후 중위 순회" << endl;
	bst.Insert(9); bst.InOrder(); cout << endl;
	
	cout << "원소 15 삭제 후 중위 순회" << endl;
	bst.Delete(15); bst.InOrder();
}

　마지막으로 다음과 같이 main() 함수를 작성하고 실행해 보면 위의 예제들과 결과가 같다는 것을 알 수 있다.

총합본

#include <iostream>
using namespace std;

struct Node
{
	int _data;
	Node* _left, * _right;
};

class BST
{
	Node* _root;

	Node* Find_Implementation(Node* node, int value)
	{
		if (!node) // node가 존재하지 않는 경우
			return NULL;

		if (node->_data == value) // value를 찾은 경우
		{
			cout << value << "을(를) 찾았습니다\n";
			return node;
		}

		if (value < node->_data) // value 값이 노드의 왼쪽에 있는 경우
		{
			cout << node->_data << "에서 왼쪽으로 이동\n";
			return Find_Implementation(node->_left, value);
		}

		cout << node->_data << "에서 오른쪽으로 이동\n"; // value 값이 노드의 오른쪽에 있는 경우
		return Find_Implementation(node->_right, value);
	}

	void Insert_Implementation(Node* node, int value)
	{
		if (value < node->_data) // value가 왼쪽으로 가야 하는 경우
		{
			if (!node->_left) // node의 왼쪽 자식이 없을 때
				node->_left = new Node{ value, NULL, NULL };

			else // node의 왼쪽 자식이 있을 때
				Insert_Implementation(node->_left, value);
		}

		else // value가 오른쪽으로 가야하는 경우
		{
			if (!node->_right) // node의 오른쪽 자식이 비었을 때
				node->_right = new Node{ value, NULL, NULL };

			else
				Insert_Implementation(node->_right, value);
		}
	}

	void InOrder_Implementation(Node* node)
	{
		if (!node) // node가 존재하지 않는 경우
			return;

		// 중위 순회는 왼쪽 → 현재 → 오른쪽 순으로 방문
		InOrder_Implementation(node->_left);
		cout << node->_data << ' ';
		InOrder_Implementation(node->_right);
	}

	Node* Find_Successor_Implemetation(Node* node)
	{
		auto current = node->_right; // 후손 노드는 항상 오른쪽에서 시작

		while (current && current->_left) // 오른쪽 서브트리의 가장 왼쪽 노드를 찾을 때까지
			current = current->_left;

		return current;
	}

	Node* Delete_Implementation(Node* node, int value)
	{
		if (!node)
			return NULL;

		if (value < node->_data) // 왼쪽 노드인 경우 왼쪽으로 타고 들어가게 재귀 호출
			node->_left = Delete_Implementation(node->_left, value);

		else if (value > node->_data) // 오른쪽 노드인 경우 오른쪽으로 타고 들어가게 재귀 호출
			node->_right = Delete_Implementation(node->_right, value);

		else // 삭제하려는 노드를 찾았을 때
		{
			if (!node->_left) // 자식 노드가 없거나 왼쪽 자식만 없는 경우
			{
				auto tmp = node->_right;
				delete node;
				return tmp;
			}

			if (!node->_right) // 오른쪽 자식만 없는 경우
			{
				auto tmp = node->_left;
				delete node;
				return tmp;
			}

			auto successor = Find_Successor_Implemetation(node); // 후속 노드 찾기
			node->_data = successor->_data;

			// 오른쪽 서브 트리에서 후속 노드를 찾아 삭제
			node->_right = Delete_Implementation(node->_right, successor->_data);
		}

		return node;
	}

public:
	BST() : _root(nullptr) {}

	Node* Find(int value)
	{
		return Find_Implementation(_root, value);
	}

	void Insert(int value)
	{
		if (!_root) // 루트 노드가 없는 경우
			_root = new Node{ value, NULL, NULL };
		else
			Insert_Implementation(_root, value);
	}

	void InOrder()
	{
		InOrder_Implementation(_root);
	}

	Node* Find_Successor(Node* node)
	{
		return Find_Successor_Implemetation(node);
	}

	void Delete(int value)
	{
		_root = Delete_Implementation(_root, value);
	}
};

int main()
{
	BST bst;
	bst.Insert(15);
	bst.Insert(13);
	bst.Insert(8);
	bst.Insert(14);
	bst.Insert(5);
	bst.Insert(10);
	bst.Insert(3);
	bst.Insert(7);
	bst.Insert(19);
	bst.Insert(17);
	bst.Insert(16);
	bst.Insert(18);
	bst.Insert(25);
	bst.Insert(30);
	
	cout << "중위 순회: "; bst.InOrder(); cout << endl;

	cout << "원소 3 찾기: ";
	bst.Find(3);

	cout << "원소 9 삽입 후 중위 순회" << endl;
	bst.Insert(9); bst.InOrder(); cout << endl;
	
	cout << "원소 15 삭제 후 중위 순회" << endl;
	bst.Delete(15); bst.InOrder();
}

저작자표시 비영리 변경금지

'CS > 자료구조' 카테고리의 다른 글

[자료구조] 그래프 (0)	2023.04.24
[자료구조] 힙 (2)	2023.04.20
[자료구조] 이진 탐색 트리 (1) (0)	2023.04.19
[자료구조] 트리 순회(Tree traversal) (0)	2023.04.17
[자료구조] 트리(Tree) (0)	2023.04.17

현재글[자료구조] 이진 탐색 트리 (2) - 구현

개발일지