본문 바로가기
알고리즘

알고리즘 - 트리, 이진트리

by 개발자 포비 2023. 2. 12.

오늘은 트리에 대해서 알아보도록 하겠습니다.

트리란 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다.

 

트리를 이루는 구성요소로는 '노드'와 '간선'으로 이루어져 있다.

간선으로 이루어진 그래프와는 '계층'적인 구조를 가지는 것이 특징이다.

 

트리의 구조

그 외에도 트리는 이러한 성질을 가지고 있다.

1) N개의 노드를 가진 트리는 항상 N-1개의 간선을 지닌다.

2) 트리에 존재하는 한 노드에서 어떠한 노드로 가는 경로는 항상 유일해야 한다.

 

트리를 잘 사용하기 위해서는 트리와 관련된 용어에 대해서 알아보아야 한다.

- 루트 노드 : 최상위 계층의 노드
- 깊이(depth)  : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 (aka. 몇 층?)
- 높이(height) : 가장 깊숙히 있는 노드의 길이(max(depth)) 
- 크기 : 자신을 포함한 모든 자손 노드의 개수
- 노드의 차수 : 부(하위)트리 갯수/간선수 = 각 노드가 지닌 가지의 수
- 트리의 차수 : 트리의 최대 차수

- 단말 노드(leaf node) : 자식이 없는 노드
- 내부 노드 : 리프 노드가 아닌 노드
- 링크 : 노드를 연결하는 선 (edge, branch라고도 부름)
- 형제 : 같은 부모를 가지는 노드

 

 작성된 코드를 통해 대략적인 구조에 대해 알아보도록 하겠습니다.

using NodeRef = shared_ptr<struct Node>;

struct Node
{
	Node() {}
	Node(const string& data) : data(data) {};

	string			data;
	vector<NodeRef> children;
};

NodeRef CreateTree()
{
	NodeRef root = make_shared<Node>("R1 개발실");
	{
		NodeRef node1 = make_shared<Node>("디자인팀");
		root->children.push_back(node1);
		{
			NodeRef leaf = make_shared<Node>("전투");
			node1->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("경제");
			node1->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("스토리");
			node1->children.push_back(leaf);
		}
		NodeRef node2 = make_shared<Node>("프로그래밍 팀");
		root->children.push_back(node2);
		{
			NodeRef leaf = make_shared<Node>("서버");
			node2->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("클라");
			node2->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("엔진");
			node2->children.push_back(leaf);
		}
		NodeRef node3 = make_shared<Node>("아트 팀");
		root->children.push_back(node3);
		{
			NodeRef leaf = make_shared<Node>("배경");
			node3->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("캐릭터");
			node3->children.push_back(leaf);
		}
	}

	return root;
}

 위의 코드는 게임 회사의 한 개발실의 구성도를 트리의 개념으로써 나타낸 코드입니다. 따로 출력창을 보지 않아도 대략적인 개발실 트리가 어떠한 모양일지 예상이 갈 것이라고 생각합니다.

 

 

 그럼 트리 중에서도 가장 많이 사용되는 구조인 이진 트리에 대해서 알아보겠습니다.

 

 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 의미합니다. 이 때, 자식 노드는 왼쪽/오른쪽 자식으로 서로 구분되어진다. 

 

이진 트리는 모양에 따라 '편향 이진트리', '완전 이진트리', '포화 이진트리' , '힙 트리' 등의 이름으로 부르기도 합니다. 

 

다음 시간에는 그 중에서도 힙 트리에 대해서 알아보도록 하겠습니다. 포바~!

'알고리즘' 카테고리의 다른 글

알고리즘 - 힙 & 우선순위 큐  (0) 2023.02.12
다익스트라 알고리즘  (0) 2023.02.11
BFS - 너비 우선 탐색  (0) 2023.02.10
DFS - 깊이 우선 탐색  (0) 2023.02.10
자료구조 - 큐  (0) 2023.02.06

댓글