이진트리란?
지난 글에서는 차수가 N인 트리의 대하여 설명했습니다. 이 글을 포함해서 앞으로 몇 개의 글에서는 트리 중에서도 차수가 2 인 이진트리만을 다루겠습니다.
이진 트리는 차수가 2 인 트리입니다. 영어로는 Binary Tree입니다.
이렇게 생긴 트리입니다.
별로 쓸 데 없어 보일 수도 있지만, 나중에 설명할 이진 탐색 트리, 이진 힙 같은 여러 곳에 많이 사용되는 자료구조입니다.
앞에서 말했듯이, 이진트리는 차수가 2 인 트리입니다. 다시 말해 각각의 노드는 자식이 없거나(잎 노드), 있다고 해도 하나 혹은 두 개 입니다.
포화/완전 이진 트리
위 사진과 같은 트리는 잎 노드들이 모두 같은 깊이에 있습니다. 다시 말해 잎노드를 제외한 모든 노드들의 차수가 2 입니다. 이런 이진트리를 포화 이진 트리(Full Binary Tree)라고 부릅니다.
이렇게 포화 이진 트리는 아니지만 잎 노드들이 왼쪽부터 하나 씩 차곡차곡 채워진 트리를 완전 이진 트리(Complete Binary Tree)라고 부릅니다.
이렇게 다른 이진 트리들과 완전/포화 이진 트리를 구분시키는 이유가 있습니다.
다른 이진 트리들에 비해서 완전/포화 이진 트리가 깊이가 더 낮기 때문에 나중에 다룰 이진 트리를 이용한 알고리즘의 실행 시간을 더욱 줄일 수 있습니다.
그래서 가능한 한 완전/포화 이진 트리에 근접한 형태를 유지하는 것이 바람직합니다.
다음 글에서는 이진 트리를 직접 코드로 구현할 것 입니다.