레벨

레벨(level)은 루트의 레벨을 레벨 1로 하고 자식으로 내려가면서 하나씩 더해지는 개념입니다. 즉, 깊이와 연관이 있습니다. 어떤 트리의 깊이(depth) 혹은 높이(height)는 트리가 가지는 최대 레벨을 의미합니다. 자료 구조 책을 보면 어떤 것은 루트의 레벨을 0으로 하기도 합니다. 이는 크게 신경 쓰지 않아도 됩니다. 다만 레벨을 1로 하면 이후에 나올 계산 과정이 조금은 편해지는 점이 있어 이 책에서는 루트 레벨을 1로 정했습니다.

루트를 가진 트리 말고 일반적인 정의의 트리(즉, 사이클이 없는 연결된 그래프)에서 노드와 에지 사이에는 아주 중요한 수식이 있습니다. 노드 개수를 n이라고 하고 에지 개수를 e라고 했을 때 다음 식이 성립하는데요.

e = n-1

이는 트리를 그린 후 그 수를 세어 보면 알 수 있습니다. 이 식이 중요한 이유는 이 트리에 에지가 하나라도 추가되면, 즉 e > n-1이 되는 순간 이 트리에는 사이클이 생겨서 더 이상 트리가 아니게 되기 때문입니다. 이 수식은 크루스칼 알고리즘에서 아주 중요한 역할을 합니다. 그래프 알고리즘을 다루는 장에서 다시 한 번 살펴보겠습니다.