Computer Science/Data Structure

[자료구조] 이진 트리(Binary Tree): 트리의 분류와 이진 트리의 종류(Full, Complete, Perfect, Balanced, Degenarate Binary Tree)

깃짱 2023. 12. 14. 14:00
반응형
반응형

 

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

 

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

주니어 개발자를 위한 전공 지식 모음.zip. Contribute to seoul-developer/CS development by creating an account on GitHub.

github.com

 

 

 

💋 트리 구조의 분류

트리 자료구조는 주로 노드 간의 관계 및 자식 노드의 개수에 따라 분류됩니다.

(먼저 트리 구조에 대해 이해해야 합니다.)

 

 

✔️ 이진 트리 (Binary Tree):

  • 각 노드가 최대 두 개의 자녀 노드를 가지는 트리
  • 자녀 노드가 2개니깐, left, right로 구분할 수 있습니다.

 

✔️ 삼진 트리 (Ternary Tree):

  • 각 노드가 최대 세 개의 자녀 노드를 가지는 트리
  • 일반적으로 left, mid, right이라는 구분을 사용합니다.

 

✔️ N-트리 / 일반 트리 (N-ary Tree or Generic Tree):

  • 각 노드가 최대 N개의 자식을 가질 수 있는 트리
  • 노드는 레코드 및 자식에 대한 참조 목록으로 구성됩니다.
  • 중복 참조는 허용되지 않습니다.

 

이중에서 이진 트리의 종류에 대해서 자세히 알아보겠습니다.

  • 풀 이진 트리 (Full Binary Tree)
  • 완전 이진 트리 (Complete Binary Tree)
  • 균형 이진 트리 (Balanced Binary Tree)
  • 퇴화 이진 트리 (Degenerate or Pathological Binary Tree)

 

💋 풀 이진 트리 (Full Binary Tree)

  • 모든 노드에 자녀가 0개거나 2개인 트리

A full binary tree is a binary tree with either zero or two child nodes for each node.

 

 

 

💋 완전 이진 트리 (Complete Binary Tree)

  • 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 있고, 마지막 레벨은 왼쪽부터 빠짐없이 노드가 채워진 이진 트리

A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.

 

 

💋 포화 이진 트리 (Perfect Binary Tree)

  • 모든 레벨에서 노드가 빠짐없이 채워져 있는 이진 트리
  • perfect binary tree / non-perfect binary tree

 

 

 

💋 균형 이진 트리 (Balanced Binary Tree)

  • 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1인 이진 트리

 

 

💋 변질 이진 트리 (Degenerate Binary Tree)

이미지 출처: https://iq.opengenus.org/degenerate-or-pathological-tree/

  • 모든 부모 노드는 하나의 자녀 노드만 가지는 이진 트리
  • pathological binary tree라고도 불립니다.
  • 모든 부모 노드가 왼쪽 자녀만 가지면 left skewed binary tree, 오른쪽 자녀만 가지면 right skewed binary tree라고 부릅니다.

 

 

 

💋 참고자료

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!

 

반응형