트리와 이진트리란?

[bugoverdose]

트리

• 정점과 간선으로 구성된 계층적 데이터의 집합
• 트리는 그래프의 일종. 숲은 트리로 이루어진 집합.

트리의 성질

1. 루트 노드는 하나만 존재
2. 사이클이 존재하지 않음.
3. 자녀 노드에 하나의 부모 노드만 존재
4. 데이터를 순차적으로 저장하지 않는 비선형 구조(nonlinear). (not 리스트)
5. 트리에 서브트리가 존재하는 재귀적 구조
6. 계층적 구조 : 부모-자식의 계층 구조를 지님. 특정 노드는 인접한 다른 노드의 부모 혹은 자식

결과적으로 V - 1 = E라는 공식이 성립함.

• 간선의 개수는 노드의 개수-1
• 임의의 두 노드(정점) 사이의 경로(간선)는 유일무이하게 존재. 트리 내의 모든 노드는 단 한가지 경로를 통해 서로에게 도달 가능.

트리의 구성

루트 노드 - 브랜치 노드(내부 노드) - 리프 노드(외부 노드/단말 노드)

• 루트 노드: 최상위 노드. 트리의 시작점.
• 브랜치/내부 노드: 루트 노드와 리프 노드 사이에 존재하는 모든 노드. 자녀 노드를 지니는 노드.
• 리프 노드: 자식 노드가 없는 노드. 외부 노드. 단말 노드 등

노드의 세부 종류

• 부모 노드(parent): 자녀 노드를 지니는 노드.

• 자녀 노드(child): 모든 노드는 0개 이상의 자녀 노드를 지님.

• 형제 노드(sibling): 같은 부모를 공유하는 노드들. (단순히 같은 레벨은 아님)

• 조상 노드(ancestor): 부모 노드를 따라 루트 노드까지 올라가며 만날 수 있는 모든 노드들.

• 자손 노드(descendant): 모든 자녀 노드들을 따라 내려가며 만날 수 있는 모든 노드들. (한줄로 내려가는게 아니라 서브트리를 구성)

주요 용어

• 노드의 높이: 해당 노드로부터 가장 먼 리프 노드까지의 거리(간선의 개수).

  • 리프 노드의 높이는 언제나 0
  • 트리의 높이(height): 루트 노드의 높이. 루트 노드로부터 가장 먼 리프 노드까지의 거리(간선의 개수).

• 노드의 깊이(depth): 해당 노드로부터 루트 노드까지 도달하는 데 걸리는 간선의 개수(최단 거리).

  • 루트 노드의 깊이는 언제나 0
  • 트리의 깊이는 루트 노드로부터 가장 멀리 떨어진 노드의 깊이.
  • 트리의 높이 == 트리의 깊이

• 노드의 차수(degree): 노드의 자녀 노드 개수.

  • 트리의 차수: 노드들의 차수 중 가장 큰 차수. 차수의 최대값.
  • 이진 트리의 차수는 2

• 서브트리: 트리 내의 부분 집합. 그 자체로 새로운 트리를 구성. 특정 노드의 자녀노드들은 전부 각자 재귀적으로 서브트리를 구성함

• 경로(path): 한 노드에서 다른 노드에 도달할 때까지의 노드들의 시퀀스

  • 경로 길이(length of path): 경로에 있는 노드들의 개수. 출발 노드와 도착 노드 포함.

• 두 노드 사이의 거리(distance): 두 노드 사이의 최단 경로의 간선 수

• 레벨: 깊이와 동의어. 해당 노드와 루트 노드 사이의 경로에서 간선의 개수

  • 루트 노드의 레벨은 0. (1인 문서도 존재)
  • 내부 노드는 깊이에 따라 1레벨, 2레벨 ...

• width: 같은 레벨에 속한 노드의 개수

• 트리의 크기(size): 트리를 구성하는 모든 노드의 개수

  • 노드의 크기(size): 자신을 포함한 자손 노드의 개수

---

이진트리(binary tree)

자녀 노드 개수가 최대 2개인 트리. 차수가 2 이하.

• left child : 왼쪽 자녀 노드
• right child : 오른쪽 자녀 노드

형태에 따른 이진트리의 종류

1. full + complete = perfect

   • 정이진 트리(full): 모든 자식 노드가 없거나, 2개인 이진트리. 모든 노드의 차수가 0 혹은 2.

   • 완전 이진 트리(complete): 왼쪽에서부터 차곡차곡 채워져 있는 이진트리.

   • 마지막 레벨을 제외하고 모든 레벨에서 노드가 완전히 채워짐.

   • 마지막 레벨도 왼쪽부터 빠짐없이 채워짐. (complete해가는 과정)

   • heap 자료구조가 내부적으로 완전 이진 트리로 구현됨.

   • 포화 이진 트리(perfect): 모든 레벨에서 노드가 빠짐없이 채워져 있는 이진 트리

   • 정이진 트리 + 완전 이진 트리.

2. 변질 이진 트리(degenerate 혹은 pathological)

   • 모든 부모 노드에서 자식 노드가 1개만 존재하는 이진 트리. 차수가 1.
   • left skewed binary tree: 모든 부모 노드에서 left child 노드만 지니는 경우
   • right skewed binary tree: 모든 부모 노드에서 right child 노드만 지니는 경우

3. 균형 이진 트리(balanced)

   • 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1인 이진 트리.
   • map, set 내부의 레드 블랙 트리는 균형 이진 트리의 일종

[tonic523]

• 이진 트리 형태가 무엇이 있나요?
  • 정 이진 트리, complete 이진 트리, perfact 이진 트리…