트리 (Tree)
트리 (Tree)에 대해 정리한 페이지입니다.
Tags
Algorithm
개요
트리(Tree)에 대해 정리한 페이지입니다.
트리 (Tree)
개념
트리(Tree)는 상위-하위의 계층적(Hierarchical) 구조를 갖는 비선형 자료 구조로, 노드(Node)들이 간선(Edge)으로 서로 연결되어 있는 자료 구조를 말합니다. 트리는 탐색형 자료 구조로 널리 사용되며, 특정 조건을 지키도록 구성된 트리에서는 배열이나 리스트를 사용하는 것보다 같은 작업을 더 빠르게 수행할 수 있습니다.
특징
트리의 특징은 다음과 같습니다.
사이클이 없음트리는 그래프의 일종이지만 사이클을 갖지 않습니다.
연결 그래프모든 노드는 반드시 연결되어 있습니다.
노드 수(N)와 간선 수(E)의 관계트리에서는 항상
E = N - 1의 관계가 성립합니다.유일한 경로두 노드 사이의 경로는 오직 하나만 존재합니다.
주요 용어
트리에서 사용하는 주요 용어에 대해 정리하면 다음과 같습니다.
노드(Node)트리의 각 원소를 말하며, 일반적으로 자료가 저장된 곳을 말합니다. 노드 사이에는 상/하위 관계가 존재하며, 상위 노드를
부모(Parent), 하위 노드를자식(Child)노드라고 부릅니다. 부모 노드가 서로 같은 두 노드는형제(Sibling)노드라고 부르며, 부모 노드와 그의 부모들을 통틀러선조(Ancestor), 자식 노드와 그의 자식들을 통틀어자손(Descendant)이라고도 부릅니다.간선(Edge)노드들을 서로 연결하고 있는 선을 말합니다.
루트(Root)트리의 가장 위에 있는, 부모가 없는 노드를 말합니다. 트리에는 오직 단 하나의 루트만 존재합니다.
깊이(Depth)루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 말합니다. 루트는 깊이가 0에 해당합니다.
높이(Height)트리의 최대 깊이를 말합니다.
리프(Leaf)자식이 없는 노드를 말합니다.
서브트리(Subtree)전체 트리 구조에서 어떤 노드를 루트로 하는 하위 트리를 말합니다.
트리의 주요 종류
트리의 주요 종류는 다음과 같습니다.
편향 트리(Skewed Tree)왼쪽 또는 오른쪽 서브 트리만 갖는, 한 쪽으로 기울어진 트리입니다. 즉, 모든 노드들은 자식을 하나만 갖으며 트리 구조 상 연결 리스트를 사용하는 것과 차이가 없습니다.
이진 트리(Binary Tree)각 노드가 최대 2개의 자식을 갖는 트리입니다.
이진 탐색 트리(Binary Search Tree)(왼쪽 서브 트리의 값) < (루트의 값) < (오른쪽 서브 트리의 값)의 규칙을 갖는 이진 트리입니다.
세그먼트 트리(Segment Tree)저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있게 구현한 트리입니다. 주로 구간 합, 구간 최솟값, 구간 최댓값 등 1차원 배열의 특정 구간에 대한 질문을 빠르게 대답하는 데 사용됩니다.
세그먼트 트리에 대한 내용은 다음 링크에 작성하였습니다.
힙(Heap)부모 노드의 값이 자식 노드의 값보다 항상 크거나(최대 힙), 작은(최소 힙) 완전 이진 트리입니다. 주로 우선순위 큐를 구현하거나, 힙 정렬에 사용됩니다.
트라이(Trie)문자열을 저장하고 탐색하는 데 특화된 트리로, 각 노드는 문자 하나를 나타내고 루트에서 리프까지의 경로가 하나의 문자열을 나타냅니다. 주로 자동 완성, 사전 검색, 문자열 검색 등에 사용됩니다.
트리의 순회 종류
트리의 순회란 트리의 노드를 체계적으로 방문하는 방법으로, 대표적으로 다음 3가지 순회 순서가 존재합니다.
전위 순회(Pre-order Traverse)(루트) → (왼쪽 서브 트리) → (오른쪽 서브 트리) 순서로 순회하는 것을 말합니다.
중위 순회(In-order Traverse)(왼쪽 서브 트리) → (루트) → (오른쪽 서브 트리) 순서로 순회하는 것을 말합니다.
후위 순회(Post-order Traverse)(왼쪽 서브 트리) → (오른쪽 서브 트리) → (루트) 순서로 순회하는 것을 말합니다.
구현
트리의 노드
1
2
3
4
5
class TreeNode<T> {
value: T, // 저장할 자료
parent: TreeNode<T>, // 부모 노드를 가리키는 포인터
children: Array<TreeNode<T>> // 자식 노드를 가리키는 포인터
}
트리의 순회
트리의 재귀적 속성을 이용하면 트리의 순회를 쉽게 구현할 수 있습니다.
1
2
3
4
5
6
7
8
const traversal = (root: TreeNode<number>) => {
console.log(root.value);
const length: number = root.children.length;
for (let i = 0; i < length; i++) {
traversal(root.children[i]);
}
};
트리의 높이
트리의 높이는 루트의 각 자식을 루트로 하는 서브 트리들의 높이를 각각 재귀 호출을 통해 계산하고, 그 중 최댓값에 1을 더한 것과 같습니다.
1
2
3
4
5
6
7
8
const height = (root: TreeNode<number>): number => {
let h = 0;
let length = root.children.length;
for (let i = 0; i < length; i++) {
h = Math.max(h, 1 + height(root.children[i]));
}
return h;
};
Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
const path = process.platform === "linux" ? "/dev/stdin" : "./algorithm/input.txt"; const input = require("fs").readFileSync(path).toString().split("\n"); const V = Number(input[0]); // 트리의 정점의 개수, 2 <= V <= 100_000 const graph = Array.from({ length: V }, () => []); for (let i = 1; i <= V; i++) { const arr = input[i].split(" ").map(Number); const start = arr[0] - 1; let index = 1; while (arr[index] !== -1) { const end = arr[index++] - 1; const distance = arr[index++]; graph[start].push([end, distance]); } } const traverse = (node, distance) => { distanceArr[node] = distance; graph[node].forEach((arr) => { if (distanceArr[arr[0]] === 1_000_000_001) { traverse(arr[0], distance + arr[1]); } }); }; let distanceArr = new Int32Array(V).fill(1_000_000_001); traverse(0, 0); let maxDistance = 0; let node = 0; for (let i = 0; i < V; i++) { if (distanceArr[i] > maxDistance) { node = i; maxDistance = distanceArr[i]; } } distanceArr = new Int32Array(V).fill(1_000_000_001); traverse(node, 0); console.log(Math.max(...distanceArr));