자료구조 이진 트리(Binary Tree)의 종류

Binary Tree 이진 트리

 

이진 트리(Binary Tree) 란 무엇인가?

• 각각의 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다.
• 정렬과 검색 알고리즘을 위한 하나의 도구
  • 이진 트리의 모양에 따라 알고리즘의 성능에 차이가 있다.
  • 트리의 형태는 레벨과 노드 수에 따라서 결정된다.

 

이진 트리(Binary Tree) 의 종류

1. Perfect binary tree 포화 이진 트리

1. 포화 이진 트리는 모든 레벨의 노드가 가득 차있는 트리이다.
   • 노드가 2개의 자식을 가지고 있다.
   • 차수(Degree) 가 2 이다.
2. 모든 노드가 가득 차있어 단말 노드부터 루트노드까지의 높이가 같다.
3. 노드의 개수 n = 2^h - 1, h 는 높이

A는 B 와 C를 자식으로 가져 꽉 차있고, B는 D 와 E, C는 F 와 G를 자식으로 가져 꽉 차있어 모든 레벨이 가득 차 있다고 할 수 있다. 따라서 포화 이진 트리가 되는것을 알 수 있다.

 

2. Complete binary tree 완전 이진 트리

1. 완전 이진 트리는 마지막 레벨 바로 전까지는 꽉 차있다 마지막 레벨에서 왼쪽부터 차례대로 채워져 있는 트리이다.
2. 완전 이진 트리의 개념은 힙(heap)과 관련이 있다.
3. 노드의 개수 n < 2^h -1, h 는 높이

왼쪽의 트리는 왼쪽부터 노드가 채워져있기 때문에 완전 이진트리라고 할 수 있지만 오른쪽의 트리는 레벨 3에서 왼쪽부터 노드가 채워져있지 않기 때문에 완전 이진 트리라고 할 수 없다.

 

3. Skewed binary tree 편향 이진 트리

1. 왼쪽 또는 오른쪽으로 편향되게 채워져있는 트리이다.
2. 각각의 높이에서 1개의 노드만 있다.
   • 따라서 왼쪽 혹은 오른쪽으로만 편향되게 된다.
3. h <= 노드의 개수 n <= 2^h - 1, h 는 높이
   1. 편향 이진 트리에서 노드의 개수 n은 위 식의 최솟값 h와 같다.
   2. 최댓값은 포화 이진 트리와 같다.

왼쪽의 트리에서 A는 왼쪽 자식으로 B를 가지고, B는 왼쪽 자식으로 D를 가지고 있어 왼쪽 편향 트리이다.

오른쪽의 트리에서 A는 오른쪽 자식으로 B를 가지고, B는 오른쪽 자식으로 D를 가지고 있어 오른쪽 편향 트리이다.

 

4. Full binary tree 정 이진 트리

1. 정 이진 트리는 모든 노드가 0 개 또는 2개의 자식 노드만을 갖는 트리이다.
2. 2 * height + 1 <= 노드의 개수 n <= 2^(height+1) - 1

 

A는 B 와 C로 2개의 자식 노드, B는 D와 E로 2개의 자식 노드, C는 0개의 자식 노드를 가지고 있기 때문에 정 이진 트리가 된다.

 

5. Balanced binary tree 균형 이진 트리

1. 균형 이진 트리는 모든 노드의 왼쪽과 오른쪽 서브 트리의 높이가 1 이상 차이가 나지 않는 트리이다.

왼쪽의 트리들은 왼쪽과 오른쪽의 서브 트리의 높이가 1 이상 차이가 나지 않는것을 볼 수 있다.

하지만 오른쪽의 트리들은 왼쪽과 오른쪽의 서브 트리의 높이가 1이상 차이가 나기 때문에 균형 이진 트리라고 할 수 없다.