Heap, 다른 말로 우선 순위 큐 알고리즘을 배우기 전에, 완전이진트리와 포화이진트리에 대해서 짚고 넘어가도록 하겠습니다. 트리에 대해서 이론적으로만 설명하면 재미가 없으니, 나올 때 마다 설명을 하는 게 맞는 듯 싶어요. 이진 트리라고 하면, 자식의 갯수가 최대 2개인 Tree를 의미합니다. 이 둘은, 균형 트리라는 공통점이 있어요. 다른 점은 무엇일까요?

 

 

 이 둘을 영어로는 각각, Complete Binary Tree, Perfect Binary Tree라고 이야기를 합니다. 당연하게도, 포화 이진 트리는 완전 이진 트리이기도 합니다.

 

 


 먼저 포화 이진 트리부터 그려봅시다. 먼저 잎이란, 자식이 없는 노드를 의미해요. 단말 노드라고 많이 이야기를 합니다. 일단 이들의 레벨이 모두 같다? 깊이가 모두 같다는 것입니다. 높이가 0인 PBT를 그려보겠습니다.

 

 

 그러면 이렇게 그려질 겁니다. leaf가 하나입니다. 이제 높이가 1인 PBT를 그려볼 건데요. 그러면, 1번이 내부 노드가 되어야 합니다. 내부 노드는 무조건 2개의 자식 노드를 가져야 합니다.

 

 

 따라서, 이렇게 그려지겠네요. 다음에 높이가 2인 PBT를 그리면 어떻게 될까요? 이미 1은 2개의 child를 가지고 있어요. 2와 3이 2개의 자식을 가져야 합니다. 그러므로, 아래와 같이 그려집니다.

 

 

 그러면 노드 수가 7개이고 높이가 3인 Tree가 그려집니다. 잎의 갯수는 4개입니다. 그러면, 높이가 4인 PBT의 노드 갯수는 몇 개가 될까요? 리프의 갯수가 4개인가요? 이들이 2개씩을 가져야 하니까 8개의 노드가 늘어나면 되겠네요.

 

 

 즉 노란색 부분이 child를 2개씩 가지면 되므로, 높이가 3인 PBT의 노드 갯수는 15개가 됩니다. 높이가 d인, 완전 이진트리의 노드 갯수를 2^(d+1) - 1, 리프 갯수를 2^d이라 해 봅시다. 그러면, d+1인 PBT의 리프 갯수는 2^(d+1)가 됩니다. 높이가 d였던 PBT의 left들이 자식을 각각 2개씩 가졌기 때문입니다. 그러면 전체 노드 갯수는 어떻게 되나요? 2^(d+1) - 1 + 2^(d+1)이 되므로, 이를 잘 계산하면 2^(d+2) - 1이 됩니다.

 

 따라서, 이가 d인 포화 이진 트리의 노드 수는 2^(d+1)-1이 됩니다.

 

 


 완전 이진 트리, Complete Binary Tree는 포화 이진트리에서 오른쪽 리프부터 제거해 나간 트리를 의미합니다.

 

 

 먼저 우측에 있는 leaf인 7을 제거했어요. CBT인가요? 네. 완전 이진 트리입니다. 다음에 가장 우측에 있는 6을 제거해 봅시다.

 

 

 이것 역시 완전 이진 트리라고 할 수 있어요. 다음에 5를 제거하면 어떨까요?

 

 

 역시 Complete 하다고 할 수 있어요. 보시면, 번호가 1, 2, 3, 4 순으로 꽉 채워져 있음을 알 수 있어요. 그리고 세 가지 모두 다 하나의 특징을 더 잡을 수 있는데요. 깊이가 0인 노드의 수는 1, 1인 노드의 수는 2라는 것입니다. 깊이가 2인 것의 수는 1개일 수도 있고, 2개, 3개, 4개일 수도 있지만요.

 

 

 그러면 이 경우에는 어떨까요? 1, 2, 3만 있는 경우. 이 때도 마찬가지입니다. 저는 가장 우측에 있는 leaf를 제거했어요. 7, 6, 5, 4 순으로 remove를 한 것 뿐입니다. 그랬더니 이런 트리가 만들어 진 것 뿐입니다. 따라서, 이것도 Complete Binary라고 할 수 있겠습니다.

 

 


 우리는 이 사실을 하나 발견할 수 있어요.

 

 그러면, 노드의 갯수가 k인 완전 이진 트리의 깊이는 어떻게 될까요? 일단 노드의 수가 2^u꼴이라면, 높이는 밑이 2인 log(k)일 겁니다. 만약에 2^u + t꼴이라고 한다면 (단 t<2^u) 높이는 floor(밑이 2인 log(k))가 될 거에요. 예를 들어 k = 6이라고 해 봅시다. 6을 2^u + t꼴로 나타내면, 2^2 + 2로 나타낼 수 있습니다. floor(밑이 2인 log(6))의 값은 floor(2.xx) 이므로 2가 됩니다.

 

 floor(x)는 x보다 작거나 같습니다. 따라서, Complete Binary Tree의 노드 갯수가 K개라면, Tree의 높이는 밑이 2인 log(K)보다 작거나 같습니다. 이는, Root에서부터, Tree 내에 있는 특정한 아이템을 찾을 때, 최악의 경우라도 O(log)만에 찾을 수 있다는 의미입니다.