[자료 구조] - 트리 자료 구조 (3)-이진 트리와 종류(완전, 포화, 완벽, 균형) :: Binary Tree (Full, Complete, Perfect, Balanced)

이진 트리는 우리가 앞으로 마주하게될 트리(Red-Black Tree, AVL Tree, Segment Tree)들중 가장 쉽고 자주 쓰이는 트리이다.

이진 트리 Binary Tree

이진 트리는 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리이다.

 

이 때 중요한 점이 왼쪽 자식과 오른쪽 자식을 하나씩만 가져야 이진 트리가 된다.

 

이러한 이진 트리는 왼쪽 자식과 오른쪽 자식을 구분한다는 특징이 있는데, 우리가 트리의 개념과 용어 에서 배웠듯이 오른쪽 자식은 오른쪽 서브트리를 갖고 왼쪽은 왼쪽 서브트리를 가질 수 있다.

출처 : https://coderkoo.tistory.com/9

이제 이진 트리에 대해서 알았으니 그 종류에 대해 알아보자.

이진 트리의 종류

출처 : https://towardsdatascience.com/

이진 트리의 종류는 크게 5가지가 있다. 한글로 번역하는 과정에서 여러 참고 서적들이 잘 못 번역하여 잘 못 알게되는 경우가 있어서 필자는 영어로 설명하겠다.

• Full
• Complete
• Degenerate
• Perfect
• Balanced

Full Binary Tree

Full Bianry Tree는 모든 노드의 자식이 0이거나 1인 이진 트리이다.

Complete Binary Tree

Complete Binary Tree는 마지막 노드를 제외하고 모든 노드의 자식이 0이며 마지막 레벨의 노드는 왼쪽에 채워져 있는 형태이다.

Degenerate Binary Tree

Degenerate Binary Tree는 모든 부모 노드가 왼쪽으로 자식을 갖는 경우이다.

Perfect Binary Tree

Perfect Bianry Tree는 모든 노드의 자식이 0이거나 채워져 있는 형태로 루트 노드를 기준이로 좌 우가 균형이 되어야 한다.

Balanced Binary Tree

Balanced Binary Tree는 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이가 최대 1만큼 차이가 날 수 있는 이진 트리다.