[자료구조] 트리, 이진트리, 힙 - 1

트리

• 비선형 구조 (원소들 간에 1:n 관계를 가지는 것)
  • 선형구조는 원소들 간에 1:1의 관계를 가지는 것임. 대표적으로 linkedList, arrayList가 있음
• 원소들 간에 계층관계를 가짐
• 상위원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조

 

[트리의 용어]

• 노드: 트리의 원소
  • 트리의 원소: A,B,C,D,E,F,G,H,I,J,K,L
• 간선: 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결
• 루트 노드: 트리의 시작 노드
  • 루트노드: A
• 형제노드: 같은 부모노드를 가진 노드들
  • 형제 노드: B,C,D
• 조상노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
  • J의 조상 노드들: F,B,A
• 서브트리: 부모노드와 연결된 간선을 끊었을 때 생성되는 트리
  
  • A의 서브 트리: B트리, C트리, D 트리
• 자손 노드: 서브 트리에 있는 하위 레벨의 노드들
  
  • B의 자손 노드: E,F,J,K

• 차수(degree)
  • 노드의 차수: 노드에 연결된 자식 노드의 수(B의 차수= 2, F의 차수=1)
  • 트리의 차수: 트리에 있는 노드의 차수 중 가장 큰 값(트리 A의 차수=3)
  • 단말 노드(리프노드): 차수가 0인 노드, 자식 노드가 없는 노드
• 높이(레벨)
  • 노드의 높이: 루트노드에서 노드에 이르는 간선의 수. 노드의 레벨(B의 높이=1, J의 높이=3)
  • 트리의 높이: 트리에 있는 노드의 높이 중 가장 큰 값. 최대 레벨(트리 A의 높이=3)

 

---

이진트리

이진트리는 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리를 말한다.

각 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리이다.

• 왼쪽 자식 노드(left child node)
• 오른쪽 자식 노드(right child node)

[이진트리의 특징]

• 이진트리의 최대 노드 수는 레벨 i에서 \(2^i\)개를 가짐
• 높이가 h인 이진 트리가 가지는 최소 노드 개수는 \(h+1\)이고 최대 개수는 \(2^{h+1}-1\)이다.

 

[이진트리의 종류]

이진트리는 포화 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 편향 이진 트리(Skewed Binary Tree)가 있다.

 

1. 포화 이진 트리(Full Binary Tree)

• 모든 레벨에서 노드가 2개씩 있는 이진 트리
• 높이가 h일때 \(2^{h+1}-1\)개 노드가 있음
• 위에 그래프에서 높이=3, 노드 개수=\(2^4-1 = 15\) 

2. 완전 이진 트리(Complete Binary Tree)

• 마지막 레벨의 노드 빼고 나머지 노드들은 전부 빈자리가 없는 이진 트리
• 높이가 h일 때 노드의 개수 = \( 2^h \le n \le 2^{h+1}-1 \)
• 예를 들어 레벨이 3인 그래프에서 가질 수 있는 노드 개수: \(2^3  \le n \le 2^4-1\)

3. 편향 이진 트리(Skewed Binary Tree)

• 높이 h에 대해 한쪽 노드 방향에만 자식 노드를 가지는 이진 트리
• 높이 h일 때 노드 개수는 h+1을 가짐
  • 왼쪽 편향 이진 트리
  • 오른쪽 편향 이진 트리