아침 CS - (3) 이진 트리

이진트리의 개념과 구조

사실 트리에는 이진 트리만 있는 것이 아니다.

삼진 트리도 있고 십육진 트리도 있을 것이다. 그러나 우리가 가장 잘 알아야 하는 이진트리에 대해 가장 먼저 살펴보기로 하고 다른 구조를 갖는 트리들은 어디에 쓰이는지 나중에 또…. 공부할 기회가 뭐 있겠죠.

우선 트리에서 사용하는 용어들을 잠깐 살펴봅시다.

---

기본 용어와 개념들

노드

• 우리가 트리에서 가장 쉽게 보는 그 동글뱅이.

• 노드에도 몇 가지 종류가 있음.

• 계층에 따른 노드 구분

  • 부모 노드 : 자식을 1개 이상 갖고 있는, 즉, 하위레벨에 노드가 한 개라도 있는 모든 노드
  • 자식 노드 : 상위 노드를 갖고 있는, 즉 부모 노드가 아닌 노드

• 특성에 따른 노드 구분

  • 루트 노드 : 트리의 최상단에 위치하는 노드. 각 트리별로 하나 뿐이다.
  • 단말 노드 : 마지막 노드. 최하위 노드. 자식이 없는 노드이다.
  • 내부 노드 : 단말 노드를 제외한 모든 노드.
  • 형제 : 같은 부모를 갖고 있는 두 개의 노드.

• 노드의 ~

  • 크기 : 자신을 포함한 자손들의 총 갯수.
  • 깊이 : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 링크의 수
  • 차수 : 노드가 가진 가지의 수

링크

• 노드를 이어주는 선
• n개의 노드를 갖는 트리에서, 링크의 갯수는 n-1개임

레벨

• 같은 깊이에 있는 노드들의 총 집합
• 최상단이 레벨 1부터 시작, 아래로 내려갈때마다 1씩 커짐

---

이진 트리의 종류

• 포화 이진 트리 : 모든 레벨에서 노드들이 꽉 채워진 상태.

  • 높이가 h인 포화 이진 트리는 2^h - 1 개의 노드를 가짐.

• 완전 이진 트리 : 마지막 레벨을 제외하고 모든 노드가 채워짐, 마지막 레벨도 다 채워져도 무방.

• 편향 트리 : 보시다시피….

  • 트리 최악의 경우가 발생 : 최악의 경우 노드가 N개인 이진 트리의 높이는 O(N)이 될 수도 있음.
  • 포화 트리, 혹은 완전 트리의 경우 : O(logN)

참고 문헌

[Algorithm] 트리의 개념과 용어정리