[자료구조] 트리 (Tree)

개념

트리는 원소들을 계층적으로 저장하는 추상 데이터 타입이다. 최상위 원소를 제외하고, 각각의 원소는 하나의 부모 원소와 0 또는 여러 개의 자식 원소를 갖고 있다.

특성

일반적으로 트리는 다음 조건을 만족하는 하나 이상의 노드(node)들로 구성된 유한 집합 T를 말한다.

T의 원소 중 근 노드(root node)라 불리우는 특정한 1개의 노드가 존재한다.
근 노드를 제외한 나머지 노드들은 서로 분리된 부분 집합이다.
순환(cycle)을 허용하지 않는다. 처음과 끝의 경로가 같은 단순 경로를 사이클(cycle)이라 한다. 트리는 그래프의 부분 집합으로서, 그래프를 형성하는 정점 가운데서 어떠한 두 정점 사이에도 사이클이 형성되지 않은 연속된 그래프(connected graph)라고도 할 수 있다.

용어

노드(node)는 트리를 구성하는 기본 요소이며 레코드, 원소, 데이터 필드 등과 같이 단위 정보를 나타내는 항목을 말한다.
근 노드(root node)는 트리의 제일 상위 계층에 속하는 노드이며, 1 레벨에 있는 단 한 개의 노드이다.
서브 트리(subtree)는 트리에서 근 노드를 제거했을 때 생기는 하위 계층의 트리를 말한다. 각 서브 트리의 근 노드를 제거하면 다시 새로운 서브 트리가 생긴다.
차수(degree)는 어느 노드에서의 부 트리의 개수 혹은 가지의 개수이다.
트리의 차수는 트리를 형성하는 모든 노드의 차수 중에서 최대치를 말한다.
단 노드 또는 단말 노드(terminal node 또는 leaf)는 차수가 0인 노드 즉 서브 트리가 없는 노드를 말한다.
간 노드 또는 가지 노드(nonterminal node)는 차수가 0이 아닌 노드 즉 부 트리가 있는 노드이다. 단말 노드를 제외한 모든 노드가 해당된다.
부모 노드(parent node) 임의의 노드에서 바로 상위의 계층에 있는 노드이다.
형제 노드(brother node)는 부모 노드가 같은 노드들의 집합이다.
자식 노드(children node)는 임의의 노드에서 바로 하위의 계층에 있는 노드들의 집합이다.
조상(ancestors)은 특정 노드에서 근 노드에 이르기까지의 경로 상에 존재하는 모든 노드들의 집합이다.
자손(descendants)는 특정 노드의 하위 계층에 있는 모든 노드들의 집합이다.
레벨(level)은 근 노드를 레벨 1로 하여 하위계층으로 내려가면서 1씩 증가하는 번호이다. 레벨 m인 노드의 자식 노드는 레벨 m+1로 정의 하는데 계층 번호가 된다.
높이(height) 또는 깊이(depth)는 트리의 단말 노드의 레벨 중에서 최대인 레벨수이다.
트리군(forest)는 서로 독립된 즉 분리된 트리들의 집합이다.