[자료구조]이진 탐색 트리(Binary Search Tree)

이진 검색 트리

이진 검색 트리란 이진 탐색과 연결리스트를 결하한 자료구조입니다.

이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 삽입과 삭제가 가능합니다.

 

이진 탐색의 경우 탐색에 소요되는 시간 복잡도는 O(logn)으로 빠르지만 자료 삽입, 삭제가 불가능하고, 연결리스트의 경우 자료 삽입, 삭제에 필요한 시간 복잡도는 O(1)로 효율적이지만 자료 탐색에 필요한 시간복잡도는 O(n)이 됩니다.

이 둘을 결합하여 효율적으로 자료 탐색 및 자료 삽입, 삭제를 가능하게 하는 것이 이진 검색 트리입니다. 

이진 검색 트리의 속성

▶ 각 노드에 값(데이터)과 키가 존재하며, 키 값은 모두 달라야 한다.

▶ 노드의 왼쪽 서브트리에는 그 노드의 키 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

▶ 노드의 오른쪽 서브트리에는 그 노드의 키 값보다 큰 값들을 지닌 노드들로 이루어져 있다.

▶ 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

▶ 중복된 노드가 없어야 한다.

 

여기서 가장 중요한 부분은 노드에 키 값과 데이터가 존재한다는 것입니다. 즉, 데이터와 키 값이 쌍을 이루어 존재하고, 이 키 값은 고유 값으로 중복된 값이 없어야 합니다.

이러한 키 값을 통해 이진 탐색 트리에서 자료 탐색, 삽입, 삭제를 진행하게 됩니다. 

이진 검색 트리의 자료 삽입

▶삽입하고자 하는 노드의 키 값을 이진 검색 트리의 루트 노드부터 비교를 진행합니다.

▶비교하는 노드의 키값 보다 작다면 노드의 왼쪽 노드로, 크다면 오른쪽 노드로 이동합니다.

▶이동하고자 하는 곳이 nullptr이라면 그곳에 노드를 삽입합니다.

 

위 그림을 보면 8 - 5 - 4 - 6 - 15 - 16의 키 값으로 이루어진 이진트리가 있습니다. 여기에 키 값 10을 가지는 노드를 추가하고 있습니다.

먼저 루트 노드 부터 시작하여 키 값을 비교합니다. 

루트 노드의 키 값은 8로 삽입하고자 하는 키 값보다 작으므로 오른쪽 노드로 이동합니다.

다음 노드의 키 값은 15로 삽입하고자 하는 키 값보다 큽니다. 따라서 왼쪽 노드로 이동해야 하는데, 왼쪽 노드가 없으므로 키 값 15를 가지는 노드의 왼쪽 노드에 키 값 10을 가지는 노드를 추가합니다.

이진 탐색 트리의 자료 삭제

<출처 : http://mattlee.tistory.com/30>

이진 탐색 트리에서 자료 삭제는 3가지 경우를 고려해야 합니다.

1. 삭제하고자 하는 노드가 단말 노드인 경우 (자식 노드가 없는 경우)

 

삭제하고자 하는 노드가 단말 노드인 경우는 매우 간단합니다. 

삭제하고자 하는 노드를 가리키고 있는 부모 노드의 링크를 nullptr을 통해 연결을 끊어주고, 삭제하고자 하는 노드의 메모리를 해제한 뒤 NULL로 만들어주면 됩니다.

2. 삭제하고자 하는 노드가 하나의 서브트리만 가지는 경우 (자식 노드가 왼쪽 혹은 오른쪽만 있는 경우)

 

위 그림에서 키 값 68을 가진 노드를 삭제하고자 합니다. 

키 값 35를 가지고 있는 노드가 부모 노드의 오른쪽 노드를 삭제하는 것이므로 키 값 68을 가진 노드의 메모리를 반납하고 그 자식 노드를 키 값 35를 가진 부모 노드의 오른쪽 링크에 연결해 주면 됩니다.

3. 삭제하고자 하는 노드가 두 개의 서브트리를 모두 가지는 경우 (자식 노드 2개를 모두 있는 경우)

 

이 경우가 가장 복잡하고 어려운 경우입니다.

키 값 18을 가진 노드를 삭제하고자 하는 경우 부모 노드의 왼쪽 노드에 어떤 노드를 연결할지를 결정해야 합니다. 

두 가지 경우가 있는데, 

1. 삭제하고자 하는 노드의 왼쪽 서브트리에 있는 값 중 가장 큰 값

2. 삭제하고자 하는 노드의 오른쪽 서브트리에 있는 값 중 가장 작은 값

이 둘 중 하나를 선택하여 노드를 연결시켜 주면 됩니다.(보통은 왼쪽 서브트리에서 가장 큰 값을 선택합니다.)

이렇게 하는 이유는 트리의 변동성을 최소화하기 위함입니다.

 

왼쪽 서브 트리의 가장 큰 값인 12를 선택했다고 하면, 삭제하고자 하는 노드의 왼쪽 서브트리에서 NULL이 나오기 전까지 오른쪽 노드로 이동을 진행합니다. 이렇게 찾아낸 노드를 키 값 35인 노드의 왼쪽 필드에 연결하고 왼쪽 필드에 7을 오른쪽 필드에 26을 연결하면 됩니다.

물론 삭제하고자 한 노드는 메모리를 반납해 줍니다.

 

<코드>

class C_BST
{
private:
	struct S_NODE{
		int nId;
		int nData;
		S_NODE* pLeftNode;
		S_NODE* pRightNode;
	};

private:
	S_NODE * m_pRoot;

public:
	C_BST();
	bool addData(int nId, int nData);
	bool removeData(int nId);
	void print();

private:
	S_NODE * createNode(int nId, int nData);
	void printData(S_NODE* pNode);
	S_NODE** findNode(S_NODE** ppNode, int nId);
	S_NODE** findMaxNode(S_NODE** ppNode);
};

이진 검색 트리를 구성하는 Class입니다. 

노드를 구성하는 구조체 S_NODE를 보시면 키 값인 nId와 데이터인 nData가 존재하고 있습니다. 

여기서 키 값인 nId를 통해 자료 삽입과 삭제를 진행하게 됩니다.

 

C_BST::S_NODE ** C_BST::findNode(S_NODE ** ppNode, int nId)
{
	//while ((*ppNode) && (*ppNode)->nId != nId) {
	//	if ((*ppNode)->nId > nId) {
	//		ppNode = &(*ppNode)->pLeftNode;
	//	}
	//	else if ((*ppNode)->nId < nId) {
	//		ppNode = &(*ppNode)->pRightNode;
	//	}
	//}
	//return ppNode;

	if (!(*ppNode) || (*ppNode)->nId == nId) {
		return ppNode;
	}

	if ((*ppNode)->nId > nId) {
		return findNode(&(*ppNode)->pLeftNode, nId);
	}
	else if ((*ppNode)->nId < nId) {
		return findNode(&(*ppNode)->pRightNode, nId);
	}

	return nullptr;
}

삽입할 노드의 위치를 찾거나 삭제할 노드를 찾을 때 사용하는 findNode 함수입니다.

주석 친 부분은 반복을 사용하여 구현한 방식이고, 주석이 아닌 부분은 재귀적인 방식으로 구현한 코드입니다.

찾고자 하는 키 값(여기선 nId)을 가지는 Node가 존재하면 해당 노드를, 존재하지 않으면 키 값이 삽입될 위치를 반환합니다.

 

C_BST::S_NODE ** C_BST::findMaxNode(S_NODE ** ppNode)
{
	while ((*ppNode)->pRightNode)
	{
		ppNode = &(*ppNode)->pRightNode;
	}
	return ppNode;

	/*if (!(*ppNode)->pRightNode)
		return ppNode;
	return findMaxNode(&(*ppNode)->pRightNode);*/
}

인자로 들어온 서브트리의 가장 큰 값을 반환하는 함수로 자료 삭제 과정에서 삭제하고자 하는 노드의 자식 모두 있는 경우 사용하는 함수입니다.

주석 친 부분은 재귀적인 방식으로 구현한 것이고 주석이 아닌 부분은 반복을 통해 구현한 것입니다.

 

C_BST::S_NODE * C_BST::createNode(int nId, int nData)
{
	S_NODE* pNewNode = nullptr;
	pNewNode = new S_NODE{};
	pNewNode->nId = nId;
	pNewNode->nData = nData;
	return pNewNode;
}

새로운 노드를 동적할당을 통해 생성하고 그 노드를 반환하는 함수입니다.

 

bool C_BST::addData(int nId, int nData)
{
	S_NODE** ppFindNode = findNode(&m_pRoot, nId);

	if ((*ppFindNode))
		return false;

	(*ppFindNode) = createNode(nId, nData);

	return true;;
}

노드를 사입하는 함수입니다.

findNode() 함수를 통해 삽입하고자 하는 노드의 키값을 비교하여 삽입할 위치를 찾습니다. 

만약 삽입하고자 하는 노드의 키값과 동일한 키값을 가진 노드가 있다면 (*ppfFindNode)는 NULL이 아닐 것이고 이 경우 노드를 삽입할 수 없으므로 false를 반환하고 함수를 빠져나옵니다.

삽입하고자 하는 키값을 가진 노드가 존재하지 않으면 (*ppFindNode)는 NULL 값을 가지지만 ppFindNode가 이중 포인터로 선언된 변수이므로 삽입할 위치를 가리키고 있습니다. 따라서 여기에 노드를 추가하면 됩니다.

 

C_BST::S_NODE * C_BST::createNode(int nId, int nData)
{
	S_NODE* pNewNode = nullptr;
	pNewNode = new S_NODE{};
	pNewNode->nId = nId;
	pNewNode->nData = nData;
	return pNewNode;
}

새로운 노드를 동적할당을 통해 생성하고 그 노드를 반환하는 함수입니다.

 

bool C_BST::removeData(int nId)
{
	S_NODE** ppFindNode = findNode(&m_pRoot, nId);

	if (!(*ppFindNode))
		return false;

	
	if ((*ppFindNode)->pLeftNode && (*ppFindNode)->pRightNode) {
		S_NODE** ppMaxNode = findMaxNode(&(*ppFindNode)->pLeftNode);

		(*ppFindNode)->nId = (*ppMaxNode)->nId;
		(*ppFindNode)->nData = (*ppMaxNode)->nData;

		ppFindNode = ppMaxNode;
	}

	S_NODE* pNextNode = nullptr;
	if ((*ppFindNode)->pLeftNode) {
		pNextNode = (*ppFindNode)->pLeftNode;
	}
	else {
		pNextNode = (*ppFindNode)->pRightNode;
	}

	delete (*ppFindNode);
	(*ppFindNode) = pNextNode;

	return true;
}

인자로 받은 키 값을 가진 노드를 삭제하는 함수입니다.

findNode() 함수를 통해 키 값을 가진 노드를 찾는데 만약 해당 키 값을 가진 노드가 없다면 이 함수는 NULL을 반환하게 되고 이 경우 삭제를 진행할 수 없으므로 false를 반환하고 함수를 종료합니다.

 

해당 키 값을 가진 노드가 존재한다면 삭제를 진행합니다.

삭제하고자 하는 노드가 단말 노드인 경우 모든 조건을 건너뛰고 해당 노드의 메모리를 반환하고 삭제한 노드의 부모 노드의 링크를 NULL로 변경합니다.

 

삭제하고자 하는 노드에 하나의 자식 노드가 있는 경우에는 삭제하고자 하는 노드의 자식노드를 임시 변수를 통해 저장하고, 노드를 삭제한 뒤 부모노드의 링크에 임시변수에 저장한 노드를 연결합니다.

 

삭제하고자 하는 노드에 2개의 자식노드가 모두 있는 경우 더블 포인터형 임시 변수를 통해 삭제하고자 하는 노드의 왼쪽 서브트리에서 가장 큰 키 값을 가지는 노드를 가리키도록 합니다. 그리고 삭제하고자 하는 노드의 키 값과 데이터를 해당 노드의 키 값과 데이터로 변경합니다.

그다음 삭제하고자 하는 노드를 가리키고 있던 더블 포인터 변수 ppFindNode가 가리키는 곳을 더블 포인터형 임시 변수가 가리키는 곳으로 이동합니다.

이후 ppFindNode가 가리키는 노드를 삭제하면 됩니다. 이는 단말 노드 또는 자식 노드를 하나 가지는 노드를 삭제하는 과정과 똑같아집니다.