알고리즘

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

개발자 포비 2023. 2. 12. 21: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;
}

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

 

 

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

 

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

 

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

 

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