[Algorithm] 트리(Tree)구조란 무엇인가?

 트리(Tree)의 정의 

트리는 정점(Node)과 선분(Branch)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태이다.

가족의 계보(족보), 연산수식, 회사 조직 구조도, 히프등을 표현하기에 적합하다.

 

 

 

 트리(Tree) 관련용어 

노드(Node) : 트리의 기본요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것

EX : A, B, C, D, E, F, G, H, ,I ,J ,K ,M

 

근 노드(Root Node) : 트리의 맨 위에 있는 노드

EX : A

 

디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수

EX : A=3 , B=2, C=1

 

단말 노드(Terminal Node) : 자식이 하나도 없는 노드

EX : K, L, F, G, M, I, J

 

비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드

EX : A, B, C, D, E, H

 

조상 노드(Ancestors Node) : 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들

EX : M의 조상 노드는 H, D, A

 

자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들

EX : D의 자식노드는 : H, D, A

 

부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들

EX : E,F의 부모노드는 B

 

형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들

EX : H의 형제 노드는 I, J

 

Level : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L_1

EX : H의 레벨은 3

 

깊이(Depth) : Tree에서 노드가 가질 수 있는 최대의 레벨

EX : 위 트리의 깊이는 4

 

숲(Forest) : 여러개의 트리가 모여있는 것

EX : 위 트리에서 근 노드 A를 제거하면 B,C,D를 근 노드로 하는 세 개의 트리가 있는 숲이 생긴다.

 

트리의 디그리 : 노드들이 디그리 중에서 가장 많은 수

EX : 노드 A나 D가 세 개의 디그리를 가지므로 위 트리의 디그리는 3이다.