완전 이진 트리(Complete Binary Tree) 자료구조 이해

본 포스팅에서는 완전 이진 트리(Complete Binary Tree) 자료구조에 대해 알아봅니다.

 

* 완전 이진 트리(Complete Binary Tree) 자료구조란?

완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 합니다. 또한, 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 합니다(그림 1 참고). 그림 1 우측 트리는 노드 12의 자식 노드가 우측에만 삽입되어 있기 때문에 완전 이진트리라고 할 수 없습니다.

 

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

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 건강한 하루 보내시길 바랍니다 :)

고맙습니다.