heap sort(힙 정렬) Full Binary Trees vs Complete Binary Trees

Full Binary Tree vs Complete Binary Tree

 

heap sort를 공부하다 보면 Full binary tree와

Complete binary tree에 대한 용어를 들어본 적이 있을 겁니다.

예를 들어, 이런 형태의 배열이 존재한다고 가정해봅시다.

heap sort를 사용하여 해당 배열을 정렬한다면,

맨 처음 꼭대기에 있는 노드를 제외하고 2개씩 나누어 왼쪽부터 정렬해야 합니다.

마치 이렇게 말이죠.

이런 식으로 배열을 나누고 Tree 형태로 표현하게 되면,

요런 형태의 tree가 나오게 됩니다.

heap sort를 하진 않았지만

이런 방식으로 표현한 다음에 최솟값이나 최댓값 정렬을 하게 됩니다.

위의 tree를 살펴보면 모든 노드들은 자신의 child 노드를 2개씩 가지고 있으며,

비어있거나 대칭이 되지 않는 곳이 없습니다.

이를 "더이상 채울 수 없다"라는 의미에서 Full Binary Tree라고 합니다. 

반면에 노드가 완벽히 채워지지는 않지만

배열을 왼쪽부터 정리하여 데이터를 Tree형태로 만든 경우를 Complete Binary Tree라고 부릅니다.

여기서 중요한 점은 Complete Bianary Tree는 규칙을 가지고

왼쪽부터 배열을 정리하여 표현한 방식을 의미한다는 것이고,

heap sort가 무.조.건 왼쪽부터 정렬하는 게 원칙은 아니라는 것입니다.

왜냐하면 heap sort의 방식이 이거 하나가 아니라

다른 방식의 heap sort도 존재하기 때문입니다.

따라서 왼쪽부터 정렬한다는 기준은 complete Binary Tree일 때만 해당됩니다.

형 뭔 말인지 모르겠어.

그래서 Complete Binary Tree example 그림을 준비했습니다.

이렇게 정렬된 것이 바로 Complete Binary Tree에 해당합니다.