Khái niệm
Đối với Cây Đỏ-Đen, chiều cao lớn nhất của nút tối đa gấp đôi chiều cao tối thiểu. Đối với Cây Tìm kiếm Nhị phân nhất định, chúng tôi cần xác minh thuộc tính sau.
Đối với mọi nút, chiều dài của đường đi từ nút đến nút dài nhất không quá gấp đôi các nút trên đường đi ngắn nhất từ nút đến nút.
Ví dụ
13 41 \ / \ 15 11 101 \ / \ 17 61 151
Cây trên không thể là Cây đỏ-đen Cây trên có thể là Cây đỏ-đen với bất kỳ màu sắc nào
Chiều cao tối đa của 13 là 1
Chiều cao tối thiểu của 13 là 3
11 / \ 6 101 / \ 51 151 / 41
Cây trên cũng có thể là cây Đỏ-đen
Trong trường hợp này, độ phức tạp về thời gian dự kiến là O (n). Cây nên được thăm nhiều nhất một lần trong dung dịch.
Phương pháp
Đối với mọi nút, chúng tôi yêu cầu lấy độ cao lớn nhất và nhỏ nhất và so sánh chúng. Khái niệm là ghé thăm cây và đối với mỗi nút xác minh xem nó có cân bằng hay không. Việc cần làm của chúng ta là viết một hàm đệ quy trả về 3 thứ, một giá trị boolean để cho biết cây có cân đối hay không, chiều cao nhỏ nhất và chiều cao lớn nhất. Để trả về nhiều giá trị, chúng tôi có thể áp dụng cấu trúc hoặc chuyển các biến bằng tham chiếu. Việc phân bổ tham chiếu maxh và minhby được thực hiện để các giá trị có thể được áp dụng trong các lệnh gọi mẹ.
Ví dụ
/* 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;
} Đầu ra
Balanced