[자료구조] 트리(Tree)

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

트리(Tree)

 

트리의 예시

 

개요

　지금까지 다룬 자료 구조는 순방향과 역방향을 지원하는 선형 자료 구조였다. 이러한 구조는 특정 데이터를 검색할 때 순서대로 자료를 찾아나가야 하는 문제점과, 데이터를 저장하기 위해 일정한 공간을 미리 할당해야 하는 등 제한적인 구조를 갖고 있어 복잡한 문제를 해결하는 데 어려움이 있다. 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다.

 

　계층적 문제(Hieararchy Problem)란 계층적 속성을 갖는 자료를 선형 구조로 표현하기 어렵다는 것을 의미한다. 다음과 같은 조직도를 표현한다고 해보자.

 

 

　이러한 조직을 표현하기 위해서, 기존에 배운 선형 자료 구조인 배열과 벡터, 리스트를 이용해 표현하기는 어려워 보인다.

 

　순환 종속성(Cyclic Dependency) 문제란, 두 개 이상의 요소가 서로 순환적으로 의존하여 발생하는 문제를 의미한다. 다음과 같은 그래프를 표현한다고 해보자.

 

 

　이 또한 기존에 배운 선형 자료 구조인 배열과 벡터, 리스트를 이용해 표현하기는 어려워 보인다.

 

　따라서 이러한 단점을 개선할 비선형 자료 구조를 공부해 보도록 하자. 비선형 자료 구조는 크게 트리와 그래프로 나뉘며, 각 데이터의 항목들이 계층적으로 연결되어 있지 않은 것을 의미한다. 즉, 하나의 자료 뒤에 여러 자료가 존재하며 데이터들이 서로 다른 방향으로 연결되어 있다. 이러한 비선형 자료 구조를 이용한다면, 선형 자료 구조와 달리 데이터를 더욱 효율적으로 검색하고 저장할 수 있을 것으로 기대할 수 있다.

---

특징

　트리(Tree)란 계층적인 구조를 갖고 있는 자료 구조다. 여기서 '계층(Hierarchy)'의 의미는, 각 노드의 방향성에 있어 계층 구조를 갖는다는 것을 의미한다. 즉, 전체적인 구조는 계층적이지 않다는 것을 의미한다. 트리의 특징은 다음과 같다.

• 단일 루트: 모든 노드들은 하나의 루트(root) 노드에서 시작하며, 모든 경로는 루트 노드로부터 시작
• 방향성: 각각의 간선(edge)은 방향성을 가지며, 부모에서 자식으로만 연결
• 비순환성: 임의의 노드에서 출발하여 자기 자신으로 되돌아올 수 없음

 

　트리는 이러한 구조를 갖고 있어 데이터 삽입, 삭제, 검색 등의 작업이 효율적으로 이루어지며 데이터의 계층적인 관계를 표현하기 용이하다. 하지만, 불균형한 트리일 경우 검색 속도가 느려질 수 있으며, 트리의 크기가 커질 경우, 메모리 공간을 많이 차지한다는 단점이 존재한다. 이때 불균형한 트리(Unbalanced Tree)란 각 노드의 서브 트리(Sub Tree)가 한쪽으로 치우쳐진 형태의 트리를 말한다.

 

불균형한 트리 예시

 

　다음은 불균형한 트리의 예시다. 왼쪽 서브 트리의 높이가 오른쪽 서브트리의 높이보다 작아 불균형한 상태다.

---

구현

　다시 한번 예시로 사용한 회사의 조직도를 갖고 와보자.

 

 

　지금부터 이 조직도를 트리로 구현해 보며, 트리에 익숙해지는 시간을 가져보자.

 

#include <iostream>
using namespace std;

struct node
{
	string _position;
	node* _left, * _right;
};

　위의 조직도를 보면 한 노드는 직책(position)과 두 개의 자식 노드(_left, _right)를 갖고 있으므로, node를 구조체로 선언해 준다.

 

class Tree
{
	node* _root;

public:
	static Tree CreateRoot(const string& pos) // 루트 노드 생성
	{
		Tree tree;
		tree._root = new node{ pos, NULL, NULL };

		return tree;
	}

　루트 노드 _root를 선언해 주고, 루트 노드를 생성하는 함수 CreateRoot()를 작성해 준다. 이때 static 키워드가 붙어있는데, 이는 Tree 클래스의 인스턴스를 생성하지 않고 호출할 수 있게 위해서다. 이렇게 하면 객체를 생성할 필요가 없으므로 코드가 더욱 간결해지고, 메모리 사용량도 줄어든다.

 

	static node* Find(node* node, const string& value)
	{
		if (!node) // 노드가 비었을 때, 혹은 찾고자 하는 값이 없을 때
			return NULL;

		if (node->_position == value) // 찾고자 하는 값을 루트노드가 갖고 있는지 검사
			return node;

		auto firstFind = Tree::Find(node->_left, value);
		
		if (firstFind) // _left 서브트리의 값이 있을 때
			return firstFind;

		return Tree::Find(node->_right, value);
	}

　노드를 찾는 Find() 함수다. 이진트리에서 탐색은 루트 노드애서 시작하여 찾고자 하는 값을 가진 노드를 찾을 때까지 왼쪽 혹은 오른쪽 서브트리를 순회하는 과정이다. 따라서 다음과 같은 조건들이 필요하다.

• 노드가 비어있는지 확인 → 비어 있으면 NULL 반환
• 노드가 찾고자 하는 값을 갖고 있는지 확인 → 갖고 있으면 해당 노드를 반환
• 노드의 자식 노드 중에 값을 갖고 있는지 확인 → 갖고 있으면 자식 노드 반환

　이 과정을 값을 찾을 때까지, 혹은 NULL을 반환할 때까지 반복한다. 이때 Find() 함수에 static 키워드가 붙은 이유는 Find() 함수가 클래스의 멤버 함수지만, 멤버 변수에 접근할 필요가 없기 때문이다. 따라서 메모리 사용량을 줄이는데 도움이 되고, 코드가 더 간결해진다.

 

	bool AddSub(const string& upper, const string& sub) // 부모노드에 sub를 다는 함수
	{
		auto parentsNode = Tree::Find(_root, upper);

		if (!parentsNode) // 부모노드가 존재하지 않는 경우
		{
			cout << upper << "을(를) 찾을 수 없습니다: \n";
			return false;
		}

		if (parentsNode->_left && parentsNode->_right) 
        // 부모노드 아래에 left, right가 모두 있는 경우
		{
			cout << upper << " 아래에 " << sub << "을(를) 추 가할 수 없습니다. \n";
			return false;
		}

		if (!parentsNode->_left) // 왼쪽 노드가 비어있는 경우
			parentsNode->_left = new node{ sub, NULL, NULL };
		else
			parentsNode->_right = new node{ sub, NULL, NULL };

		cout << upper << " 아래에 " << sub << "을(를) 추가했습니다.\n";
		
		return true;
	}
};

　부모 노드에 자식을 다는 AddSub() 함수를 추가해 준다. 먼저 부모 노드가 존재하는지 확인하기 위해, 이전에 작성한 Find() 함수로 찾아본다. 만약 부모 노드가 존재하지 않거나, 부모 노드 아래에 자식 노드가 꽉 차있으면 false를 반환한다.

　이 과정을 거친 후, 왼쪽 혹은 오른쪽이 비어 있다면 부모 노드 아래에 자식 노드를 추가해 주고 true를 반환하면 된다.

 

int main()
{
	auto tree = Tree::CreateRoot("CEO"); // CEO 루트 노드 추가

	tree.AddSub("CEO", "부사장"); // CEO -> 부사장
	
	tree.AddSub("부사장", "IT부"); // 부사장 -> IT부
	tree.AddSub("부사장", "홍보부"); // 부사장 -> 홍보부

	tree.AddSub("홍보부", "언론팀"); // 홍보부 -> 언론팀
	tree.AddSub("홍보부", "전략팀"); // 홍보부 -> 전략팀

	tree.AddSub("IT부", "DB"); // IT부 -> DB
	tree.AddSub("IT부", "업무지원팀"); // IT부 -> 업무지원팀
}

　마지막으로 main() 함수에 다음과 같이 작성하면 된다.

 

실행 결과

---

요약

트리(Tree)
1. 정의: 계층적 구조를 갖는 비선형 자료구조
2. 특징
　a. 단일 루트
　b. 방향성
　c. 비순환성
3. 장점
　a. 데이터 삽입, 삭제, 탐색의 효율성 높음
　b. 데이터의 계층적 관계 표현 용이
4. 단점
　a. 불균형한 트리 문제
　b. 트리의 크기가 커질 경우 메모리 공간 많이 사용