[C++] 트리와 이진 탐색 트리 (Binary Shearch Tree)

[ 목차 ]

1. 개요

1) 개요

리스트, 큐, 스택, 배열과 같은 자료구조를 선형 자료 구조라고 부릅니다.

데이터들을 연속적으로 접근할 수 있는 것이죠.

 

근데, 예를 들어 가족의 가계도, 회사의 조직도, 컴퓨터의 디렉터리 등에 대한 자료구조를 어떻게 표현하면 좋을까요?

이 경우에 사용하는 것이 트리(tree) 계층적 자료 구조입니다.

 

트리 구조는 마치 나무를 거꾸로 뒤집을 형태라고 그렇게 부릅니다.

가장 최상단 노드를 루트노드라고 부르며,

루트의 아래로 작은 트리들이 재귀적으로 정의되는 것을 기본 구조로 합니다.

 

2) 용어

 

트리는 한 개 이상의 노드로 이루어진 유한 집합입니다.

트리에서 최상위 노드를 루트 노드

한 노드에서 뻗어 나오는 노드들을 자식 노드

그 반대를 부모 노드라고 합니다.

 

2의 경우 7, 5를 자식으로 가지고 있고

2와 6은 7을 공통 부모로 가지고 있죠.

 

가계도와 유사하게

조부모 노드, 형제 노드, 손자 노드, 삼촌 노드 등.. 이 존재합니다.

이해하기보다는 일반적인 가계도를 생각하시면 됩니다.

 

그리고 자식을 가지지 않는 노드를 단말 노드, 말단 노드, 리프 노드, 외부 노드 등으로 부릅니다.

자식을 가지지 않는 것을 내부 노드, 비말단 노드 등으로 부릅니다.

 

 

추가적으로 용어정리를 하겠습니다.

 

서브 트리 : 루트인 A의 왼쪽 자식들은 자기들끼리 작은 트리를 이루고 있고, 오른쪽 자식 또한 그렇습니다.

이런 트리 속의 트리를 서브 트리라고 말합니다. 트리는 서브 트리들의 재귀적 정의라고 말하곤 합니다.

 

에지 (간선) : 부모와 자식을 잇는 선을 뜻합니다. 부모에서 자식으로 이동할 순 있지만, 자식에서 부모로 역행할 순 없습니다. 단방향이라는 것을 이해하시면 됩니다.

 

차수 : 한 노드가 가지는 자식의 수를 뜻합니다. 흔히 자료구조에서 사용되는 것은 차수가 2인 이진트리입니다.

레벨 : 트리의 각층에 번호를 매긴다고 보시면 됩니다. 0부터 시작할 수도 있고 1부터 시작할 수도 있습니다. 자료마다 달라서 둘 다 알고 계시면 되겠습니다. 

높이 : 임의의 노드가 가지는 최대 레벨을 뜻합니다.

2. 이진트리

트리 중에서 가장 많이 쓰이는 트리이고, 이때까지 예시로 보여준 그림 모두 2진 트리입니다.

모든 노드의 최대 차수가 2이며, 내부 노드는 오른쪽 자식 혹은 왼쪽 자식을 가집니다.

 

1) 이진트리의 성질

(1) n개의 노드를 가진 이진트리는 n-1의 간선을 가진다.

(2) 높이가 h인 이진트리는 적어도 h개의 노드를 가진다.

(3) 레벨 i에서의 노드의 최대 개수는 2^(i-1) 개입니다.

(4) n개의 노드를 가지는 이진트리의 높이는 최소 log2(n+1)의 올림수이다.

 

2) 이진트리의 구현

이진트리는 배열로 구현할 수 있고, 포인터로도 구현할 수 있습니다.

 

(1) 배열로 구현하는 이진트리

자신의 인덱스가 i라고 하고 루트가 인덱스 1부터 시작할 때

 

(1) (i/2) 번 째 인덱스가 자신의 부모이다.

(2) i*2는 왼쪽자식, i*2 + 1는 오른쪽 자식이다.

 

이러한 구현법은 보통 '우선순위 큐'를 이진 힙으로 구현할 때 많이 쓰이는 방식입니다.

자세한 것은 다른 포스팅에서 다뤄보겠습니다.

 

(2) 포인터로 구현하는 이진트리

이진트리에서 파생되는 많은 자료 구조들인 이진 탐색 트리, 2-3 트리, 2-3-4 트리, RB 트리가 보통 포인터를 이용해서 구현됩니다. 

연결리스트를 잘 이해하고 있다면, 구현하는데 도움이 될 것입니다.

 

 

이런 식의 왼쪽 자식과 오른쪽 자식을 가리키는 노드 포인터를 링크 영역에 가지고 있고

데이터 영역에 저장하고자 하는 데이터를 가지고 있습니다.

 

Node->_left, Node->_right 등으로 링크에 접근해서 자식 노드로 직관적이게 이동할 수 있습니다.

3. 이진 탐색 트리

1) 개요

이진트리 기반의 탐색을 위한 자료 구조입니다.

탐색 알고리즘에 있어서 가장 중요한 트리 응용 중 하나입니다.

 

이진 탐색 트리가 지켜야 할 규칙은 다음과 같습니다.

(1) 모든 노드는 유일한 키를 가진다.

(2) 왼쪽 서브 트리의 키값은 항상 루트의 키 값 보다 작다.

(3) 오른쪽 서브 트리의 키값은 항상 루트의 키값 보다 크다.

(4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

(2), (3) 규칙이 이진 탐색 트리의 가장 중요한 특징입니다.

 

루트부터 시작해서

찾고자 하는 값이 루트의 값보다 크면 오른쪽으로, 아니면 왼쪽으로..

를 반복해서 빠르게 원하는 키를 가지는 트리를 찾을 수 있습니다.

 

2) 노드 구조

 

노드는 앞서 살펴봤던 것과 같이 데이터와 왼쪽 오른쪽 자식에 대한 포인터를 가집니다.

 

3) 트리의 기본 구조

 

이 BST 클래스를 기본 구조로 하나씩 기능을 추가해 보겠습니다.

트리는 오직 _root에 대한 정보만 가지고 있고

_root를 통해 다른 노드에 방문하도록 합니다.

 

참고로 이해를 위해 초기에는 int class 트리를 만들고

후에 템플릿을 이용해서 일반화 클래스로 만들어보겠습니다.

 

4) 트리의 삽입

 

insertCore 함수입니다.

주석 때문에 조금 코드가 더러운 감이 있는데요

트리의 재귀적인 특성을 이용한 코드입니다.

 

트리는 루트 노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성되는데

루트 노드를 기준으로 insertNode의 키값을 비교하여

왼쪽 서브트리로 넘길지, 오른쪽 서브트리로 넘길지 비교하는 로직이 들어가 있으며

 

루트가 nullptr인 노드를 발견할 때까지 함수는 계속 실행됩니다.

 

이 알고리즘은 O(log2 n)의 복잡도를 보입니다.

백터나 연결리스트의 경우 위치를 잡고, 삽입하는 것까지 O(n)을 소모하는데,

이진트리의 특성상 bst는 O(log2 n) 만에 삽입이 가능합니다.

 

매개변수가 복잡하여 ADT의 특성이 깨질 수도 있음을 우려하여

핸들러 함수를 사용하였습니다.

 

참고로 이진 탐색 트리의 특성에 맞게 동일한 키값은 삽입되지 않습니다.

 

5) 트리의 탐색

 

탐색의 코드이며, 위 삽입 코드가 이해가 잘 안 됐을 때는

탐색코드를 먼저 보면 이해하기 쉽습니다.

 

삽입, 탐색, 삭제 등 굳이 재귀적으로 만들지 않고 while 문을 사용해서 만들 수도 있지만

그러면 부모 노드 또한 이중으로 관리해야 하기 때문에 구현이 번거로워집니다.

 

더하여 while과 if로 BST를 구현할 경우 삭제 연산이 매우 매우 어려워지기 때문에

이렇게 재귀적으로 구현하는게 난이도 및 가독성 면에서 훨씬 좋습니다.

 

트리의 탐색의 경우로 O(log2 n)입니다.

 

6) 트리의 순회

아무래도 선형 자료구조가 아니고 논리적 자료구조이기 때문에 순회하는 것조차 쉬운 일은 아니죠.

트리를 순회하는 방법은 총 4가지 있습니다.

 

(1) 전위 순회

현재 노드 -> 왼쪽 자식 -> 오른쪽 자식 순으로 순회하는 방식을 말합니다.

 

루트 노드에서 출발하면

42 -> 28 -> 21 -> 17 -> 23 -> 31.. 등

왼쪽 서브트리를 재귀적으로 먼저 방문 한 뒤 오른쪽 서브트리를 방문합니다.

 

 

코드는 이와 같고

 

방문 순서는 이와 같습니다.

 

(2) 중위 순회

왼쪽 자식 -> 현재 노드 -> 오른쪽 자식 순서대로 접근합니다.

즉, 함수 실행 시 가장 왼쪽 자식에게 접근하고, 현재 노드 -> 오른쪽 자식 순서대로 순회합니다.

 

이진 탐색 트리의 특성상 중위 순회를 할 시 항상 정렬된 값이 나옵니다.

 

 

(3) 후위 순회

후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 현재 노드 순서대로 접근합니다.

마치 자식을 다 읽고 나서야 자신에게 접근하는 모습을 보입니다.

 

 

 

 

(4) 레벨 순회

레벨 순회는 레벨에 대해 오름차순으로 순회하는 방식입니다.

레벨 1을 쭉 순회하고

레벨 2를 쭉 순회하고..

 

를 반복하는 것이죠.

 

이것은 그래프 탐색 알고리즘 중 BFS(너비 우선 탐색)을 이용합니다.

 

 

큐를 사용해서 이렇게 레벨 순으로 순회할 수 있습니다.

4. 이진 탐색 트리의 삭제 

이진 탐색 트리에서 삭제 연산은 꽤나 복잡합니다.

먼저 노드를 삭제하기 위해 탐색하는 것까지는 좋은데,

특정 노드를 삭제하고 이진 탐색 트리의 특성에 맞게 트리를 재구성하는 것이 복잡한 것이죠.

 

먼저 삭제에 있어 3가지 경우의 수를 생각해 보겠습니다.

 

(1) 삭제하려는 노드가 단말 노드일 경우

(2) 삭제하려는 노드가 하나의 서브트리를 가질 경우

(3) 삭제하려는 노드가 2개의 서브트리를 가질 경우

 

1) 삭제하려는 노드가 단말 노드일 경우

이 경우는 가장 쉬운 경우입니다.

그냥 노드를 없애고 부모노드의 자식링크를 nullptr로 밀어주면 끝입니다.

 

 

2) 삭제하려는 노드가 하나의 서브트리를 가질 경우

두 번째 방법도 어렵지는 않습니다.

부모 노드의 자신의 서브트리를 연결해주기만 해 주면 됩니다.

 

3) 삭제하려는 노드가 2개의 서브트리를 가질 경우

마지막으로 삭제하려는 노드가 두 개의 서브트리인 경우에는 조금 복잡해집니다.

 

62를 어떻게 제거해야 이진 탐색 트리의 규칙을 만족하게 만들 수 있을까요?

한 가지 방법은, 후계자를 선택하는 방법입니다.

 

일단 자신 다음으로 작은 값 혹은 큰 값을 선택하여 삭제할 노드에 복사합니다.

예를 들어 다음으로 큰 값을 선택한다고 하면,

먼저 노드 62의 오른쪽 서브 트리에서 가장 왼쪽 노드를 고르면 됩니다.

67이 62 다음으로 큰 수를 가지는 노드인 것이죠.

 

노드 62의 데이터를 삭제할 노드에 모두 복사하고,

삭제할 노드의 오른쪽 서브 트리에서 노드 62를 삭제하는 문제로 바꿉니다.

그러면 1), 2) 해결 방법을 사용하여 문제를 해결할 수 있죠.

 

 

이런 식으로 말이죠.

 

이진 탐색 트리의 삭제 복잡도는 O(log2 N)입니다.

 

4) 리팩토링 + 템플릿 일반화 프로그래밍 후 전체 코드

template <typename Ty>
struct BstCmp
{
	int operator()(Ty left, Ty right)
	{
		if (left < right)
			return 1;
		else if (left > right)
			return -1;
		return 0;
	}
};

template <typename Ty>
struct Node
{
	Node(Ty item) : _element(item) {}
	~Node() = default;

public:
	//데이터 영역
	Ty _element = Ty();

	//링크 영역
	Node* _left = nullptr;
	Node* _right = nullptr;
};

template <typename Ty, typename Comp = BstCmp<Ty>>
class BST
{
	using Node = Node<Ty>;
public:
	BST() = default;
	~BST() = default;


	Node* GetRoot() const { return _root; }

	void Insert(Node* insertNode)
	{
		_root = InsertCore(_root, insertNode);
	}

	Node* Search(Ty key)
	{
		return SearchCore(_root, key);
	}

	void PreorderTraversal(Node* node)
	{
		if (node != nullptr)
		{
			cout << node->_element << endl;
			PreorderTraversal(node->_left);
			PreorderTraversal(node->_right);
		}
	}

	void InorderTraversal(Node* node)
	{
		if (node != nullptr)
		{
			InorderTraversal(node->_left);
			cout << node->_element << " " << endl;
			InorderTraversal(node->_right);
		}
	}

	void PostorderTraversal(Node* node)
	{
		if (node != nullptr)
		{
			PostorderTraversal(node->_left);
			PostorderTraversal(node->_right);
			cout << node->_element << " " << endl;
		}
	}

	void LevelorderTraversal(Node* node)
	{
		queue<pair<Node*, Ty>> q;

		q.push(make_pair(node, 1));

		while (!q.empty())
		{
			Node* hereNode = q.front().first;
			int hereLevel = q.front().second;
			q.pop();

			cout << "[" << hereLevel << "] : " << hereNode->_element << endl;

			if (hereNode->_left != nullptr)
				q.push(make_pair(hereNode->_left, hereLevel + 1));

			if (hereNode->_right != nullptr)
				q.push(make_pair(hereNode->_right, hereLevel + 1));

		}
	}

	void Remove(Ty key)
	{
		_root = RemoveCore(_root, key);
	}

	bool empty() const { return  _size == 0; }

private:
	Node* InsertCore(Node* curNode, Node* insertNode)
	{
		if (curNode == nullptr)
		{
			_size++;
			return insertNode;
		}

		if (functor(curNode->_element, insertNode->_element) == 1)
			curNode->_right = InsertCore(curNode->_right, insertNode);
		else if (functor(curNode->_element, insertNode->_element) == -1)
			curNode->_left = InsertCore(curNode->_left, insertNode);

		return curNode;
	}

	Node* SearchCore(Node* curNode, Ty key)
	{
		if (functor(curNode->_element, key) == 0)
			return curNode;
		else if (functor(curNode->_element, key) == 1)
			return SearchCore(curNode->_right, key);
		else if (functor(curNode->_element, key) == -1)
			return SearchCore(curNode->_left, key);
	}


	Node* RemoveCore(Node* curNode, Ty key)
	{
		if (curNode == nullptr) return nullptr;

		if (functor(curNode->_element, key) == 1)
			curNode->_right = RemoveCore(curNode->_right, key);
		else if (functor(curNode->_element, key) == -1)
			curNode->_left = RemoveCore(curNode->_left, key);
		else
		{
			if (curNode->_right == nullptr)
			{
				_size--;

				if (curNode->_left == nullptr)
				{
					//경우 1:
					delete curNode;
					return nullptr;
				}
				//경우 2-1:
				Node* rNode = curNode->_left;
				delete curNode;
				return rNode;
			}
			else if (curNode->_left == nullptr)
			{
				//경우 2-2:
				_size--;

				Node* rNode = curNode->_right;
				delete curNode;
				return rNode;
			}
			else
			{
				//경우 3:
				Node* successor = curNode->_right;

				while (successor->_left != nullptr)
					successor = successor->_left;


				curNode->_element = successor->_element;
				curNode->_right = RemoveCore(curNode->_right, successor->_element);
			}

		}

		return curNode;
	}


public:
	Node* _root = nullptr;
	int _size = 0;
	Comp functor;
};

5. 이진 탐색 트리의 문제점

이진 탐색트리의 경우 탐색, 삽입, 삭제 연산의 평균적인 시간 복잡도가 O(log2 n)입니다.

매우 빠르다는 것이죠.

 

그런데 이런 경우를 생각해 봅시다.

 

예를 들어서 이런 식의 트리가 있다면.. 어떨까요?

오른쪽 자식만 가지는 매우 불균형한 트리말이죠.

이런 불균형트리는 선형탐색에 비해서 시간적으로 그 어떠한 이득을 볼 수 없습니다.

 

이것은 너무 극단적인 경우이긴 하지만, 그래도 균형이 틀어질수록 이진 탐색 트리의 효율성은 점점 떨어지는 것은 사실입니다. 

 

참고로 불균형이라는 것은 왼쪽  서브트리와 오른쪽 서브트리의 높이 차가 절대값 1을 넘긴다는 것을 뜻합니다.

 

자, 그러면 어떻게 균형을 유지하면서 트리 자료구조를 사용할 수 있을까요?

 

다음 포스팅에 '자가 균형 트리'에 대한 내용을 다뤄보겠습니다.