[Data Structure] BST(Binary Search Tree)

이진 트리는 한 노드의 자식 노드가 최대 2개로 이뤄진 트리를 의미한다.

 

그 중 이진 탐색 트리는 노드가 트리에 추가가 될 때, 자동으로 데이터들의 값을 비교하여 노드의 위치를 정하는 트리를 의미한다.

 

기본적인 원리는 다음과 같다.

 

1. 추가되는 노드는 루트 노드에서부터 비교가 된다.

 

2. 루트 노드의 데이터 보다 크면 오른쪽, 작으면 왼쪽 자식 노드로 간다.

 

3. 루트 노드의 자식 노드와 데이터를 비교하여 역시나 크면 오른쪽, 작으면 왼쪽 자식으로 향한다.

 

4. 3의 과정을 반복해서 더 이상 자식 노드가 없을 때까지 이동한 다음, 해당 노드의 자식 노드로 등록이 된다.

 

이진 탐색 트리

 

위와 같은 과정으로 데이터 20을 가진 노드는 24를 가진 노드의 왼쪽 자식으로 등록이 된다. 밑에는 데이터를 삽입할 때 사용하는 함수다. 해당 과정을 거쳐서 자동으로 정렬이 된다.

 

template<typename T>
inline void BST<T>::Push_Data(T data)
{
	if (Root == nullptr)
	{
		Node<T>* node = new Node<T>();
		node->data = data;
		Root = node;
		return;
	}

	Node<T>* current = Root;

	while (current != nullptr || current->data != data)
	{
		if (current->data < data)
		{
			if (current->RChild == nullptr)
			{
				Node<T>* node = new Node<T>();
				node->data = data;

				current->RChild = node;
				node->Parent = current;
				current = nullptr;
				size++;
				break;
			}
			else
			{
				current = current->RChild;
			}
		}
		else if (current->data > data)
		{
			if (current->LChild == nullptr)
			{
				Node<T>* node = new Node<T>();
				node->data = data;

				current->LChild = node;
				node->Parent = current;
				current = nullptr;
				size++;
				break;
			}
			else
			{
				current = current->LChild;
			}
		}
		else
		{
			return;
		}
	}
}

 

이렇게 만들어진 이진 탐색 트리는 자동으로 정렬이 되는 트리이기 때문에 별도의 정렬 과정 없이 바로 탐색이 가능하다.

 

또한 삭제를 위해서 별도의 과정이 필요한데 코드로 나타내면 다음과 같다.

 

 

template<typename T>
inline void BST<T>::Delete(T data)
{
	Node<T>* Remove = SearchNode(data);

	if (!Remove)
		return;
	else
	{
		if (Remove->LChild == nullptr && Remove->RChild == nullptr)
		{
			if (Remove == Remove->Parent->LChild)
				Remove->Parent->LChild = nullptr;
			else if(Remove == Remove->Parent->RChild)
				Remove->Parent->RChild = nullptr;
		}
		else
		{
			if (Remove->Parent == nullptr)
			{
				if (Remove->LChild == nullptr || Remove->RChild == nullptr)
				{
					if (nullptr == Remove->LChild)
					{
						Remove->RChild->Parent = nullptr;
						Root = Remove->RChild;
					}
					else if (nullptr == Remove->RChild)
					{
						Remove->LChild->Parent = nullptr;
						Root = Remove->LChild;
					}
				}
			}

			if (Remove->LChild != nullptr && Remove->RChild != nullptr)
			{
				Node<T>* minNode = SearchMinNode(Remove->LChild);
				Remove->data = minNode->data;

				if (minNode->LChild)
				{
					if(minNode->Parent->RChild == minNode)
						minNode->Parent->RChild = minNode->LChild;
					else if (minNode->Parent->LChild == minNode)
						minNode->Parent->LChild = minNode->LChild;

					minNode->LChild->Parent = minNode->Parent;
				}
				else
				{
					if(minNode->Parent->RChild == minNode)
						minNode->Parent->RChild = nullptr;
					else if (minNode->Parent->LChild == minNode)
						minNode->Parent->LChild = nullptr;
				}

				delete minNode;
				return;
			}
			else if(Remove->Parent != nullptr)
			{
				Node<T>* temp = nullptr;

				if (Remove->LChild != nullptr)
					temp = Remove->LChild;
				else
					temp = Remove->RChild;

				if (Remove == Remove->Parent->LChild)
					Remove->Parent->LChild = temp;
				else if (Remove == Remove->Parent->RChild)
					Remove->Parent->RChild = temp;

				temp->Parent = Remove->Parent;

			}
		}
		delete Remove;
	}
}

template<typename T>
inline BST<T>::Node<T>* BST<T>::SearchNode(T data)
{
	Node<T>* current = Root;
	Node<T>* match = nullptr;

	int depth = 0;

	while (current != nullptr)
	{
		if (current->data == data)
		{
			match = current;
			match->depth = depth;
			break;
		}
		else if (current->data < data)
		{
			if (current->RChild != nullptr)
			{
				current = current->RChild;
				depth++;
			}
			else
				return nullptr;
		}
		else if (current->data > data)
		{
			if (current->LChild != nullptr)
			{
				current = current->LChild;
				depth++;
			}
			else
				return nullptr;
		}
	}

	return match;
}

template<typename T>
inline BST<T>::Node<T>* BST<T>::SearchMinNode(Node<T>* node)
{
	if (node == nullptr)
		return nullptr;

	if (node->RChild)
		return SearchMinNode(node->RChild);
	else
		return node;
}

 

여기서 탐색의 방법은 총 세 가지로 나뉘는데, 전위(PreOrder), 중위(InOrder), 후위(PostOrder)의 방법으로 나뉜다.

 

전위 중위 후위의 방법을 구분하는 것은 부모 노드를 언제 탐색하는가로 구분된다.

 

부모 노드 -> 왼쪽 자식 -> 오른쪽 자식 노드의 순서로 탐색하면 전위,

왼쪽 자식 -> 부모 노드 -> 오른쪽 자식 노드의 순서로 탐색되면 중위,

왼쪽 자식 -> 오른쪽 자식 -> 부모 노드의 순서로 탐색이 되면 후위로 구분짓게 된다.

 

 

 

전위 중위 후위 탐색 순서

 

각각 재귀함수로 구성이 되며 기본적인 구조는 다음과 같다.

 

template<typename T>
inline void BST<T>::InOrder(Node<T>* node)
{
    if (node == nullptr)
        return;

    if (node != nullptr)
    {
        InOrder(node->LChild);
        cout << node->data << endl;
        InOrder(node->RChild);
    }
}

template<typename T>
inline void BST<T>::PreOrder(Node<T>* node)
{
    if (node == nullptr)
        return;

    if (node != nullptr)
    {
        cout << node->data << endl;
        PreOrder(node->RChild);
        PreOrder(node->RChild);
    }
}

template<typename T>
inline void BST<T>::PostOrder(Node<T>* node)
{
    if (node == nullptr)
        return;

    if (node != nullptr)
    {
        PostOrder(node->LChild);
        PostOrder(node->RChild);
        cout << node->data << endl;
    }
}