[Data Structure] Tree 이진 탐색 트리(BST) 구현

트리의 기본 개념을 확인하려면 아래의 글 참조

2022.08.27 - [Data Structure/Tree] - [Data Structure] Tree 기본

[Data Structure] Tree 기본

트리의 순위에 대한 개념은 아래의 글 참조

2022.09.05 - [Data Structure/Tree] - [Data Structure] Tree 전위, 중위, 후위 순회

[Data Structure] Tree 전위, 중위, 후위 순회

---

이진 탐색 트리(Binary Search Tree)

• 노드의 깂은 중복되지 않는다.
• 루트 노드의 왼쪽 서브 트리는 루트 노드의 값보다 작은 값을 갖는다.
• 루트 노드의 오른쪽 서브 트리는 루트 노드의 값보다 큰 값을 갖는다.
• 좌우 서브 트리도 모두 이진 탐색 트리다.

 

이진 탐색 트리의 시간 복잡도

이진 탐색 트리의 시간 복잡도는 이진 탐색 트리의 높이가 h 일 경우,  O(h)의 시간 복잡도를 가진다. 

 

삽입 (Insert)

• 이진 탐색 트리(이하 BST)는 중복을 허용하지 않는다.
• 삽입하려는 값이 루트 노드의 값 보다 작을 경우, 왼쪽 서브 트리를 탐색하여 추가한다.
• 삽입하려는 값이 루트 노드의 값 보다 클 경우, 오른쪽 서브 트리를 탐색하여 추가한다.

int CTree::Insert(int iData)
{
	int iRet = ERRNO; // 에러 없음에 대한 define 값
	Tree* NewNode = NULL;
	Tree* tmpNode = NULL;
	
    // 루트 노드에 값이 없는 경우, 추가
	if (NULL == m_Root)
	{
		m_Root = (Tree*)malloc(sizeof(Tree));
		if (NULL == m_Root)
			return EFAULT;
		
		m_Root->iData = iData;
		m_Root->left = m_Root->right = NULL;
	}
	else
	{
		NewNode = (Tree*)malloc(sizeof(Tree));
		if (NULL == NewNode)
			return EFAULT;

		NewNode->iData = iData;
		NewNode->left = NewNode->right = NULL;

		tmpNode = m_Root;
		
        // 추가하려는 값의 크기를 적절히 비교하여 추가
		while (tmpNode)
		{
			if (iData == tmpNode->iData)
			{
				return EFAULT; // 중복된 값 허용 X
			}
			else if (tmpNode->iData > iData)
			{
				if (NULL == tmpNode->left)
				{
					tmpNode->left = NewNode;
					break;
				}
				else
				{
					tmpNode = tmpNode->left;
				}
			}
			else
			{
				if (NULL == tmpNode->right)
				{
					tmpNode->right = NewNode;
					break;
				}
				else
				{
					tmpNode = tmpNode->right;
				}
			}
		}
	}
	
	return iRet;
}

 

탐색(Search)

• 삽입의 과정과 유사하다.
• 탐색하려는 값이 루트 노드의 값 보다 작을 경우, 왼쪽 서브 트리를 탐색한다.
• 탐색하려는 값이 루트 노드의 값 보다 클 경우, 오른족 서브 트리를 탐색한다.

Tree* CTree::Search(int iData)
{
	Tree* tmpNode = m_Root;

	while (tmpNode)
	{
		if (iData == tmpNode->iData)
		{
			return tmpNode;
		}
		else if (tmpNode->iData > iData)
		{
			tmpNode = tmpNode->left;
		}
		else
		{
			tmpNode = tmpNode->right;
		}
	}

	return tmpNode;
}

 

삭제(Delete) - 재귀 사용

재귀를 사용하여 삭제 함수를 구현했다. 

삭제의 경우, 루트 노드부터 값의 크기를 비교하여 위치를 찾는다. 

삭제하려는 노드의 자식 유무에 대하여 아래와 같은 경우의 수를 처리해야 한다.

• 삭제하려는 노드의 자식이 없는 경우
• 삭제하려는 노드의 자식이 하나만 있는 경우
• 삭제하려는 노드의 자식이 둘 다 있는 경우
  • 삭제하려는 노드의 왼쪽 자식 중 가장 큰 값 or 삭제하려는 노드의 오른쪽 자식 중 가장 작은 값을 찾음
  • 삭제하려는 노드와 찾은 노드를 교환
  • 삭제하려는 노드 삭제

Tree* CTree::DeleteNode(Tree* root, int iData)
{
	if (NULL == root)
		return NULL;

	Tree* MaxNode = NULL;

	if (iData < root->iData)
		root->left = DeleteNode(root->left, iData);
	else if (iData > root->iData)
		root->right = DeleteNode(root->right, iData);

	else
	{
		// 왼쪽 노드만 있는 경우
		if (NULL == root->right)
		{
			Tree* tmpNode = root->left;
			free(root);
			return tmpNode;
		}
		// 오른쪽 노드만 있는 경우
		else if (NULL == root->left)
		{
			Tree* tmpNode = root->right;
			free(root);
			return tmpNode;
		}
		
		// 둘 다 있는 경우
		else
		{
			MaxNode = FindMaxNode(root->left);
			if (NULL != MaxNode)
			{
				root->iData = MaxNode->iData;
				root->left = DeleteNode(root->left, MaxNode->iData);
			}
		}
	}

	return root;
}

// 왼쪽 자식 중에 가장 큰 값을 찾는 방법을 선택했다.
Tree* CTree::FindMaxNode(Tree* node)
{
	if (NULL == node)
		return NULL;
	
	Tree* tmpNode = node;

	while (tmpNode && tmpNode->right)
		tmpNode = tmpNode->right;

	return tmpNode;
}

 

삭제(Delete) - 재귀 사용하지 않음

재귀를 사용하지 않고 구현했다. 

위 삭제 과정에서 고려해야 하는 사항은 동일하다.

int CTree::Delete(int iData)
{
	int iRet = ERRNO;
	Tree* delNode = NULL;
	Tree* parentNode = NULL;
	Tree* MaxNode = NULL;
	Tree* MaxNodeParent = NULL;
	Tree* ChildNode = NULL;

	delNode = m_Root;
	while (delNode)
	{
		if (iData == delNode->iData)
			break;

		parentNode = delNode;
		
		if (iData < delNode->iData)
			delNode = delNode->left;
		else
			delNode = delNode->right;
	}

	if (NULL == delNode)
		return EFAULT;

	if (NULL == delNode->left && NULL == delNode->right)
	{
		if (NULL != parentNode)
		{
			if (delNode == parentNode->left)
				parentNode->left = NULL;
			else
				parentNode->right = NULL;
		}
		else
		{
			m_Root = NULL;
		}
	}
	else if (NULL != delNode->left && NULL != delNode->right)
	{
		MaxNode = delNode->left;
		MaxNodeParent = delNode;

		while (MaxNode && MaxNode->right)
		{
			MaxNodeParent = MaxNode;
			MaxNode = MaxNode->right;
		}

		MaxNodeParent->right = MaxNode->left;
		MaxNode->left = delNode->left;
		MaxNode->right = delNode->right;

		// root 노드가 아닌 경우
		if (NULL != parentNode)
		{	
			if (delNode == parentNode->left)
				parentNode->left = MaxNode;
			else
				parentNode->right = MaxNode;
		}
		else
		{
			m_Root = MaxNode;
		}
	}
	else
	{
		if (NULL == delNode->right)
			ChildNode = delNode->left;
		else
			ChildNode = delNode->right;

		if (NULL != parentNode)
		{
			if (delNode == parentNode->left)
				parentNode->left = ChildNode;
			else
				parentNode->right = ChildNode;
		}
		else
		{
			m_Root = ChildNode;
		}	
	}

	free(delNode);
	return iRet;
}

 

이진 탐색 트리 삭제(Delete All)

이진 탐색 트리의 모든 노드를 제거한다.

재귀를 사용해서 구현하였고, 후의 순회의 방법과 동일한 방법으로 삭제를 진행한다.

void CTree::DeleteAll(Tree* node)
{
	if (NULL != node)
	{
		DeleteAll(node->left);
		DeleteAll(node->right);
		free(node);
	}
}

 

중위 순회(Inorder)

중위 순회 과정을 구현하였다. 

순회 과정은 왼쪽 > 루트 > 오른쪽이다. 

// 왼쪽 -> 루트 -> 오른쪽
void CTree::Inorder(Tree* node)
{
	Inorder(node->left);
	printf("Inorder: %d", node->iData);
	Inorder(node->right);
}

 

전위 순회(Preorder)

전위 순회 과정을 구현하였다. 

순회 과정은 루트 > 왼쪽 > 오른쪽이다.

// 루트 -> 왼쪽 -> 오른쪽
void CTree::Preorder(Tree* node)
{
	printf("Preorder: %d", node->iData);
	Preorder(node->left);
	Preorder(node->right);
}

 

후위 순회(Postorder)

후위 순회 과정을 구현하였다. 

순회 과정은 왼쪽 > 오른쪽. 루트다.

// 왼쪽 -> 오른쪽 -> 루트
void CTree::Postorder(Tree* node)
{
	Postorder(node->left);
	Postorder(node->right);
	printf("Postorder: %d", node->iData);
}

 

이상으로 이진 탐색 트리를 클래스화 하여 각각의 동작을 코드로 구현하였다.