[자료구조] 트리(Tree)

- 참조 문헌 및 사이트(Reference)

Data Structure : A Pseudocode Approach with C

Data Structure and Algorithm in C++

---

이번 글에서는 비선형(non-linear) 자료구조인 트리(Tree)에 대해서 알아보겠습니다. 나중에 그래프에 대해서도 글을 쓰겠지만, 트리는 그래프에 속하는 자료구조입니다.

 

트리는 위 그림과 같이 생겼습니다. 트리는 노드(node)라고 불리는 요소들과 방향성이 있는 브랜치(branch)로 구성되어 있으며, 이 브랜치는 각 노드를 연결시켜 주는 역할을 합니다. 

노드와 연결된 브랜치의 수는 노드의 degree(차수)라고 하며, 만약 노드를 향하는 브랜치라면 indegree, 노드에서 나오는 브랜치라면 outdegree라고 합니다. degree = indegree + outdegree를 만족합니다.

 

트리가 비어있지 않다면, 트리의 첫번째 노드는 루트(root) 노드라고 일컷습니다. 루트의 indegree는 0이며, 즉, 루트로 들어가는 브랜치는 존재하지 않습니다. 위 그림에서는 A가 트리의 루트 노드가 됩니다.

그리고 그래프라는 자료구조에서 트리를 특정하는 가장 중요한 특징 중 하나가 루트를 제외한 모든 노드의 indegree는 무조건 1이라는 점입니다. 이 말은 즉 어떤 특정 노드로 들어가는 브랜치는 오직 하나 뿐이라는 것입니다. 그리고 각 노드에서 나오는 브랜치는 0, 1 또는 2개 이상이 될 수 있습니다.

 

트리에서 사용되는 용어가 몇 가지 더 있습니다. 그림을 보면서 설명하도록 하죠.

리프(leaf) 노드는 outdegree가 0인 노드를 의미합니다. 나뭇잎이라고 불리는데 노드로부터 뻗어나가는 브랜치가 없는 노드를 의미합니다. 여기서는 C, D, E, G, H, I가 리프노드가 됩니다.

그리고 루트노드도 아니고, 리프노드도 아닌 노드들을 내부 노드(internal node)라고 합니다. B, F가 내부노드가 됩니다.

 

만약 outdegree가 0 이상인, 즉, 노드로부터 뻗어나가는 브랜치가 있다면 그 노드는 부모노드(parent)라고 하며, 부모노드에서 뻗어나가는 브랜치에 연결된 노드를 자식노드(child)라고 합니다. 만약 자식노드들이 같은 부모를 공유한다면, 그 자식노드들을 sibling(형제자매?) 노드라고 합니다.A-B 관계에서 A는 부모노드, B가 자식노드입니다. 그리고 B, E, F는 루트이자 부모노드인 A를 공유하기 때문에 B, E, F는 sibling가 됩니다.

인접한 관계가 아닐 때에는 일반적으로 조상-자손(ancestor-descendant) 노드라고 합니다. 위 그림에서 A와 D를 비교할 때, A가 조상노드가 되고 D가 자손노드가 됩니다.

 

그리고 루트 노드와의 거리를 레벨(level)이라고 합니다. 루트는 루트 자신으로부터의 거리이므로 레벨이 0이지만, 1부터 계산하는 경우도 있는 것 같으나, 보통 일반적으로는 0으로 시작합니다. 따라서 A 노드는 레벨0, B,E,F 노드는 레벨 1이 됩니다.

트리의 높이(height)는 루트로부터 가장 긴 경로를 가진 리프 노드의 레벨에 1을 더한 값을 의미합니다. 여기서는 가장 긴 리프노드의 레벨이 2이기 때문에 위의 트리에서 높이는 3이 됩니다. 높이는 깊이(depth)라고 부르기도 합니다.

 

트리는 몇 개의 서브트리(subtree)로 나누어질 수 있습니다. 아래 그림처럼 트리 속에 포함되어있는 또 다른 트리를 의미합니다. 여기서는 루트가 A인 트리가 있고, 이 트리는 루트가 B인 트리와 루트가 E인 트리, 그리고 루트가 F인 트리로 나누어 질 수 있습니다. 리프노드 또한 루트노드만 존재하는 서브트리라고 볼 수 있죠.

 

이러한 특징 때문에, 트리는 재귀적인 특성을 가지고 있습니다. 

 

사실 트리에서 자식 노드의 개수는 정하기 나름이지만, 자식 노드가 두 개까지만 가질 수 있는, 즉, 차수(degree)가 2인 이진트리(Binary Tree)로 이야기를 이어나가보겠습니다. 차수가 최대 k인 트리는 k-degree 트리라고 할 수 있습니다.

위 그림처럼 이진트리는 어떠한 노드도 두 개를 초과하는 서브트리를 가질 수 없습니다. 즉, 각 노드의 최대 outdegree는 2가 됩니다. 아래 그림은 이진트리의 종류를 보여주고 있습니다.

위 종류에서 보듯이 다양한 모양의 트리가 있습니다. 여기서 우리는 트리의 균형(balance)을 이야기할 수 있는데, (e)와 (g)에 대해서 한 번 살펴봅시다. 결론적으로 (a)는 균형이 잘 맞추어져있고, (g)는 편향되어 있습니다. 만약 데이터를 탐색할 때, (e)의 경우에는 레벨 1까지만 탐색하면 되지만, (g)의 경우에는 레벨2까지 탐색해야 합니다. 

여기서 Balance factor를 통해서 트리의 균형도를 구할 수 있는데, 이 값은 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이입니다. 즉, 아래와 같이 Balance factor를 구할 수 있습니다.

\[B = H_L - H_R\]

이 식을 통해서 위 그림의 트리의 밸런스를 구해보면 다음과 같습니다.

(a) 0 / (b) 0 / (c) 1 / (d) -1 / (e) 0 / (f) 1 / (g) -2 / (f) 2

balanced binary tree는 서브 트리의 차이가 2 이상이 아닌 트리를 의미하며, 즉, balance factor의 값이 -1, 0, 1인 트리를 말합니다. AVL트리에서는 이 balance factor를 통해서 자동으로 트리의 균형을 맞춰줍니다. AVL트리는 이 글에서는 다루지 않겠습니다.

 

다음으로는 Binary Tree의 Traversals, 순회에 대해서 이야기해보겠습니다.

순회는 트리의 각 노드를 한 번씩 방문하는 것인데, 여기 기본적인 두 접근 방법이 있습니다. 하나는 DFS(Depth-first Search), 다른 하나는 BFS(Breadth-first Search)입니다. 

많이 들어보셨겠지만, DFS는 각 루트로부터 첫번째 자식노드의 자손을 모두 방문한 다음에 루트의 두번째 자식노드를 방문하는 방법입니다. 다시 말하자면, 다음 자식노드를 방문하기 전에 한 자식노드의 자손노드를 모두 방문하는 것입니다. 

그리고 BFS는 각 레벨의 노드를 모두 방문하고 다음 레벨로 넘어가서 다음 레벨의 노드를 방문하는 방법입니다. 즉, 각 레벨에 존재하는 모든 노드를 방문해야지 다음 레벨의 노드가 시작되는 것입니다.

 

그리고 이진트리에서는 DFS가 전위순회(Preorder), 중위순회(Inorder), 후위순회(Postorder) 이렇게 세 가지 방법으로 세분화되어 있습니다. 다음과 같은 트리가 있을때, 각 순회가 어떻게 진행되는지 알아봅시다.

 

전위순회는 다음과 같은 방법으로 진행됩니다. 모든 노드에 대해서, 자기 자신을 먼저 방문한 후에 자식 노드를 방문하게 됩니다. 여기서는 A를 먼저 방문하고, B를 방문한 다음에 B에 대해서 자식 노드인 C를 방문하게 됩니다. 그리고 방문할 노드가 없는 리프노드에서는 다시 부모노드로 돌아가서 나머지 자식노드를 방문하게 됩니다. 

그래서 전위순회는 아래와 같이 A B C D E F 순서로 방문합니다.

중위순회는 왼쪽 서브트리를 먼저 방문하고, 그 다음에 자기자신(루트) 노드를 방문하고, 마지막으로 오른쪽 서브트리를 방문하게 됩니다. 즉, A의 왼쪽 서브트리인 B를 지나, B의 왼쪽 서브트리인 C로 향하게 됩니다. 그리고 C에서는 방문할 서브트리가 없기 때문에 C를 방문하고 부모노드인 B로 돌아가서 B를 방문한 다음에 오른쪽 서브트리인 D로 향하게 됩니다. 그리고 D에서는 방문할 서브트리가 없기 때문에 D를 방문하고 부모노드 B로 다시 돌아가게 됩니다. B에서 모든 노드에 방문했기 때문에 A로 돌아가서 A를 방문하고 오른쪽 서브트리로 향하게 됩니다.

아래와 같이 C B D A E F 순서로 방문합니다.

후위순회는 전위순회와 반대로 자식노드를 모두 방문한 다음에야 자기자신(루트)를 방문하게 됩니다. A에서 시작해서 왼쪽 자식노드 B로 향하고, B에도 자식노드가 있기 때문에 C와 D를 방문하고 나서야 자기자신 B를 방문하게 됩니다. 

따라서, 순서는 C D B F E A가 됩니다.

 

BFS는 각 레벨의 노드를 모두 방문하고, 다음 레벨로 넘어가서 방문을 시작합니다. 그래서 A를 방문하고, 다음 레벨인 B, E를 방문하고, 마지막 레벨인 C, D, F를 방문하게 됩니다.

따라서 A, B, E, C, D, F 순서로 방문하게 됩니다.

코드를 한 번 살펴보죠.(전체코드는 게시글 가장 밑에 있습니다)

template<typename T>
void BTree<T>::_preOrder(Node<T>* root) const
{
	std::cout << root->data << " ";
	if (root->left)
		_preOrder(root->left);
	if (root->right)
		_preOrder(root->right);
}

template<typename T>
void BTree<T>::_inOrder(Node<T>* root) const
{
	if (root->left)
		_inOrder(root->left);
	std::cout << root->data << " ";
	if (root->right)
		_inOrder(root->right);
}

template<typename T>
void BTree<T>::_postOrder(Node<T>* root) const
{
	if (root->left)
		_postOrder(root->left);
	if (root->right)
		_postOrder(root->right);
	std::cout << root->data << " ";
}

template<typename T>
void BTree<T>::BFS() const
{
	std::queue<Node<T>*> q;

	if (!root)
		return;

	std::cout << "BFS : ";
	//search node position by using BFS
	q.push(root);

	while (!q.empty())
	{
		Node<T>* curNode = q.front();
		q.pop();
		std::cout << curNode->data << " ";
		if (curNode->left)
			q.push(curNode->left);

		if (curNode->right)
			q.push(curNode->right);
	}
}

전위, 중위, 후위 순회는 재귀로 구현되었으며, 단순히 루트를 방문하는 순서만 변경되었습니다. 여기서 값을 출력했을 때 방문했다고 정의합니다.

BFS의 경우에는 큐로 구현이 되었습니다. C++의 STL <queue> 헤더를 사용해서 구현을 했습니다. DFS나 BFS는 그래프에서 조금 더 자세히 다루어 보도록 하겠습니다.

 

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

(*Inorder 중위순회가 아까 설명했던 것과 순서가 다른데, 제 코드에서는 비어있는 노드부터 순서대로 채워서 F 노드가 E의 오른쪽이 아닌 왼쪽에 존재해서 다르게 나오고 있습니다.)

 

전체코드를 보기전에 트리의 성질에 대해 정리하고 마무리하겠습니다.

1. 트리는 하나의 루트노드를 가집니다. 이 루트노드는 부모노드가 존재하지 않습니다.

2. 트리의 서로 다른 임의의 두 노드에 대해서 두 노드를 연결하는 경로는 유일합니다. 그렇기 때문에 트리의 브랜치 개수는 반드시 트리의 노드 수 - 1입니다.

3. 브랜치의 방향을 무시했을 때, 트리에는 싸이클이 존재하지 않습니다.

4. 그래프의 한 종류로 싸이클이 존재하지 않는 연결 그래프이며, DAG(Directed Acyclic Graph); 방향성이 있는 비순환 그래프의 한 종류이기도 합니다.

 

 

전체코드는 다음과 같습니다. 여기서는 단순히 이진 트리의 구성만 보여주기 위해서 데이터 삽입 함수만 구현하였습니다..(사실 삭제는 구현하기에 까다로워서 Binary Search Tree 이진탐색트리에 대해서 정리할 때 구현을 해보도록 하겠습니다)

트리의 데이터 삽입은 BFS로 탐색하면서 비어있는 공간이 있으면 추가하도록 했습니다. -> 그래서 F노드가 E노드의 왼쪽 자식노드가 됩니다.

+) 그리고 보통 알고리즘 문제를 풀때는 이렇게 트리를 구현하지 않고.. 벡터를 사용해서 조금 간단하게 구현하는게 대부분입니다. 이렇게 구현해서 문제를 풀기에는 시간이 너무나 촉박합니다... 그래프에 대해서 정리할때, 벡터를 사용해서 문제를 한 번 풀어보도록 하겠습니다.

/* BTree.h */
#ifndef BTREE_H
#define BTREE_H
#include <queue>

const int max_degree = 2;

template<typename T>
class Node {
public:
	Node(const T& data) : data(data), left(nullptr), right(nullptr), parent(nullptr) {}
	~Node();

	T data;
	Node *parent, *left, *right;
};

template<typename T>
Node<T>::~Node()
{
	delete child;
}

template<typename T>
class BTree
{
public:
	BTree() : count(0), root(nullptr) {}
	void insert(const T& data);
	bool empty() const;
	int size() const;
	void Traversal() const;
	void DFS() const;
	void BFS() const;
	
private:
	void _insert(Node<T>* root, Node<T>* newNode);
	void _preOrder(Node<T>* root) const;
	void _inOrder(Node<T>* root) const;
	void _postOrder(Node<T>* root) const;
	void _dfs(Node<T>* root) const;

	int count;
	Node<T>* root;
};

template<typename T>
void BTree<T>::insert(const T& data)
{
	if (empty())
	{
		root = new Node<T>(data);
		++count;
	}
	else
	{
		Node<T>* newNode = new Node<T>(data);
		_insert(root, newNode);
	}
}

template<typename T>
void BTree<T>::_insert(Node<T>* root, Node<T>* newNode)
{
	std::queue<Node<T>*> q;
	
	if (!root)
		return;

	//search node position by using BFS
	q.push(root);

	while (!q.empty())
	{
		Node<T>* curNode = q.front();
		q.pop();

		if (curNode->left == nullptr)
		{
			curNode->left = newNode;
			return;
		}
		else
			q.push(curNode->left);

		if (curNode->right == nullptr)
		{
			curNode->right = newNode;
			return;
		}
		else
			q.push(curNode->right);
	}

	return;
}

template<typename T>
bool BTree<T>::empty() const
{
	return (count == 0);
}

template<typename T>
int BTree<T>::size() const
{
	return count;
}

template<typename T>
void BTree<T>::Traversal() const
{
	if (root)
	{
		//PreOrder
		std::cout << "Preorder : ";
		_preOrder(root);
		std::cout << "\n";
		//InOrder
		std::cout << "Inorder : ";
		_inOrder(root);
		std::cout << "\n";
		//PostOrder
		std::cout << "Preorder : ";
		_postOrder(root);
		std::cout << "\n";
	}
}

template<typename T>
void BTree<T>::_preOrder(Node<T>* root) const
{
	std::cout << root->data << " ";
	if (root->left)
		_preOrder(root->left);
	if (root->right)
		_preOrder(root->right);
}

template<typename T>
void BTree<T>::_inOrder(Node<T>* root) const
{
	if (root->left)
		_inOrder(root->left);
	std::cout << root->data << " ";
	if (root->right)
		_inOrder(root->right);
}

template<typename T>
void BTree<T>::_postOrder(Node<T>* root) const
{
	if (root->left)
		_postOrder(root->left);
	if (root->right)
		_postOrder(root->right);
	std::cout << root->data << " ";
}

template<typename T>
void BTree<T>::DFS() const
{
	if (root)
	{
		std::cout << "DFS : ";
		_dfs(root);
		std::cout << "\n";
	}

	return;
}

template<typename T>
void BTree<T>::_dfs(Node<T>* root) const
{
	std::cout << root->data << " ";
	if (root->left)
		_dfs(root->left);
	if (root->right)
		_dfs(root->right);
}

template<typename T>
void BTree<T>::BFS() const
{
	std::queue<Node<T>*> q;

	if (!root)
		return;

	std::cout << "BFS : ";
	//search node position by using BFS
	q.push(root);

	while (!q.empty())
	{
		Node<T>* curNode = q.front();
		q.pop();
		std::cout << curNode->data << " ";
		if (curNode->left)
			q.push(curNode->left);

		if (curNode->right)
			q.push(curNode->right);
	}

	std::cout << "\n";
}

#endif