트리(Tree)

트리(Tree)

트리는 사이클이 없고 엣지(간선)로 연결된 노드들의 집합이다

주요 용어

부모와 자식(Parent and Child): 서브트리 $T_{1}, T_{2}, \dots, T_{k}$ 의 각 루트는 $r$ 의 자식(child)이 되며, $r$ 은 각 서브트리 루트의 부모(parent)가 된다
형제(Siblings): 동일한 부모를 가진 서브트리의 루트들을 서로 형제(Siblings)라고 부른다
순서 트리(Ordered Tree): 서브트리 $T_{i}$ 들 사이에 일정한 순서가 정해져 있는 트리를 말한다
노드의 차수(Degree of a node): 한 노드가 가지고 있는 자식 노드의 개수이다
트리의 차수(Degree of a tree): 트리 내에 있는 노드들의 차수 중 최대값이다
리프 노드/단말 노드(Leaf): 차수가 0인 노드(즉, 자식이 없는 노드)를 말한다

경로 및 높이

두 노드 간의 경로: 노드의 시퀀스 $n_{1}, n_{2}, \dots, n_{k}$ 에서 $n_{i}$ 가 $n_{i + 1}$ 의 부모인 관계를 만족하는 수열을 의미한다
경로의 길이: 경로 상에 있는 엣지의 개수이다(즉, $n_{1}, n_{2}, \dots, n_{k}$ 경로의 길이는 $k - 1$ 이다)
노드의 깊이/레벨: 루트 노드에서 해당 노드까지 이르는 유일한 경로의 길이이다
노드의 높이: 해당 노드에서 리프 노드에 이르는 가장 긴 경로의 길이이다
트리의 높이: 루트 노드의 높이와 같다

트리의 표현

트리의 높이는 서브트리의 높이를 이용해 재귀적으로 정의하고 계산할 수 있다

$height (A) = max (height (B), height (C), height (D)) + 1$

하위 노드로의 확장 예시:

경로의 유일성: 루트 노드에서 트리 내의 임의의 노드 $v$ 에 이르는 경로는 반드시 오직 하나만 존재한다
노드와 엣지의 관계: 트리에 존재하는 총 노드의 개수가 $N$ 개일 때, 전체 엣지의 개수는 항상 $N - 1$ 개이다
진입 차수(Incoming Edge)의 규칙: 루트 노드는 위에서 들어오는 엣지가 없으며(0개), 이를 제외한 트리의 모든 노드는 자신에게 들어오는 엣지를 정확히 1개씩만 가진다

트리를 컴퓨터 메모리상에 구현할 때는 포인터를 활용한 연결 리스트(Linked List) 방식을 주로 사용하며, 트리의 형태에 따라 다음과 같은 구조적 고려사항이 존재한다

최대 차수(Maximun Degree)를 아는 경우의 표현:

한 노드가 기질 수 있는 최대 자식의 수만큼 노드 내에 고정된 크기의 포인터 배열을 선언하여 구현한다
한계점: 자식 노드가 적거나 없는 리프 노드의 경우, 사용되지 않는 포인터들이 모두 NULL로 채워지기 때문에 심작한 메모리 낭비가 발생한다

최대 차수를 모르는 일반적인 트리의 표현:

해결책(왼쪽 자식-오른쪽 형제 표현법):

구조적 규칙: 일반적인 트리를 이진 트리 형태로 메모리에 효율적으로 표현하기 위해 다음 두 가지 핵심 규칙을 적용한다