완전 이진 트리(Complete binary tree) 란?

완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한

모든 노드는 완전히 채워져 있어야 한다.

또한, 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며,

노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다.(그림1 참고)

그림1 우측 트리는 노드 12의 자식 노드가 우측에만 삽입되어 있기 때문에 완전 이진트리라고 할 수 없다.

img1.daumcdn.png

그림1. 완전 이진 트리 자료구조의 올바른 예시(좌측)와 올바르지 않은 예시(우측)

주요 특징

  1. 노드 채우는 순서

: 노드를 위에서 아래로, 그리고 같은 레벨에서는 왼쪽에서 오른쪽으로 채우는 것처럼 생각하면 이해하기 쉽다.

  1. 배열 표현 용이

: 완전 이진 트리는 노드의 인덱스를 사용하여 배열(Array)에 효율적으로 저장할 수 있다.

예를 들어, 부모 노드의 인덱스가 i일 때 왼쪽 자식 노드는 2i,

오른쪽 자식 노드는 2i+1 인덱스에 저장되는 방식으루 구현할 수 있다.