트리(Tree)의 개념

트리는 계층적인 자료를 표현하는데 이용되는 자료구조이다.

인공지능 문제에서도 트리가 사용되는데, 대표적인 것이 결정 트리(decision tree)이다. 결정 트리는 인간이나 컴퓨터의 의사결정 구조를 표현하는 한 가지 방법이다.

트리의 용어들

트리의 구성 요소를 노드(node)라고 한다. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 이들 중 하나의 노드는 루트(root) 노드라 불리고 나머지 노드들은 서브트리(subtree)라고 불린다. 아래 그림에서 계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 된다.

트리에서 루트와 서브트리는 선으로 연결된다. 이 연결선을 간선 또는 엣지(edge)라고 한다.

노드들간에는 부모 관계, 형제 관계, 조상과 자손 관계가 존재한다. 아래 그림에서 A는 B의 부모 노드(parent node)가 되고, 반대로 B는 A의 자식 노드(children node)가 된다. B와 C와 D는 형제 관계(sibling)이다.

조상 노드(ancestor node)는 루트 노드에서 임의의 노드까지 경로를 이루는 노드를 말하며, 자손 노드(descendent node)는 임의의 노드의 서브트리에 속하는 모든 노드를 말한다.

자식 노드가 없는 노드를 단말 노드(terminal node 또는 leaf node)라고 하며, 그 반대는 비단말 노드(nonterminal node)이다.

Untitled

노드의 차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다. 아래 그림에서 루트 노드의 경우 자식 노드가 3개이기 때문에 차수도 3이다. 단말 노드는 차수가 0인 노드가 된다.

트리의 차수는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수이다. 아래 그림에서 A와 B 노드의 차수가 3으로 가장 크므로 전체 트리의 차수는 3이 된다.

트리에서의 레벨(level)은 트리의 각층에 번호를 매기는 것으로서 정의에 의하여 루트의 레벨은 1이 되고 한 층씩 내려갈 수록 1씩 증가한다. 아래 그림에서 A의 레벨은 1이고 B의 레벨은 2이다. 트리의 높이(height)는 트리가 가진 최대 레벨을 말한다. 아래 트리의 높이는 3이다.

나무가 모이면 숲이 되듯이 트리들의 집합을 포레스트(forest)라고 한다.

Untitled

Untitled

트리의 표현

컴퓨터에서 트리를 표현하는 가장 일반적인 방법은 아래 그림 (a)와 같이 노드 구조를 이용하여 표현하는 것이다. 각 노드는 데이터를 저장하는 데이터 필드와 자식 노드를 가리키는 링크 필드를 갖는다. 이때 링크 필드의 개수는 자식 노드의 개수 즉 노드의 차수가 되어야 한다.

Untitled

문제는 일반적인 트리에서 각 노드들은 임의의 개수의 자식을 가질 수 있다는 것이다. 자식 노드의 개수가 일정하지 않으면 노드의 구조가 복잡해진다. 이것은 프로그램을 상당히 복잡하게 만드므로 실제로는 위 그림의 (b)와 같이 두 개의 자식 노드를 사용하는 이진트리(binary tree)가 많이 사용된다.