数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 检查给定的二叉树是否像红黑树一样高度平衡
概念
关于红黑树，节点的最大高度最多是最小高度的两倍。对于给定的二叉搜索树，我们需要验证以下属性。
关于每个节点，从叶子到节点的最长路径的长度不超过从节点到叶子的最短路径上的节点的两倍。
示例
13 41 \ / \ 15 11 101 \ / \ 17 61 151
上图的树不能是红黑树 上图的树可以是红黑树，并且可以进行任何颜色分配
节点 13 的最大高度为 1
节点 13 的最小高度为 3
11 / \ 6 101 / \ 51 151 / 41
上图的树也可以是红黑树
在这种情况下，预期的时效复杂度为 O(n)。在解决方案中，树最多被访问一次。
方法
关于每个节点，我们需要获取最大和最小高度并进行比较。这个概念是遍历树，并为每个节点验证它是否平衡。我们需要编写一个递归函数，该函数返回三件事：一个布尔值，用于指示树是否平衡，最小高度和最大高度。为了返回多个值，我们可以应用结构或通过引用传递变量。通过引用传递 maxh 和 minh 是为了可以在父级调用中使用这些值。
示例
/* 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
更新于: 2020-07-23
181 次查看
广告