트리(Tree)란?

트리(Tree)는 데이터 사이의 계층 관계를 표현하는 비선형 자료구조를 의미한다.

트리는 노드(Node)와 가지(Edge)로 구성된다.

아래 그림에서 A, B, C 등이 노드에 해당하며 해당 노드들을 연결하는 선들이 가지다.

 

트리의 가장 위쪽에 있는 노드를 루트(Root), 가장 아래쪽에 있는 노드를 리프(Leaf)라고 한다.

리프는 단말 노드(Terminal Node), 외부 노드(External Node)라고도 하며,

물리적으로 가장 아래쪽에 위치한다는 의미가 아니라 해당 노드 아래로 가지가 더 이상 뻗어나갈 수 없다는 의미이다.

 

리프를 제외한 노드(루프 포함)를 비 단말 노드(Non-Terminal Node), 내부 노드(Internal Node)라고도 한다.

어떤 노드와 노드가 가지로 연결되어 있을 때 위쪽에 있는 노드를 부모 노드(Parent Node), 아래쪽 노드를 자식 노드(Childe Node)라고 한다. 부모가 같은 노드를 형제 노드(Sibling Node)라고 한다.

 

루트에서 얼마나 멀리 떨어져 있는지를 나타내는 것을 레벨(Level)이라 한다. 가장 위쪽에 있는 루트의 레벨은 0이고, 가지가 하나씩 아래로 뻗어 내려갈 때마다 레벨이 1씩 증가한다.

 

각 노드가 갖는 자식의 수를 차수(Degree)라고 한다. 아래 그림에서 노드 D의 차수는 2이다.

모든 노드의 차수가 N 이하인 트리를 N진 트리라고 한다. 아래 그림은 차수가 2개 이하이므로 이진 트리이다.

 

루트에서 가장 멀리 있는 리프까지의 거리, 곧 리프 레벨의 최대값을 높이(Height)라고 한다.

아래 그림에서 트리의 높이는 3이다. 

 

어떤 노드를 루트로 하고 그 자손으로 구성된 트리를 서브 트리(Subtree)라고 한다. 

 

 

▶ 관련 링크