[DataStructure] 완전 이진 트리

TToII·2021년 2월 21일
0

Datastructure

목록 보기
1/6
post-thumbnail

완전 이진 트리란 ?

포화 이진 트리에서 오른쪽 리프부터 제거해 나간 트리
즉, 부모 노드를 기준으로 왼쪽부터 자식 노드를 채워 넣은 트리
(따라서, 포화 이진 트리도 완전 이진 트리이다)

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다.
마지막 레벨 h 에서 1부터 2h-1 개의 노드를 가질 수 있다.

<완전 이진 트리의 속성>

  • 루트 노드를 레벨 1로 두었을 때 레벨 k의 최대 노드의 수는 2^(k-1)
  • N개의 노드를 가진 완전 이진 트리의 높이는 log2(N+1)
  • 높이가 h라면, 2^h <= 노드의 수 < 2^(h+1)

<리스트에 저장된 완전 이진 트리의 특성>

  • a[i]의 부모는 a[i/2]에 있다 (단, i > 1)
  • a[i]의 왼쪽 자식은 a[2i]에 있다 (단, 2i <= N)
  • a[i]의 오른쪽 자식은 a[2i+1]에 있다 (단, 2i+1 <= N)
profile
Hello World!

0개의 댓글