트리 Tree

Intro

• 트리에 대한 이해

트리의 개념

노드로 이루어진 자료 구조이며 계층적 모델이다.

트리는 하나의 루트 노드를 가지며 노드 A가 노드 B를 가리킬 때 A를 부모 노드 B를 A의 자식 노드 라고 한다.¹

트리 관련 용어

• 루트 노드(Root node) : 부모가 없는 노드 , 트리는 하나의 루트 노드 만을 가진다.

• 단말 노드(Terminal node 또는 leaf node) : 자식이 없는 노드

• 내부 노드(internal node) : 단말 노드가 아닌 노드

• 형제 노드(Sibling node) : 같은 부모를 가지는 노드

• 노드의 깊이(Depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

• 노드의 레벨(Level) : 트리의 특정 깊이를 가지는 노드의 집합

• 노드의 차수(Degree) : 각 노드가 지닌 가지의 수

• 트리의 차수(Degree of tree) : 트리의 최대 차수

• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리의 종류

• 이진 트리
  • 전 이진 트리
  • 포화 이진 트리
  • 완전 이진 트리
  • 힙
• 균형 트리
• 이진 탐색 트리

참고자료

정보통신기술 용어해설

1. 위키백과 ↩