ตรวจสอบว่า Binary Tree นั้นมีความสูงที่สมดุลเหมือน Red-Black Tree ใน C++ . หรือไม่

แนวคิด

สำหรับต้นไม้สีแดง-ดำ ความสูงที่ใหญ่ที่สุดของโหนดจะสูงเป็นสองเท่าของความสูงขั้นต่ำขั้นต่ำสำหรับต้นไม้การค้นหาไบนารีที่กำหนด เราจำเป็นต้องตรวจสอบคุณสมบัติต่อไปนี้

สำหรับโหนดทุกโหนด ความยาวของเส้นทางลีฟไปยังโหนดที่ยาวที่สุดมีไม่เกินสองเท่าของโหนดบนเส้นทางที่สั้นที่สุดจากโหนดหนึ่งไปอีกโหนดหนึ่ง

ตัวอย่าง

13    41
\    / \
15  11 101
\   /    \
17 61 151

ต้นไม้ด้านบนไม่สามารถเป็นต้นไม้สีแดง-ดำ ต้นไม้ด้านบนสามารถเป็นต้นไม้สีแดง-ดำได้ด้วยการกำหนดสีใดๆ

ความสูงสูงสุด 13 คือ 1

ความสูงขั้นต่ำ 13 คือ 3

   11
  / \
 6   101
 /    \
51    151
/
41

บนต้นไม้ก็สามารถเป็นต้นไม้สีแดง-ดำได้

ในกรณีนี้ ความซับซ้อนของเวลาที่คาดหวังคือ O(n) ควรเยี่ยมชมต้นไม้อย่างน้อยที่สุดหนึ่งครั้งในสารละลาย

วิธีการ

ในส่วนที่เกี่ยวกับทุกโหนด เราต้องการความสูงที่ใหญ่ที่สุดและเล็กที่สุดและเปรียบเทียบ แนวคิดคือการเยี่ยมชมต้นไม้และให้ทุกโหนดตรวจสอบว่ามีความสมดุลหรือไม่ ความต้องการของเราคือการเขียนฟังก์ชันแบบเรียกซ้ำที่ส่งคืนสามสิ่ง ค่าบูลีนเพื่อระบุว่าต้นไม้มีความสมดุลหรือไม่ ความสูงน้อยที่สุดและความสูงที่ใหญ่ที่สุด สำหรับการคืนค่าหลายค่า เราสามารถใช้โครงสร้างหรือส่งผ่านตัวแปรโดยการอ้างอิง การส่งการอ้างอิง maxh และ minhby จะดำเนินการเพื่อให้ค่าสามารถนำมาใช้ในการเรียก parent ได้

ตัวอย่าง

/* 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