C++로 주어진 이진 트리가 힙(Heap)인지 확인하는 방법

개념

주어진 이진 트리가 힙(heap) 속성을 만족하는지 검증해야 하는 경우가 있습니다. 이진 트리가 힙이 되기 위해서는 다음 두 가지 조건을 모두 충족해야 합니다.

• 이진 트리는 완전 이진 트리(complete tree)여야 합니다. 즉, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 합니다.

• 최대 힙(max-heap)을 기준으로 할 때, 트리의 모든 노드 값은 자식 노드의 값보다 크거나 같아야 합니다.

예시

다음 트리는 힙 속성을 만족하는 예입니다.

반면 아래 트리는 힙 속성을 만족하지 않습니다.

접근 방법

위 두 조건은 각각 독립적으로 검증해야 합니다.

• 완전 이진 트리 여부 검사: isCompleteUtil 함수를 사용하여 트리가 완전한 형태인지 확인합니다.

• 힙 속성 검사: isHeapUtil 함수를 사용하여 각 노드가 자식보다 크거나 같은 값을 가지는지 확인합니다.

isHeapUtil 함수를 작성할 때는 다음 사항들을 고려해야 합니다.

• 모든 노드는 자식을 2개 가지거나, 자식이 없는(마지막 레벨 노드) 경우, 또는 자식이 1개뿐인 경우 중 하나입니다. 단, 자식이 하나뿐인 노드는 최대 한 개만 존재할 수 있습니다.

• 노드에 자식이 없다면 리프(leaf) 노드이므로 true를 반환합니다. (기저 사례, base case)

• 노드에 자식이 하나뿐이라면, 그 자식은 반드시 왼쪽 자식입니다(완전 이진 트리이기 때문). 따라서 해당 노드와 유일한 자식만 비교하면 됩니다.

• 노드에 자식이 둘 다 있다면, 해당 노드에서 힙 속성을 검증한 후 양쪽 서브트리에 대해 재귀적으로 검사를 수행합니다.

구현 예제

/* 이진 트리가 최대 힙인지 검사하는 C++ 프로그램 */
#include <bits/stdc++.h>
using namespace std;
struct Node1{
    int key;
    struct Node1 *left;
    struct Node1 *right;
};
struct Node1 *newNode(int k){
    struct Node1 *node1 = new Node1;
    node1->key = k;
    node1->right = node1->left = NULL;
    return node1;
}
unsigned int countNodes(struct Node1* root1){
    if (root1 == NULL)
        return (0);
    return (1 + countNodes(root1->left) + countNodes(root1->right));
}
bool isCompleteUtil (struct Node1* root1, unsigned int index1, unsigned int number_nodes){
    if (root1 == NULL)
        return (true);
    if (index1 >= number_nodes)
        return (false);
    // 왼쪽과 오른쪽 서브트리에 대해 재귀 호출
    return (isCompleteUtil(root1->left, 2*index1 + 1, number_nodes) && isCompleteUtil(root1->right, 2*index1 + 2, number_nodes));
}
bool isHeapUtil(struct Node1* root1){
    if (root1->left == NULL && root1->right == NULL)
        return (true);
    if (root1->right == NULL){
        return (root1->key >= root1->left->key);
    }
    else{
        if (root1->key >= root1->left->key &&
            root1->key >= root1->right->key)
        return ((isHeapUtil(root1->left)) &&
        (isHeapUtil(root1->right)));
        else
            return (false);
    }
}
bool isHeap(struct Node1* root1){
    unsigned int node_count = countNodes(root1);
    unsigned int index1 = 0;
    if (isCompleteUtil(root1, index1, node_count) &&
        isHeapUtil(root1))
    return true;
    return false;
}
// 드라이버 코드
int main(){
    struct Node1* root1 = NULL;
    root1 = newNode(10);
    root1->left = newNode(9);
    root1->right = newNode(8);
    root1->left->left = newNode(7);
    root1->left->right = newNode(6);
    root1->right->left = newNode(5);
    root1->right->right = newNode(4);
    root1->left->left->left = newNode(3);
    root1->left->left->right = newNode(2);
    root1->left->right->left = newNode(1);
    if (isHeap(root1))
        cout << "주어진 이진 트리는 힙입니다\n";
    else
        cout << "주어진 이진 트리는 힙이 아닙니다\n";
    return 0;
}

출력 결과

주어진 이진 트리는 힙입니다