이 튜토리얼에서는 한 번의 순회(single traversal)만으로 이진 트리의 밀도를 구하는 방법을 알아봅니다.
이진 트리의 밀도는 다음과 같은 간단한 공식으로 정의됩니다.
밀도 = 트리의 크기 ÷ 트리의 높이
핵심 개념 정리
- 트리의 크기(Size): 주어진 이진 트리에 존재하는 노드의 총 개수
- 트리의 높이(Height): 루트 노드에서 가장 깊은 리프(leaf) 노드까지의 최대 깊이
일반적으로 크기와 높이를 각각 따로 계산하면 트리를 두 번 순회해야 하지만, 하나의 함수에서 두 값을 동시에 계산하면 단 한 번의 순회로 밀도를 구할 수 있습니다. 시간 복잡도는 O(n)입니다.
문제 해결 단계
- 이진 트리의 더미 데이터를 초기화합니다.
- 트리의 크기와 높이를 동시에 구합니다.
- 재귀 호출을 통해 트리의 높이를 계산합니다.
- 왼쪽 서브트리의 높이가 오른쪽보다 크면 왼쪽 높이에 1을 더해 반환하고, 그렇지 않으면 오른쪽 높이에 1을 더해 반환합니다.
- 노드를 방문할 때마다 크기(size)를 1씩 증가시킵니다.
- 공식 (트리의 크기 / 트리의 높이)을 이용해 밀도를 계산합니다.
- 계산된 밀도를 출력합니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int findHeightAndSizeOfTree(Node* node, int &size) {
if (node == NULL) {
return 0;
}
int leftTreeCount = findHeightAndSizeOfTree(node->left, size);
int rightTreeCount = findHeightAndSizeOfTree(node->right, size);
size++;
return (leftTreeCount > rightTreeCount) ? leftTreeCount + 1 : rightTreeCount + 1;
}
float treeDensity(Node* root) {
if (root == NULL) {
return 0;
}
int treeSize = 0;
int treeHeight = findHeightAndSizeOfTree(root, treeSize);
return (float)treeSize/treeHeight;
}
int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
cout << treeDensity(root) << endl;
return 0;
}코드 설명
findHeightAndSizeOfTree 함수가 핵심입니다. 이 함수는 재귀적으로 트리를 순회하면서 각 노드를 방문할 때마다 참조 변수 size를 1씩 증가시켜 전체 노드 수를 세고, 동시에 왼쪽과 오른쪽 서브트리의 높이 중 더 큰 값에 1을 더해 현재 서브트리의 높이를 반환합니다. 이렇게 하면 별도의 순회 없이 크기와 높이를 한 번에 얻을 수 있습니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
2.33333
예제 트리는 총 7개의 노드(크기)와 높이 3을 가지므로, 밀도는 7 ÷ 3 ≈ 2.33333이 됩니다.
마무리
이번 튜토리얼에서는 단 한 번의 순회로 이진 트리의 크기와 높이를 동시에 계산하여 밀도를 구하는 방법을 배웠습니다. 이 기법은 불필요한 중복 순회를 줄여 효율성을 높일 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.