자료구조: 트리(Tree)

트리 Tree

• 정점node과 간선edge를 이용하여 데이터의 배치 형태를 추상화한 자료구조
• 1:n 관계의 비선형 자료구조
• 계층 관계로 만들어진 계층형 자료구조

root node

• 트리에서 최상위 노드

leaf node

• 자식 노드가 없는 노드

internal node

• leaf node가 아닌 노드

parent node

• 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드라고 함 ^참조

child node

• B를 A의 자식 노드라고 함 ^참조

sibling

• 동일한 부모를 갖는 형제 노드

ancestor

• 부모의 부모(...의 부모의) 노드

descendant

• 자식의 자식(...의 자식의) 노드

---

노드의 수준 Level

• root node는 level 0
• root node로 부터 해당 노드까지 거치는 간선의 갯수

트리의 높이 Height (=깊이 Depth)

• 최대 수준(Level) + 1

---

부분 트리 sub tree

노드의 차수 Degree

• 자식(sub tree)의 수
• 자식과 연결된 간선의 수
• leaf node의 Degree 는 0
• root node를 제외한 모든 노드는 단 하나의 부모 node를 가짐

---

이진 트리 Binary tree

• 모든 노드의 차수 Degree가 2 이하인 트리
• 재귀적으로 정의할 수 있음
  • 빈 트리(Empty tree)이거나
  • root node + left sub tree + right sub tree
    • 이 때 왼쪽, 오른쪽 서브트리도 이진트리

포화 이진 트리 Full Binary tree

• 모든 레벨에서 노드들이 모두 채워져있는 이진 트리
• 높이가 K이고 노드의 개수가 2^K - 1인 이진트리

완전 이진 트리 Complete Binary tree

• 높이 K인 완전 이진 트리
• 레벨 K-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
• 레벨 K-1 에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리