값과 다른 노드를 가리키는 참조로 이루어진 노드들의 집합. 데이터를 한 줄로 늘어놓지 않는 비선형 구조이고, 계층을 표현한다. 파일 시스템, 조직도, HTML 문서 구조가 전부 트리다.
트리가 되는 조건
트리가 되려면 세 가지를 만족해야 한다. 루트 노드가 하나뿐이어야 하고, 어느 경로로도 자기 자신에게 되돌아올 수 없어야 하고, 자녀 노드의 부모가 하나뿐이어야 한다.
이 셋을 만족하는 그래프가 곧 트리다. 그래서 트리는 그래프의 특수한 경우이고, 정점이 N개면 간선은 정확히 N-1개다. 부모와 자식 관계가 정해지지 않은 것도 트리라고 부르는데(unrooted tree), 흔히 그리는 것은 루트를 정해둔 rooted tree다.
또 하나 중요한 성질은 재귀적이라는 것이다. 어떤 노드를 잡아도 그 노드와 자손들이 다시 하나의 트리, 곧 서브 트리를 이룬다. 트리를 다루는 코드가 거의 항상 재귀인 이유다.
관계를 부르는 말
관계를 부르는 말들은 이렇다. 노드와 노드를 잇는 선이 간선(edge)이고 구현에서는 참조다. 최상단 노드가 루트(root), 바로 위아래가 부모와 자녀, 같은 부모를 가진 노드들이 형제(sibling)다. 부모를 따라 루트까지 올라가며 만나는 모든 노드가 조상이고 자녀를 따라 내려가며 만나는 모든 노드가 자손이다. 자녀가 있으면 내부 노드, 없으면 리프(leaf)이고 외부 노드나 단말 노드라고도 한다.
크기를 재는 말
크기를 재는 말은 간선 수로 세는지 노드 수로 세는지가 문서마다 달라서 문제를 풀 때 정의를 확인해야 한다. 여기서는 간선 수 기준이다. 한 노드에서 다른 노드까지의 노드 시퀀스가 경로(path)다. 그 노드에서 가장 먼 리프까지의 간선 수가 높이(height)라 리프의 높이는 0이고, 루트에서 그 노드까지의 간선 수가 깊이(depth)라 루트의 깊이는 0이다. 레벨(level)은 깊이와 같은 뜻으로 쓴다. 자녀 노드의 수가 차수(degree), 두 노드 사이 최단 경로의 간선 수가 거리(distance), 자신을 포함한 자손 노드의 수가 크기(size)이고, 특정 레벨에 있는 노드의 수를 width라고 한다.
트리의 높이와 트리의 깊이와 루트의 높이는 셋 다 같은 값을 가리킨다.
높이가 곧 시간복잡도
높이가 중요한 이유는 그것이 곧 시간복잡도이기 때문이다. 트리를 쓰는 알고리즘은 대부분 루트에서 리프까지 한 번 내려간다. 노드가 N개일 때 높이가 log N이면 O(log N), 한쪽으로 늘어져 높이가 N이면 O(N)이 된다. 이진 탐색 트리가 빠르기도 하고 느리기도 한 이유, 균형 트리가 필요한 이유가 전부 여기에 있다.