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

01. 이진 탐색 트리란?

출처 : 위키백과

• 이진 탐색 트리는 이진트리 기반의, 탐색을 용이하게 하기 위한 자료구조
• 탐색을 위한 키 값 기준으로 정렬된다.
• 이진 탐색 트리의 정의는 다음과 같다.

1. 모든 노드는 유일한 키를 갖는다.
2. 왼쪽 서브트리의 키는 루트의 키보다 작다.
3. 오른쪽 서브트리의 키는 루트의 키보다 크다.
4. 왼쪽과 오른쪽 서브트리도 이진트리이다.

---

02. 이진 탐색 트리의 연산

• 이진 탐색 트리는 삽입, 삭제 과정에서 이진트리의 특성을 유지해야 한다.

탐색

탐색 연산은 키 값 비교를 통해 왼쪽과 오른쪽 노드를 탐색할지 결정한다.

1. 찾고자 하는 키 값과 현재 노드의 키 값이 일치한다면 탐색 성공
2. 찾고자 하는 키가 현재 노드보다 작다면, 왼쪽 노드로 이동해 다시 탐색한다.
3. 찾고자 하는 키가 현재 노드보다 크다면, 오른쪽 노드로 이동해 다시 탐색한다.
4. 더 이상 왼쪽, 오른쪽 노드가 없다면 탐색 실패 (찾은 경우 1번에서 반환했기 때문)

CBinaryNode* CBinSrchTree::SearchIterative(char key)
{
	if (!m_Root)
	{
		std::cout << "Key값이 " << static_cast<int>(key) << "인 노드 없음\n";
		return nullptr;
	}

	CBinaryNode* node = m_Root;

	while (node)
	{
		if (node->GetData() == key)
		{
			std::cout << "Key값이 " << static_cast<int>(key) << "인 노드 : " << &node << '\n';
			return node;
		}
		else
		{
			if (node->GetData() > key)
			{
				node = node->GetLeft();
			}
			else
			{
				node = node->GetRight();
			}
		}
	}

	std::cout << "Key값이 " << static_cast<int>(key) << "인 노드 없음\n";
	return nullptr;
}

삽입

삽입 연산은 삽입할 노드의 키 값으로 탐색을 진행하다가 탐색이 실패한 지점이 삽입할 지점이다.

예시

5라는 Key 값을 가진 노드를 삽입하는 과정이다.

1. 5는 8보다 작으니 3으로 이동

2. 5는 3보다 크니 6으로 이동

3. 5는 6보다 작으니 4로 이동

4. 5는 4보다 크니 오른쪽으로 이동

5. 오른쪽이 null node이므로 탐색 실패, 5는 4의 오른쪽 노드로 삽입

 

 

 

 

 

 

bool CBinSrchTree::Insert(CBinaryNode* node)
{
	if (!m_Root)
	{
		m_Root = node;
		return true;
	}

	CBinaryNode* curNode = m_Root;

	while (curNode)
	{
		if (curNode->GetData() == node->GetData())
			return false;
		else
		{
			if (node->GetData() < curNode->GetData())
			{
				if (!curNode->GetLeft())
				{
					curNode->SetLeft(node);
					break;
				}
				else
				{
					curNode = curNode->GetLeft();
				}
			}
			else
			{
				if (!curNode->GetRight())
				{
					curNode->SetRight(node);
					break;
				}
				else 
				{
					curNode = curNode->GetRight();
				}
			}
		}
	}

	return true;
}

삭제

삭제 연산은 이진탐색트리 연산 중에서 가장 복잡한 연산이다.

삭제 연산 또한 먼저 탐색을 진행하여 삭제할 노드를 찾아야 한다.

기본적으로 노드를 삭제하면, 그 자리를 대체할 후계 노드를 찾는 과정이라고 생각하면 된다.

삭제 연산은 삭제할 노드의 상태에 따라 다르게 진행되어야 하는데, 총 3가지 경우가 있다.

 

Case 1 : 삭제하려는 노드가 단말 노드(자식 노드가 없는)인 경우

가장 간단한 케이스이다.

그냥 해당 노드를 삭제하고, 부모 노드에게서 해당 자식 노드와의 링크를 NULL로 만들어주면 된다.

삭제할 노드와 부모 노드를 알고 있어야 한다.

Case 2 : 삭제하려는 노드가 하나의 자식 노드만 가지고 있는 경우

이 또한 어렵지 않다.

대상 노드를 삭제하고, 삭제 대상의 위치로 자식 노드를 이동시켜주면 된다.

삭제할 노드, 삭제할 부모 노드, 삭제할 노드의 유일한 자식 노드를 알고 있어야 한다.

Case 3 : 삭제하려는 노드가 자식 노드를 두개 다 가지고 있는 경우

가장 복잡한 케이스이다.

2번 케이스처럼 그냥 삭제할 노드의 두 자식 중 아무나 선택해서 올린다면, 이진탐색트리 구조가 깨지게 된다.

( 18번 노드의 자식인 26번 노드를 그냥 18번 자리로 올린다고 생각해보자. 26번 노드의 자식은 셋이 된다.)

이진 트리의 조건을 만족하면서 삭제 노드의 자리를 대체할 노드를 찾는 조건은

 

삭제 노드의 key값과 가장 근접한 값을 가진 노드를 찾는 것이다.

이를 만족하는 노드는,

1. 삭제할 노드의 왼쪽 자식 노드의 자식 중에서 가장 오른쪽 노드

2. 삭제할 노드의 오른쪽 자식 노드의 자식 중에서 가장 왼쪽 노드

위 그림에서는 12번 노드와 22번 노드가 이에 해당된다.

둘 중 어떤 것을 택해도 상관은 없다.

 

3번 케이스의 삭제 연산을 위해서는

삭제할 노드, 삭제할 노드의 부모 노드, 삭제할 노드를 대체할 노드(승계 노드), 승계 노드의 부모 노드를 알고 있어야 한다.

 

삭제 연산의 코드

bool CBinSrchTree::Remove(char data)
{
	CBinaryNode* parent = nullptr;
	CBinaryNode* curNode = m_Root;

	while (curNode)
	{
		if (curNode->GetData() == data)
		{
			// 삭제할 노드가 단말 노드인 경우
			if (curNode->IsLeaf())
			{
				// 삭제할 노드가 루트인 경우
				if (curNode == m_Root)
				{
					m_Root = nullptr;
				}
				else
				{
					if (parent->GetLeft() == curNode)
						parent->SetLeft(nullptr);
					else
						parent->SetRight(nullptr);
				}
			}
			// 삭제할 노드의 자식 노드가 하나일 경우
			else if (!curNode->GetLeft() || !curNode->GetRight())
			{
				// 삭제할 노드가 루트인 경우 삭제할 노드의 존재하는 자식을 루트로 한다.
				CBinaryNode* child = curNode->GetLeft() ? curNode->GetLeft() : curNode->GetRight();
				if (curNode == m_Root)
				{
					m_Root = child;
				}
				else
				{
					if (parent->GetLeft() == curNode)
						parent->SetLeft(child);
					else
						parent->SetRight(child);
				}
			}
			// 삭제할 노드의 양쪽 자식 노드가 존재하는 경우
			else
			{
				CBinaryNode* replace = curNode->GetRight();
				CBinaryNode* replaceParent = curNode;

				while (replace->GetLeft())
				{
					replaceParent = replace;
					replace = replace->GetLeft();
				}

				// 승계될 노드가 삭제될 노드의 바로 오른쪽 자식이 아닐 경우
				// 승계될 노드의 부모는 승계될 노드의 오른쪽 자식을 왼쪽 자식으로 올린다.
				if (replace != curNode->GetRight())
					replaceParent->SetLeft(replace->GetRight());

				if (!parent)
					m_Root = replace;
				else if (parent->GetLeft() == curNode)
					parent->SetLeft(replace);
				else
					parent->SetRight(replace);

				if (curNode->GetLeft() != replace)
					replace->SetLeft(curNode->GetLeft());
				if (curNode->GetRight() != replace)
					replace->SetRight(curNode->GetRight());
			}

			delete curNode;
			curNode = nullptr;

			return true;
		}
		else
		{
			parent = curNode;

			if (curNode->GetData() > data)
				curNode = curNode->GetLeft();
			else
				curNode = curNode->GetRight();
		}
	}

	return false;
}

---

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

삽입, 삭제, 탐색 모두 O(logN)의 시간 복잡도를 보장한다.

단순히 생각해봐도, 한 단계 아래 노드로 이동할수록 탐색해야 할 노드가 1/2로 줄어드는 것이 되므로 매우 효율적이다.

C++ STL의 Set가 이 이진 탐색 트리로 구현되어 있다고 한다.

단, 좌우의 서브트리가 균형을 이루지 않는 경우, 즉, 오른쪽 자식들만 존재하거나 왼쪽 자식들만 존재하는 트리의 경우 시간 복잡도가 O(N)으로 증가한다.

균형을 유지하기 위해 AVL트리 같은 기법들이 있다고 한다.