이진 탐색 트리 (BST)

 

 

 

예시 코드

 

코드 구조 : 노드, 이진탐색트리 (삽입,찾기,삭제 함수 포함), 데이터 비교 함수, 메인 함수

 

 

// 노드

template<class datatype>
class Node
{
public:
	Node() = default;
	Node(datatype data_in)
	{
		_data = data_in;
	};
	~Node() 
	{
		if (_left_node != nullptr)
		{
			_left_node = nullptr;
		}

		if (_right_node != nullptr)
		{
			_right_node = nullptr;
		}

		if (_parent_node != nullptr)
		{
			_parent_node = nullptr;
		}
		
	};
public:
	datatype _data;
	Node* _parent_node = nullptr;
	Node* _left_node = nullptr;
	Node* _right_node = nullptr;
};

 

 

 

// 이진 탐색 트리

template<class datatype>
class BST
{
public:
BST() {};
BST(int (*function)(datatype first_data_in, datatype last_data_in))
{
	_compare = function;
};
~BST()
{
	if (root != nullptr)
	{
		delete root;
		root = nullptr;
	}
}

void insert(datatype data_in)
{
	Node<datatype>* current_node = root;
	if (root == nullptr)
		root = new Node<datatype>(data_in);
	else
	{

		while (current_node != nullptr)
		{
			if (_compare(current_node->_data, data_in) > 0)	// 비교값보다 작은 수. 왼쪽으로 보내야
			{
				if (current_node->_left_node == nullptr)	// 왼쪽 노드가 텅텅 비었다면 추가해야
				{
					current_node->_left_node = new Node<datatype>(data_in);
					current_node->_left_node->_parent_node = current_node;
					current_node = nullptr;
				}
				else   // 왼쪽 노드에 데이터가 존재한다면 커서를 그 왼쪽 노드로 이동
					current_node = current_node->_left_node;
			}
			else if (_compare(current_node->_data, data_in) == 0)	// 비교값과 같은 수. 
			{
				// 값 추가 무시
			}
			else      // 비교값보다 큰 수. 오른쪽으로 보내야
			{
				if (current_node->_right_node == nullptr)	// 오른쪽 노드가 텅텅 비었다면 추가해야
				{
					current_node->_right_node = new Node<datatype>(data_in);
					current_node->_right_node->_parent_node = current_node;
					current_node = nullptr;
				}
				else  // 오른쪽 노드에 데이터가 존재한다면 커서를 그 오른쪽 노드로 이동
					current_node = current_node->_right_node;
			}
		}
	}
}

void destroy(datatype data_in)
{
	Node<datatype>* current_node = root;
	int result;
	if (root != nullptr)
	{
		while (current_node != nullptr)
		{
			result = _compare(current_node->_data, data_in);
			if (result == 0)
			{
               					 // 자식노드 둘다 살아 있는 경우
				if (current_node->_left_node != nullptr && current_node->_right_node != nullptr)	
				{
					Node<datatype>* temp_node = current_node;
								
                                
                       			 //오른쪽이면 최소값 노드 검색
					if (current_node->_data > current_node->_parent_node->_data)	
					{
						while (temp_node->_right_node != nullptr)
							temp_node = temp_node->_right_node;
						
                           		 //최하단까지 갔고 왼쪽노드가 살아 있을 때
						if (temp_node->_parent_node->_left_node != nullptr)			
						{
							current_node->_data = temp_node->_parent_node->_left_node->_data;
							delete temp_node->_parent_node->_right_node;
							temp_node->_parent_node->_right_node = nullptr;
						}
						else     //최하단까지 갔는데 왼쪽 노드가 없으면
						{
							current_node->_parent_node->_right_node = current_node->_left_node;
							current_node->_left_node->_right_node = current_node->_right_node;
							delete current_node;
							current_node = nullptr;
						}
					}
					else         //왼쪽이면 최대값 노드 검색
					{
						while (temp_node->_left_node != nullptr)
							temp_node = temp_node->_left_node;
											
                                    //최하단까지 갔고 오른쪽노드가 살아 있을 때
						if (temp_node->_parent_node->_right_node != nullptr)	
						{
							current_node->_data = temp_node->_parent_node->_right_node->_data;
							delete temp_node->_parent_node->_right_node;
							temp_node->_parent_node->_right_node = nullptr;

						}
						else    //최하단까지 갔는데 오른쪽 노드가 없으면
						{
							current_node->_parent_node->_left_node = current_node->_right_node;
							current_node->_right_node->_left_node = current_node->_left_node;
							delete current_node;
							current_node = nullptr;
						}
					}


				}
                     		  // 자식노드 둘다 없는 경우
				else if (current_node->_left_node == nullptr && current_node->_right_node == nullptr)      
				{
                   		  //부모노드보다 큰 경우
					if (current_node->_data > current_node->_parent_node->_data)		
						current_node->_parent_node->_right_node = nullptr;
					else  //부모노드보다 작 경우
						current_node->_parent_node->_left_node = nullptr;


					delete current_node;
					current_node = nullptr;
				}
				else     		// 자식노드 하나만 있는 경우
				{
                   		  // 오른쪽 노드
					if (current_node->_data > current_node->_parent_node->_data) 
					{
						current_node->_parent_node->_right_node = current_node->_right_node;
						delete current_node;
						current_node = nullptr;
					}
					else  // 왼쪽 노드, 같은 숫자는 고려하지 않음
					{
						current_node->_parent_node->_left_node = current_node->_left_node;
						delete current_node;
						current_node = nullptr;
					}
				}
			}
			else if (result == 1)
				current_node = current_node->_left_node;
			else if (result == -1)
				current_node = current_node->_right_node;

		}
	}
}

Node<datatype>* find(datatype data_in)
{
	Node<datatype>* current_node = root;
	int result;
	if (root == nullptr)
	{
		return nullptr;
	}
	else
	{
		while (current_node != nullptr)
		{
			result = _compare(current_node->_data, data_in);
			if (result == 0)
				return current_node;
			else if (result == 1)
				current_node = current_node->_left_node;
			else if (result == -1)
				current_node = current_node->_right_node;

		}

		return nullptr;

	}
}


public:
	int (*_compare)(datatype first_data_in, datatype last_data_in);
	Node<datatype>* root = nullptr;

};

 

 

 

// 데이터 비교 함수 및 메인 함수

template<class datatype >
int check(datatype data_in, datatype other_data_in)
{
	if (data_in == other_data_in)
	{
		return 0;
	}
	else if (data_in > other_data_in)
	{
		return 1;
	}
	else
	{
		return -1;
	}
}


int main()
{
	BST<int>* main_BST = new BST<int>(check);

	main_BST->insert(6);
	main_BST->insert(4);
	main_BST->insert(9);
	main_BST->insert(2);
	main_BST->insert(5);
	main_BST->insert(11);
	main_BST->insert(10);
	main_BST->insert(13);

	main_BST->destroy(13);


	if (main_BST->find(9) != nullptr)
		std::cout << main_BST->find(9)->_data;
	else
		std::cout << " 삭제 되었습니다.";

	return 0;
}