Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 완전 이진 트리 노드 개수 효율적으로 계산하기

완전 이진 트리(Complete Binary Tree)가 주어졌을 때, 전체 노드의 개수를 세는 문제입니다. 예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.

C++로 완전 이진 트리 노드 개수 효율적으로 계산하기

이 경우 출력 결과는 6이 됩니다.

문제 해결 접근 방식

완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨의 노드들은 왼쪽부터 채워지는 특성이 있습니다. 이 특성을 활용하면 단순히 모든 노드를 순회하는 것보다 훨씬 효율적으로 노드 개수를 구할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 트리의 왼쪽 끝까지의 높이와 오른쪽 끝까지의 높이를 각각 계산했을 때 두 값이 같다면, 해당 서브트리는 포화 이진 트리(Full Binary Tree)입니다. 포화 이진 트리의 노드 개수는 2h − 1 공식으로 즉시 구할 수 있으므로, 더 이상 재귀 호출을 하지 않아도 됩니다.

알고리즘 단계

  • 재귀 방식으로 해결하며, countNodes() 함수는 루트 노드를 인자로 받습니다.
  • 높이 변수 hl(왼쪽 높이)과 hr(오른쪽 높이)을 0으로 초기화합니다.
  • 루트를 가리키는 두 개의 임시 노드 l과 r을 생성합니다.
  • l이 NULL이 아닌 동안 hl을 1씩 증가시키고, l을 l의 왼쪽 자식으로 이동합니다.
  • r이 NULL이 아닌 동안 r을 r의 오른쪽 자식으로 이동시키고, hr을 1씩 증가시킵니다.
  • hl과 hr이 같다면 (2 ^ hl) − 1을 반환합니다. 해당 서브트리가 포화 상태라는 의미입니다.
  • 그렇지 않다면 1 + countNodes(루트의 왼쪽 자식) + countNodes(루트의 오른쪽 자식)을 반환합니다.

이 알고리즘은 매 재귀 단계마다 트리의 한쪽 부분이 포화 트리인지 확인하여 계산 범위를 크게 줄이기 때문에, 시간 복잡도가 O((log n)2)로 일반적인 전체 순회(O(n))보다 빠릅니다.

C++ 구현 예제

아래 구현 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
         temp->right = new TreeNode(val);
      else
         temp->right = new TreeNode(0);
         return;
      } else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   int fastPow(int base, int power){
      int res = 1;
      while(power > 0){
         if(power & 1) res *= base;
         base *= base;
         power >>= 1;
      }
      return res;
   }
   int countNodes(TreeNode* root) {
      int hr = 0;
      int hl = 0;
      TreeNode* l = root;
      TreeNode* r = root;
      while(l){
         hl++;
         l = l->left;
      }
      while(r){
         r = r->right;
         hr++;
      }
      if(hl == hr) return fastPow(2, hl) - 1;
      return 1 + countNodes(root->left) + countNodes(root->right);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9,10};
   TreeNode *node = make_tree(v);
   cout << (ob.countNodes(node));
}

참고로 fastPow() 함수는 거듭제곱을 분할 정복(비트 시프트) 방식으로 빠르게 계산하는 함수로, pow() 함수를 사용하는 것보다 효율적입니다.

입력

[1,2,3,4,5,6,7,8,9,10]

출력

10

입력 배열로 구성된 트리에는 총 10개의 노드가 있으며, 프로그램은 이를 정확히 계산하여 10을 출력합니다.