비선형 자료구조 - 이진 트리(Binary Tree)란 무엇이고 여러 가지 종류를 알아보자

시작하며.

지난 글에서 트리 자료구조는 어떤 것인지 왜 이진 트리가 중요한지 등 정리했었다.
이진 트리는 성격에 따라 여러 가지 종류로 분류되며
오늘은 이진 트리란 무엇이고 종류와 특징에 대해서 알아보고자 한다.

 

이진 트리(Binary Tree).

각 노드는 최대 2개의 자식을 가질 수 있는 트리
자식 노드는 좌우를 구분하여 값을 저장 (왼쪽 자식 : 부모 노드의 왼쪽 / 오른쪽 자식 : 부모 노드의 오른쪽 아래)
이진 트리의 서브 트리는 공백이 될 수도 있고 하나의 서브트리만 가지거나 두 개 모두 가질 수도 있다.

자식 노드는 좌우를 구분하여 값을 저장

 

이진 트리의 종류.

• Perfect binary Tree : 포화 이진 트리
  - 모든 레벨의 노드들이 2개씩 다 채워져 있는 트리
  -  모든 리프 노드가 같은 레벨에 있어야 함

 

• Complete binary tree : 완전 이진 트리
  - 마지막 레벨을 제외하고 모든 노드가 가득 차 있어야 하며, 
     마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
  - 왼쪽이 비어있고 오른쪽만 있다면? 그냥 이진 트리

 

• Full binary tree : 정 이진 트리
  - 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

• Balanced binary tree : 균형 이진 트리
  - 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리
  - 탐색 속도가 균형 이진 트리가 아닌 것 보다는 빠름
• Skewed binary tree : 편향 트리(사향 트리)
  - 한쪽으로 기울어진 트리

 

이진 트리 특징.

포화 이진 트리의 높이가 h라면 노드의 수는 2^(h+1) - 1 개
포화(완전) 이진 트리의 노드가 N개 일 때, 높이는 logN 
이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N - 1개