[자료구조] - 트리(Tree)[1] - 트리의 정의와 용어

 

 

 

트리의 정의와 트리에서 사용되는 용어들을 알아보도록 하겠습니다.

 

 

 

 

 

 

트리(Tree)

트리는 나무의 가지와 같은 형태의 자료구조입니다.

 

 

트리는 노드(Node)로 구성되는 유한집합으로, 다음의 조건을 만족해야 합니다.

1. 루트라 불리는 특별한 노드가 하나 존재합니다.
2. 루트가 아닌 나머지 노드들은 n개의 노드가 서로 중복되지 않는(disjoint) 집합 T1, ..., Tn으로 나누어지며, 각각의 노드 집합은 다시 트리입니다. 이때 이러한 트리를 루트의 서브트리(subtree)라 정의합니다.

 

위와 같이 루트 노드로부터 연결된 다른 노드들은 다시 각각이 트리가 되며, 이는 재귀적으로 계속됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

트리의 용어

 

노드 (Node)

원소(element)와 다른 노드로의 간선(혹은 가지 - egde, branch)으로 구성되는 트리의 기본 구성 단위

 

 

 

 

노드의 차수(Degree of Node)

해당 노드의 서브트리의 개수 혹은
해당 노드가 가진 간선(가지)의 개수

 

 

 

 

 

 

트리의 차수 (Degree of Tree)

트리에 있는 노드들의 차수 중에서 가장 큰 값

 

 

 

 

 

 

잎 (Leaf)

차수가 0인 노드

 

 

 

 

 

 

자식 (Child)

노드의 서브트리의 루트 노드

 

 

 

 

 

 

 

부모 (parent)

자식(child)의 역관계

 

 

 

 

 

 

 

형제 (Sibling)

부모(parent)가 동일한 노드

 

 

 

 

 

 

 

조상 (Ancestor)

한 노드로부터 루트 노드까지의 경로를 따라 존재하는 모든 노드들

 

 

 

 

 

 

 

 

자손 (Descendent)

한 노드 이후 존재하는 모든 모드들

 

 

 

 

 

레벨 (Level)

루트의 레벨은 1, (0으로 설정하는 경우도 있으며, 설정하기 나름입니다.)
루트의 자식의 레벨은 2
노드 X의 레벨이 k라면, X의 자식의 레벨은 k + 1

 

 

 

 

 

 

 

 

높이(Height) 또는 깊이(Depth)

트리의 최대 레벨(Level)