데이터 구조에서 루트 트리(Rooted Tree)와 비루트 트리(Unrooted Tree)의 차이 완벽 정리

트리(tree)는 컴퓨터 과학에서 가장 널리 사용되는 계층적 자료구조 중 하나입니다. 그런데 트리는 크게 루트 트리(rooted tree, 뿌리 있는 트리)와 비루트 트리(unrooted tree, 뿌리 없는 트리)로 나눌 수 있으며, 이 두 구조는 근본적인 성격이 서로 다릅니다. 이번 글에서는 두 트리의 개념을 예시와 함께 살펴보고, 핵심적인 차이점을 명확하게 정리해 보겠습니다.

루트 트리(Rooted Tree)의 예시

루트 트리는 이름 그대로 ‘뿌리(root)’가 되는 특정 노드가 존재하는 트리입니다. 루트는 트리 전체의 시작점 역할을 하며, 모든 노드는 이 루트로부터 간선(edge)을 따라 연결됩니다.

위 그림처럼 루트 트리에서는 부모-자식 관계가 명확하게 정의되며, 방향성이 존재합니다. 파일 시스템의 디렉터리 구조나 조직도 등이 대표적인 루트 트리의 실제 활용 사례입니다.

비루트 트리(Unrooted Tree)의 예시

반면 비루트 트리에는 특정한 루트 노드가 없습니다. 노드들이 간선으로 연결된 형태만 존재할 뿐, 어느 노드가 최상위에 있는지에 대한 정보는 없습니다.

비루트 트리는 주로 생물학의 계통수(phylogenetic tree) 분석에서 많이 사용됩니다. 종들 간의 진화적 관계를 나타낼 때, 공통 조상의 위치를 확정하지 않은 채 종들 사이의 상대적인 관계만 표현하는 경우가 많기 때문입니다.

루트 트리와 비루트 트리의 기본적인 차이

두 트리 구조의 가장 중요한 차이점은 다음과 같습니다.

• 루트 트리: 자손(descendant)을 가진 각 노드는 해당 자손들의 추론된 최근 공통 조상(most recent common ancestor)을 나타냅니다. 또한 일부 트리에서는 간선의 길이를 시간의 추정치로 해석할 수 있습니다. 즉, 진화나 흐름의 방향과 순서까지 표현할 수 있는 구조입니다.
• 비루트 트리: 조상이 되는 루트가 존재하지 않습니다. 비루트 트리는 분기(branching)의 순서만 표현하며, 마지막 공통 조상이 어디에 위치했는지는 나타내지 않습니다.

한눈에 보는 비교

마무리

정리하면, 루트 트리는 계층 구조와 조상-자손 관계를 명확히 표현하는 반면, 비루트 트리는 요소들 간의 연결 관계와 분기 구조만 표현합니다. 문제의 목적에 따라 적절한 트리 구조를 선택하는 것이 효율적인 데이터 표현과 알고리즘 설계의 첫걸음입니다.