[C++] BST(이진 탐색 트리) 구현

CBST.h

#pragma once

// data 파트에 해당하는 구조체
template<typename T1, typename T2>
struct tPair
{
	T1 first;
	T2 second;
};

// 노드라는 데이터 타입 단위
template<typename T1, typename T2>
struct tBSTNode
{
	// data 파트(map에서는 pair라고 함.)를 가리키는 포인터
	tPair<T1, T2> pair;

	// 부모 노드를 가리키는 포인터
	tBSTNode* pParent;

	// 자식 노드를 가리키는 포인터
	tBSTNode* pLeftChild;
	tBSTNode* pRightChild;
};

template<typename T1, typename T2>
class CBST
{
private:
	// BST는 루트 노드만 알면 된다.
	tBSTNode<T1, T2>* m_pRoot;  // 루트 노드 주소
	int m_iCount;  // 데이터 개수

public:
	bool insert(const tPair<T1, T2>& _pair);

public:
	// 생성자
	CBST()
		: m_pRoot(nullptr)
		, m_iCount(0)
	{

	}

	// 루트 노드에 접근
	tBSTNode<T1, T2>* getRoot() const {
		return m_pRoot;
	}
};

template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tPair<T1, T2>& _pair)
{
	// pair를 넣을 수 있는 노드를 동적 할당하여 만든다.
	tBSTNode<T1, T2>* pNewNode = new tBSTNode<T1, T2>();
	// pair 부분 복사
	pNewNode->pair = _pair;
	pNewNode->pParent = nullptr;
	pNewNode->pLeftChild = nullptr;
	pNewNode->pRightChild = nullptr;

	// 첫 번째 데이터라면
	if (nullptr == m_pRoot)
	{
		// 만들어진 노드가 루트 노드가 되어야 한다.
		m_pRoot = pNewNode;
	}
	// 첫 번째 데이터가 아니라면
	else
	{
		// 루트 노드 값은 바뀌거나 훼손되면 안 되니까 지역 변수를 사용한다.
		tBSTNode<T1, T2>* pNode = m_pRoot;  // 루트 노드 주소를 받는다.

		// 루트 노드와 들어온 데이터를 pair의 first끼리 비교한다.
		// 언제까지 반복? => 들어온 데이터가 단말 노드가 될 때까지 비교하면서 내려간다.
		while (true)
		{
			// pNewNode : 새로 들어온 노드 / pNode : 현재 노드
			if (pNode->pair.first < pNewNode->pair.first)
			{
				// 오른쪽 자식이 null이면(비었으면)
				if (nullptr == pNode->pRightChild)
				{
					// 새로운 노드를 현재 노도의 오른쪽 자식으로 임명해주고 주소값을 넣어준다.
					pNode->pRightChild = pNewNode;
					// 현재 노드를 새로운 노드의 부모로 지정한다.
					pNewNode->pParent = pNode;
					// 자리를 찾아서 연결됐기 때문에 반복문을 빠져나간다.
					break;
				}
				else
				{
					// 새로 들어온 노드가 더 크다면 오른쪽으로 가야 하므로 노드를 오른쪽 포인터로 갱신한다.
					pNode = pNode->pRightChild;
				}
			}
			else if (pNode->pair.first > pNewNode->pair.first)
			{
				// 왼쪽 자식이 null이면(비었으면)
				if (nullptr == pNode->pLeftChild)
				{
					// 새로운 노드를 현재 노도의 왼쪽 자식으로 임명해주고 주소값을 넣어준다.
					pNode->pLeftChild = pNewNode;
					// 현재 노드를 새로운 노드의 부모로 지정한다.
					pNewNode->pParent = pNode;
					// 자리를 찾아서 연결됐기 때문에 반복문을 빠져나간다.
					break;
				}
				else
				{
					// 새로 들어온 노드가 더 작다면 왼쪽으로 가야 하므로 노드를 왼쪽 포인터로 갱신한다.
					pNode = pNode->pLeftChild;
				}
			}
			// 두 개가 같다면 (first값이 똑같다면, key값이 같다면)
			else
			{
				// 중복값을 허용하는 map은 multi map이라고 따로 있고, 일반적인 map은 중복을 허용하지 않는다.
				// 일반적인 map은 중복 key가 들어오면 트리에 넣지 않고 무시한다.
				// 중복 key가 발생해서 값이 안 들어갔는데 값이 들어갔다고 착각하는 경우가 있으므로 주의해야 한다.
					// find()로 값이 있는지 확인해봐야 한다.
				// multi map은 중복 key가 발생하면 리스트 구조로 같은 key값에 해당하는 노드를 연결짓는다.
				// key는 같지만 second는 다를 수도 있기 때문에 원하는 조건을 걸어서 찾으면 되는데,
				// 이렇게 되면 이진 탐색 트리를 구현한 효율이 없어진다.
				// 그래서 보통 multi map보다는 일반 map을 사용한다.

				// 반환값을 통해서 실패했다고 알리기 위해 템플릿에 bool을 붙였다.
				return false;
			}
		}
	}

	// 데이터 개수 증가
	++m_iCount;

	return true;
}

 

main.cpp

#include <iostream>
#include <map>  // Red/Black 이진 탐색 트리가 구현되어있는 자료구조
#include <set>
#include <string>  // 문자열 클래스 사용

#include "CBST.h"

using std::cout;
using std::endl;

// 성별
#define MAN 1
#define WOMAN 2

// 학생 정보 구조체
struct tStdInfo
{
	wchar_t szName[20];  // 이름
	unsigned char age;  // 나이
	unsigned char gender;  // 성별

	// 기본 생성자
	tStdInfo()
		:szName{}
		, age(0)
		, gender(0)
	{

	}

	// 생성자 오버로딩
	tStdInfo(const wchar_t* _pName, unsigned char _age, unsigned char _gender)
		:szName{}
		// szName{_pName}라고 하면 오류가 발생한다.
			// 배열 초기화는 wchar_t szArr[100] = L"abcdef"; 형태로는 가능한데,
			// 구조체 멤버는 _pName을 받아와서, 주소가 가리키는 곳에 있는 문자열을 멤버 내부 배열로 하나하나 옮겨와야 한다.
		, age(_age)
		, gender(_gender)
	{
		// wcscpy_s() : 문자열 복사 함수
		wcscpy_s(szName, _pName);  // 목적지(저장할 곳(멤버)), 가져올 원본
	}
};

// pair 구조체
struct pair
{
	const wchar_t* first;
	tStdInfo second;
};

// 내가 만든 클래스
class MyClass
{
private:
	int a;

public:
	bool operator < (const MyClass& _other) const
	{
		if (a < _other.a)
			return true;
		else
			return false;
	}
};

// 출력 함수
template <typename T1, typename T2>
void printBST(tBSTNode<T1, T2>* node) {
	if (node == nullptr)
		return;

	// 왼쪽 자식
	printBST(node->pLeftChild);

	// 현재 노드 출력
	cout << "Key: " << node->pair.first << ", Value: " << node->pair.second << endl;

	// 오른쪽 자식
	printBST(node->pRightChild);
}

int main()
{
	CBST<int, int> bstint;

	tPair<int, int> pair;

	pair.first = 100;
	pair.second = 0;
	bstint.insert(pair);

	pair.first = 150;
	pair.second = 15;
	bstint.insert(pair);

	pair.first = 50;
	pair.second = 5;
	bstint.insert(pair);

	// 출력
	printBST(bstint.getRoot());

	return 0;
}

▽ 출력 결과

Key: 50, Value: 5
Key: 100, Value: 0
Key: 150, Value: 15