이번 글에서는 데이터 구조에서 중요한 개념인 비루트 이진 트리(Unrooted Binary Tree)에 대해 자세히 알아보겠습니다.
비루트 이진 트리의 정의
비루트 이진 트리는 사이클(cycle)이 없는 연결된 무방향 그래프(connected undirected graph)입니다. 일반적인 루트 트리와 달리 특정한 루트(root) 노드가 지정되어 있지 않다는 점이 가장 큰 특징입니다.
잎 노드(Leaf)와 내부 노드(Internal Node)
트리를 구성하는 정점(vertex)은 이웃(neighbor)의 수에 따라 두 가지로 분류됩니다.
- 잎 노드(Leaf): 이웃을 하나만 가지는 정점으로, 트리의 끝부분에 위치합니다.
- 내부 노드(Internal Node): 잎 노드를 제외한 나머지 정점들입니다.
여기서 정점의 차수(degree)란 해당 정점이 가진 이웃의 개수를 의미합니다. 따라서 노드가 둘 이상인 트리에서 잎 노드는 차수가 1인 정점이라고 정의할 수 있습니다.
자유 트리(Free Tree)
자유 트리(Free tree)는 비루트 이진 트리의 한 종류로, 모든 내부 노드가 정확히 차수 3을 가지는 트리를 말합니다. 즉, 각 내부 노드가 세 개의 이웃 정점과 연결되어 있는 형태입니다.
컴퓨터 과학에서의 활용
컴퓨터 과학에서 이진 트리는 일반적으로 루트가 있고 순서가 정해진(ordered) 형태로 데이터 구조에 사용됩니다. 하지만 비루트 이진 트리 역시 다음과 같은 분야에서 매우 중요하게 활용됩니다.
- 계층적 군집화(Hierarchical Clustering): 데이터 포인트 간의 유사도를 기반으로 계층 구조를 형성할 때 사용됩니다.
- 진화 트리 재구성(Evolutionary Tree Reconstruction): 생물학에서 종 간의 진화적 관계를 나타내는 계통수(phylogenetic tree)를 만들 때 핵심적으로 활용됩니다.
비루트 트리 예시
아래 이미지는 비루트 트리의 대표적인 예시를 보여줍니다. 루트가 없이 여러 정점이 균등하게 연결된 구조를 확인할 수 있습니다.
정리
비루트 이진 트리는 사이클 없는 연결 무방향 그래프로, 차수 1인 정점이 잎 노드가 되며, 모든 내부 노드의 차수가 3인 경우를 자유 트리라고 부릅니다. 데이터 구조 분야에서는 루트 트리가 주로 쓰이지만, 계층적 군집화나 진화 트리 분석처럼 방향성이 필요 없는 문제에서는 비루트 이진 트리가 더 적합한 모델이 됩니다.