개념
레드-블랙 트리(Red-Black Tree)에서 특정 노드의 최대 높이는 최소 높이의 최대 2배를 넘지 않습니다. 따라서 주어진 이진 탐색 트리(Binary Search Tree)가 이 성질을 만족하는지 검증해야 합니다.
즉, 모든 노드에 대해 리프 노드에서 해당 노드까지의 가장 긴 경로의 길이가, 노드에서 리프까지의 가장 짧은 경로에 포함된 노드 수의 2배를 초과하지 않아야 합니다.
예시
13 41 \ / \ 15 11 101 \ / \ 17 61 151
위 트리는 노드 13의 최대 높이가 1, 최소 높이가 3이므로 높이 균형 조건(최대 높이 ≤ 최소 높이 × 2)을 만족하지 않습니다. 따라서 어떤 색상 배정으로도 레드-블랙 트리가 될 수 없습니다.
반면 아래 트리는 레드-블랙 트리가 될 수 있는 경우입니다.
11
/ \
6 101
/ \
51 151
/
41위 트리는 적절한 색상 배정을 통해 레드-블랙 트리로 표현할 수 있습니다.
이 문제의 기대 시간 복잡도는 O(n)이며, 해결 과정에서 트리 전체를 최대 한 번만 방문해야 합니다.
접근 방법
모든 노드에 대해 가장 큰 높이(maxh)와 가장 작은 높이(minh)를 구한 뒤 두 값을 비교합니다. 기본 아이디어는 트리를 순회하면서 각 노드마다 균형 여부를 확인하는 것입니다.
이를 위해 다음 세 가지 정보를 반환하는 재귀 함수를 작성합니다.
- 트리가 균형인지 아닌지를 나타내는 불리언(Boolean) 값
- 최소 높이(minh)
- 최대 높이(maxh)
여러 값을 반환하기 위해 구조체(structure)를 사용하거나 변수를 참조(reference)로 전달할 수 있습니다. 여기서는 maxh와 minh를 참조로 전달하여 부모 호출(parent call)에서도 해당 값들을 활용할 수 있도록 합니다.
구현 예제
/* 주어진 이진 트리가 레드-블랙 트리처럼 균형을 이루는지 확인하는 프로그램 */
#include <bits/stdc++.h>
using namespace std;
struct Node1{
int key;
Node1 *left, *right;
};
Node1* newNode(int key){
Node1* node1 = new Node1;
node1->key = key;
node1->left = node1->right = NULL;
return (node1);
}
bool isBalancedUtil(Node1 *root, int &maxh1, int &minh1){
if (root == NULL){
maxh1 = minh1 = 0;
return true;
}
int lmxh1, lmnh1;
int rmxh1, rmnh1;
if (isBalancedUtil(root->left, lmxh1, lmnh1) == false)
return false;
if (isBalancedUtil(root->right, rmxh1, rmnh1) == false)
return false;
maxh1 = max(lmxh1, rmxh1) + 1;
minh1 = min(lmnh1, rmnh1) + 1;
if (maxh1 <= 2*minh1)
return true;
return false;
}
bool isBalanced(Node1 *root){
int maxh1, minh1;
return isBalancedUtil(root, maxh1, minh1);
}
/* 위 함수들을 테스트하기 위한 드라이버 코드 */
int main(){
Node1 * root = newNode(11);
root->left = newNode(6);
root->right = newNode(101);
root->right->left = newNode(51);
root->right->right = newNode(151);
root->right->left->left = newNode(41);
isBalanced(root)? cout << "Balanced" : cout << "Not Balanced";;
return 0;
}코드 설명
- isBalancedUtil 함수: 재귀적으로 왼쪽과 오른쪽 서브트리를 순회하며 각각의 최대/최소 높이를 계산하고, 현재 노드에서 최대 높이가 최소 높이의 2배 이하인지 확인합니다.
- 참조 전달: maxh1과 minh1을 참조로 전달해 자식 노드에서 계산된 높이 값을 부모 호출에서 그대로 사용할 수 있습니다.
- 단일 순회: 각 노드를 한 번씩만 방문하므로 전체 시간 복잡도는 O(n)입니다.
출력 결과
Balanced