ในไบนารีทรี มีเพียงสองโหนด (ซ้ายและขวา) ในแต่ละโหนดย่อย โครงสร้างแบบต้นไม้เป็นเพียงการแสดงข้อมูล Binary Search Trees (BST) เป็น Binary Tree ชนิดพิเศษที่ตรงตามเงื่อนไขเหล่านี้ -
-
เมื่อเปรียบเทียบกับพาเรนต์ โหนดย่อยด้านซ้ายมีขนาดเล็กกว่า
-
โหนดแม่ของลูกด้านขวามีขนาดใหญ่กว่าโหนดลูก
สมมติว่าเราได้รับไบนารีทรี และเราควรจะค้นหาว่าอะไรคือโครงสร้างการค้นหาไบนารีที่ใหญ่ที่สุด (BST) ภายในนั้น
ในงานนี้ เราจะสร้างฟังก์ชันเพื่อค้นหา BST ที่ใหญ่ที่สุดในไบนารีทรี เมื่อไบนารีทรีเป็นตัว BST เป็นไปได้ที่จะกำหนดขนาดของไบนารีทรีทั้งหมด ยกตัวอย่าง −
ป้อนข้อมูล
10 /\ 5 15 /\ \ 1 8 7
ดังที่แสดง แผนผังย่อยของ BST ที่เน้น ในกรณีนี้ ใหญ่ที่สุด '3' คือขนาดของทรีย่อย ดังนั้นค่าที่ส่งคืนคือขนาดของทรีย่อย
ป้อนข้อมูล
52 / \ 37 67 /\ / \ 12 27 57 77 /\ 72 87
ผลผลิต
5
ทรีย่อยที่มีโหนดที่มีความยาวน้อยกว่าความยาวของโหนดหลักจะมีโหนด BST สูงสุดสามขนาด
แนวทางในการค้นหา BST ที่ใหญ่ที่สุดในแผนภูมิไบนารีที่กำหนด
สำหรับทุกโหนด x ต้นไม้ไบนารีคือ BST หากจุดต่อไปนี้ถูกต้อง เฉพาะโหนดที่มีข้อมูลน้อยกว่าโหนดหลักเท่านั้นที่จะปรากฏในทรีย่อยด้านซ้ายของโหนด มีได้เพียงโหนดเดียวเท่านั้นที่มีข้อมูลมากกว่าโหนดหลัก ต้นไม้ย่อยทั้งซ้ายและขวาควรมีลักษณะเป็นต้นไม้การค้นหาแบบไบนารี (BST)
อัลกอริทึมจะเป็น −
เราจะเริ่มจากรูทของไบนารีทรีและทำการข้ามผ่านตามลำดับโดยใช้การเรียกซ้ำ สำหรับโหนดปัจจุบัน 'ROOT' เราจะทำสิ่งต่อไปนี้-
-
หากเป็นรูทของ BST ที่ถูกต้อง เราจะคืนค่าขนาด
-
มิฉะนั้น เราจะพบ BST ที่ใหญ่ที่สุดในทรีย่อยด้านซ้ายและขวา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *
newNode (int data) {
struct Node *node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
struct Detail {
int size;
int max;
int min;
int ans;
bool isBST;
};
bool isBST (Node * root, int min, int max) {
if (root == NULL) {
return true;
}
if (root->data < min || root->data > max) {
return false;
}
return isBST (root->left, min, root->data - 1) &&
isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
if (root == NULL) {
return 0;
}
return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
// Current Subtree is BST.
if (isBST (root, INT_MIN, INT_MAX) == true) {
return size (root);
}
// Find largest BST in left and right subtrees.
return max (largestBST (root->left), largestBST (root->right));
}
int main () {
struct Node *root = newNode (67);
root->left = newNode (72);
root->right = newNode (77); root->left->left = newNode (57);
printf ("Size of the largest BST is %d", largestBST (root));
return 0;
} ผลลัพธ์
Size of the largest BST is 2
บทสรุป
ในปัญหานี้ เราได้เรียนรู้ว่าไบนารีทรีและทรีการค้นหาแบบไบนารีคืออะไร และวิธีค้นหา BST ที่ใหญ่ที่สุดในแผนผังไบนารีที่กำหนดโดยใช้การเรียกซ้ำ ด้วยความช่วยเหลือของการเรียกซ้ำ เราจะค้นหาว่าทรีย่อยภายใต้ทุกโหนดเป็น BST หรือไม่ และคืนค่าตามนั้น
