오늘은 트리에 대해서 알아보도록 하겠습니다.
트리란 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다.
트리를 이루는 구성요소로는 '노드'와 '간선'으로 이루어져 있다.
간선으로 이루어진 그래프와는 '계층'적인 구조를 가지는 것이 특징이다.

그 외에도 트리는 이러한 성질을 가지고 있다.
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 |
댓글