개념
Red-Black Tree와 관련하여 노드의 최대 높이는 최소 높이의 최대 2배입니다. 주어진 Binary Search Tree에 대해 다음 속성을 확인해야 합니다.
모든 노드와 관련하여 가장 긴 리프에서 노드까지의 경로 길이는 노드에서 리프까지의 최단 경로에서 노드의 두 배 이하입니다.
예
13 41 \ / \ 15 11 101 \ / \ 17 61 151
위의 나무는 적-검정 나무가 될 수 없습니다. 위의 나무는 색상 할당이 있는 적-검정 나무가 될 수 있습니다.
13의 최대 높이는 1입니다.
13의 최소 높이는 3입니다.
11 / \ 6 101 / \ 51 151 / 41
위의 나무는 Red-Black Tree도 될 수 있습니다.
이 경우 예상 시간 복잡도는 O(n)입니다. 트리는 솔루션에서 최대 한 번 방문해야 합니다.
방법
모든 노드에 대해 가장 큰 높이와 가장 작은 높이를 가져와 비교해야 합니다. 개념은 트리를 방문하고 모든 노드에 대해 균형이 맞는지 확인하는 것입니다. 우리가 필요로 하는 것은 세 가지, 즉 나무가 균형을 이루고 있는지 여부를 나타내는 부울 값, 가장 작은 높이와 가장 큰 높이를 반환하는 재귀 함수를 작성하는 것입니다. 여러 값을 반환하려면 구조체를 적용하거나 참조로 변수를 전달할 수 있습니다. maxh 및 minhby 참조를 전달하면 값이 상위 호출에 적용될 수 있습니다.
예시
/* This program to check whether a given Binary Tree is balanced like a Red-Black Tree or not */
#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);
}
/* Driver program to test above functions*/
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;
} 출력
Balanced