트리

트리란?

트리를 구성하는 요소는 노드(node)와 가지(edge)입니다.

각각의 노드는 가지를 통해 다른 노드와 연결되어있습니다.

 

그림 1

 

 

루트 (root)

: 트리의 가장 윗부분에 위치하는 노드

 

리프 (leaf)

: 트리의 가장 아랫부분에 위치하는 노드

  - 물리적으로 가장 아랫부분에 위치한다는 의미가 아니라 더 이상 뻗어나갈 수 없는 마지막에 노드가 위치한다는 의미

* 다른 용어로는 끝 노드(terminal node) 또는 바깥 노드(external node)라고도 합니다.

 

안쪽 노드

루트를 포함하여 리프를 제외한 노드를 안쪽 노드라고 합니다.

* 다른 용어로는 끝이 아닌 노드(non-terminal node)라고도 합니다.

 

자식 (child)

어떤 노드로부터 가지로 연결된 아래쪽 노드

* 리프는 자식을 가질 수 없습니다.

 

부모 (parent)

어떤 노드에서 가지로 연결된 위쪽 노드

* 루트는 부모를 가질 수 없습니다.

 

형제 (sibling)

같은 부모를 가지는 노드

 

조상 (ancestor)

어떤 노드에서 가지로 연결된 위쪽 노드 모두

 

자손 (descendant)

어떤 노드에서 가지로 연결된 아래쪽 노드 모두

 

레벨 (level)

루트로부터 얼마나 떨어져있는지에 대한 값

  - 루트의 레벨은 0이고 루트로부터 가지가 하나씩 아래로 뻗어나갈 때마다 레벨이 1씩 늘어납니다.

 

차수 (degree)

노드가 갖는 자식의 수

모든 노드의 차수가 n이하인 트리를 n진 트리라고 합니다.

그림1은 모든 노드의 자식이 3개 이하이므로 3진 트리입니다.

 

높이 (height)

루트로부터 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)

그림1 트리의 높이는 3입니다.

 

서브 트리 (subtree)

트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리

 

널 트리 (null tree)

노드, 가지가 없는 트리

 

순서 트리와 무순서 트리

형제 노드의 순서가 있는지 없는지에 따라 트리를 두 종류로 분류합니다.

순서를 따지면 순서 트리(ordered tree)

따지지 않으면 무순서 트리(unordered tree)라고 합니다.

 

 

 

출처 Do it! 자료구조와 함께 배우는 알고리즘 입문: 자바 편