트리(Tree)는 그래프의 일종이다. 이름의 tree는 나무를 뜻하는 것으로, 꼭 나뭇가지가 위로 뻗어 나가는 형상을 닮았다고 해서 이런 이름이 붙여졌다. 다음 조건을 만족하는 그래프를 트리라고 한다.
- 연결 그래프이다.
- 간선의 방향을 무시했을 때 사이클이 존재하지 않는다.
다음 그림에서 1, 2번 그래프는 트리이고, 3번은 트리가 아니다. 3번은 간선의 방향을 무시하면 사이클이 생기기 때문에 트리라고 할 수 없다. 위 두 조건을 만족하는 트리에서는 $E = V-1$이라는 성질을 추가로 가진다. 또한, 트리에서 어떤 두 정점을 잇는 경로는 유일하다.
트리의 구조
트리에서 가장 위에 있는 노드를 루트 노드(Root node) 혹은 루트라고 한다. 루트와 다른 노드 사이의 거리를 그 노드의 깊이(Depth) 혹은 레벨(Level)이라고 하고, 루트 노드의 깊이는 $0$이나 $1$이다.
위 트리에서 루트는 $A$이다. 루트의 깊이를 $0$이라고 하면 $B,C$의 깊이는 $1$, $D,E,F,G$의 깊이는 $2$다.
서로 인접한 두 노드에 대해서 더 깊이가 작은 노드를 부모 노드(Parent), 더 큰 노드를 자식 노드(Child)라고 한다. 예를 들어 $A$는 $B$와 $C$의 부모이고, $B$는 $A$의 자식이자 $D, E$의 부모다. 루트 노드는 부모가 없는 유일한 노드다.
자식이 하나도 없는 노드를 리프 노드(Leaf)라고 한다. $D,E,F,G$가 리프 노드이다.
거리가 2 이상인 연결된 두 노드에 대해서는 깊이가 작은 쪽을 조상(Ancestor), 큰 쪽을 자손(Descendant)라고 한다. $A$는 $D$의 조상이라고 할 수 있고, $F$는 $C$의 자손이라고 할 수 있다. 반면 $E$는 $C$의 자손이 아니다.
트리에서 차수(Degree)는 그래프와는 달리, 자신의 자식 노드의 수로 정의된다. 차수가 최대 $K$인 트리를 $K$진 트리라고 하며, 따라서 위 그림의 트리는 이진 트리이다.
서브트리(Subtree)는 어떤 트리에 포함되어 있는 트리이다. 트리는 재귀적인 속성을 띄기 때문에, 위 그림처럼 특정 노드로부터 아래쪽을 떼어내면 그 노드를 루트 노드로 가진 새로운 트리가 된다.