045 트리 ( Tree )

 

트리 ( Tree )

정점( Node, 노드 )과 선분( Branch, 가지 )을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태로 가족의 계보( 족보 ), 연산 수식, 회사 조직 구조도, 히프( Heap ) 등을 표현하기에 적합하다.

• 노드 ( Node ) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지( Branch )를 합친 것
  ex. A, B, C, D, E, F, G, H, I, J, K, L, M
• 근 노드 ( Root Node ) : 트리의 맨 위에 있는 노드
  ex. A
• 디그리 ( Degree, 차수 ) : 각 노드에서 뻗어나온 가지의 수
  ex. A = 3, B = 2, C = 1, D = 3
• 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수
  ex. 노드 A나 D가 3개의 디그리를 가지므로 위 트리의 디그리는 3이다.
• 단말 노드 ( Terminal Node ) = 잎 노드 ( Leaf Node ) : 자식이 하나도 없는 노드, 즉 디그리가 0인 노드
  ex. K, L, F, G, M, I, J
• 비단말 노드 ( Non-Terminal Node ) : 자식이 하나라도 있는 노드, 즉 디그리가 0이 아닌 노드
  ex. A, B, C, D, E, H
• 자식 노드 ( Son Node ) : 어떤 노드에 연결된 다음 레벨의 노드들
  ex. D의 자식 노드 : H, I, J
• 부모 노드 ( Parent Node ) : 어떤 노드에 연결된 이전 레벨의 노드
  ex. E, F의 부모 노드는 B
• 형제 노드 ( Brother Node, Sibling ) : 동일한 부모를 갖는 노드들
  ex. H의 형제 노드는 I, J
• Level : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1이다.
  ex. H의 레벨은 3
• 깊이 ( Depth, Hight ) : 어떤 Tree에서 노드가 가질 수 있는 최대의 레벨
  ex. 위 트리의 깊이는 4

---

길벗알앤디 (강윤석, 김용갑, 김우경), 정보처리 산업기사 필기 1권 핵심요약, 길벗(2019), p 49.