[Programmers] 12. 기본 자료구조: 트리 (Tree) (1): 트리의 기본 용어

illstandtall·2021년 4월 29일

programmers python 이진 트리 자료구조 트리

Programmers dev course

목록 보기

13/34

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

자료구조 5. 트리 (Tree)

정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조입니다.
그래프 중에서도 순환이 없는 그래프이기도 합니다.
뿌리(root) 노드에서부터 간선들이 마치 나무에서 뿌리로부터 잔가지로 뻗어나가듯이 가지치기된 구조를 말합니다.

트리 용어

루트노드 (Root Node)
- 트리의 시작점을 말합니다.
- 위 그림에서는 노드 $A$ 가 해당합니다.
단말(리프)노드 (Leaf Node)
- 트리의 가장 마지막 단계입니다. 더이상 가지치기를 할 수 없는 노드입니다.
- 위 그림에서는 노드 $K, L, F, G, M, I, J$ 를 말합니다.
내부 노드(Internal Node)
- 루트도 아니고 단말도 아닌 노드를 말합니다.
- 위 그림에서는 노드 $E, B, C, H, D$ 가 해당합니다.
부모와 지식관계
- 부모 노드 (Parent Node)
  - 루트에 더 가까운 노드입니다.
  - 위 그림에서 노드 $D$ 의 부모 노드는 노드 $A$ 입니다.
- 자식 노드 (Child Node)
  - 루트에서 조금 더 먼 노드입니다.
  - 위 그림에서 노드 $D$ 의 자식 노드는 노드 $H, I, J$ 입니다.
- 형제 노드 (sibling)
  - 같은 부모 노드를 공유하는 노드를 말합니다.
  - 위 그림에서 노드 $B, C, D$ 는 형제 노드 입니다.
- 조상 (ancestor)
  - 노드 자신의 모든 부모 노드를 말합니다.
  - 위 그림에서 노드 $M$ 의 조상은 노드 $H, D, A$ 입니다.
- 후손 (descendant)
  - 노드 자신의 모든 자식 노드를 말합니다.
  - 위 그림에서 노드 $D$ 의 후손은 노드 $H, I, J, M$ 입니다.
노드의 수준 (Level)
- 루트 노드의 수준이 0을 기준으로 하여, 대를 거듭할 수록 수준이 높아집니다.
- 위 그림에서 노드 $A$ 의 Level은 0 입니다.
- 위 그림에서 노드 $B, C, D$ 의 Level은 1 입니다.
- 위 그림에서 노드 $E, F, G, H, I, J$ 의 Level은 2 입니다.
- 위 그림에서 노드 $K, L, M$ 의 Level은 3 입니다.
트리의 높이 (height)/ 깊이 (depth)
- 최대 수준(level) + 1
- 위 그림에서 전체 트리의 깊이는 4 입니다.
부분 트리 (Sub-Tree)
- 특정한 노드를 기준(루트 노드)으로 기준 노드와 모든 후손을 아우르는 부분 트리를 만들 수 있습니다.
- 위 그림에서 노드 $B$ 를 루트 노드로 본다면, 노드 $B$ 와 아래로 연결된 트리를 서브 트리라고 할 수 있습니다.
노드의 차수 (Degree)
- 노드의 자식(서브트리)의 수 입니다.
- 위 그림에서 노드 $B$ 는 노드 $E, F$ 와 연결되어 있으므로 차수는 2입니다.
- 단말 노드는 차수가 0입니다.