트리(Tree)

1. 트리

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

트리는 하나의 기억공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 한다.

2. 트리 관련 용어

 

<트리 구조 및 용어>

이미지 출처: 클릭!

 

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

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

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

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

비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드 (Degree가 1 이상인 노드)

조상 노드(Ancestors Node): 루트 노드까지 이르는 경로상에 있는 노드들

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

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

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

레벨(Level) : 가지(Branch)로 뻗어나온 노드들을 같은 단계로 그룹화한 것

깊이(Depth, Height) : 제일 아래인 Level

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

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

 

 

읽어주셔서 감사합니다!

정처기 화이팅!