백과

뿌리목(rooted tree)이라고도 한다. 폐로를 가지지 않는 유향 그래프 T에서, 어느 가지의 종점도 되어 있지 않은 1개의 노드 υ₀가 존재하고, 해를 제외한 다른 각 노드에는 그 노드를 종점으로 하는 가지가 꼭 하나 존재하는 것을 유향 트리라고 한다(그림).

유향 트리

ⓒ 한국사전연구사 | 저작권자의 허가 없이 사용할 수 없습니다.

υ₀를 유향 트리 T의 근(root)이라 하고 어느 가지의 시점도 되어있지 않은 노드를 잎(leaf)이라고 부른다. 그림에서 □로 표시되어 있는 노드가 잎이다. 잎 이외의 노드를 분기 노드(branch node)라고 한다. 노드 u에서 나와서 노드 υ로 들어가는 가지가 존재할 때, u를 υ의 부모(parent), υ를 u의 자식(child)이라 한다. 또, u에서 υ에의 경로가 존재할 때, u를 υ의 조상(ancestor), υ를 u의 자손(descendant)이라고 한다. 같은 부모를 갖는 자식끼리는 형제(brothers)라고 한다.

노드가 갖는 자식의 수를 그 노드의 분기수 또는 차수(degree)라고 한다. 모든 노드의 분기수가 n(n≧2)인 유향 트리를 n진 트리(다진 트리 참고)라고 한다. 특히 n=2인 경우가 2분 트리이다. 데이터 구조로서는 2분 트리에 의한 표현이 많이 쓰이고 있다. 〈참조어〉 그래프, 순서 트리, 경로, 분기 노드