資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告