완전이진트리(Complete Binary Tree)란?

필요한 사전지식

- 이진트리란?

본론

이진트리의 한 종류인 완전 이진트리는 그림으로 보면 쉽게 이해됩니다.

위의 그림은 완전이진트리(Complete Binary Tree)인 트리들이고, 밑의 그림은 아닌 트리들입니다. 차이가 느껴지시나요?

완전 이진트리들은 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리입니다. 완전이진트리가 아닌 트리들을 보시면 왼쪽이 비어있는데 오른쪽부터 들어가 있죠? 이런 트리들은 완전 이진트리가 아닙니다.