ในต้นไม้แบบทวิภาค (Binary Tree) แต่ละโหนดลูกมีเพียงสองโหนด (ซ้ายและขวา) โครงสร้างต้นไม้เป็นการแทนข้อมูลอย่างง่าย Binary Search Trees (BST) เป็นประเภทพิเศษของ Binary Tree ที่ตรงตามเงื่อนไข:
- โหนดลูกซ้ายมีค่าน้อยกว่าโหนดพาเรนต์
- โหนดลูกขวามีค่ามากกว่าโหนดพาเรนต์
สมมติว่าเราได้รับต้นไม้แบบทวิภาค และต้องการหา Binary Search Tree (BST) ที่ใหญ่ที่สุดภายในต้นไม้นั้น
ในงานนี้ เราจะสร้างฟังก์ชันเพื่อหา BST ใหญ่ที่สุดในต้นไม้แบบทวิภาค เมื่อต้นไม้แบบทวิภาคเป็น BST เอง สามารถหาขนาดของต้นไม้ทั้งหมดได้ ตัวอย่าง:
ข้อมูลนำเข้า
10 /\ 5 15 /\ \ 1 8 7
ตามที่แสดง BST ย่อยที่ไฮไลท์ ในกรณีนี้เป็น BST ใหญ่ที่สุด '3' คือขนาดของย่อยต้นไม้ ดังนั้นค่าที่คืนคือขนาดของย่อยต้นไม้
ข้อมูลนำเข้า
52 / \ 37 67 /\ / \ 12 27 57 77 /\ 72 87
ข้อมูลส่งออก
5
ย่อยต้นไม้ที่มีโหนดซึ่งความยาวน้อยกว่าความยาวของโหนดพาเรนต์ มีขนาด BST ได้สูงสุด 3 โหนด
แนวทางการหา BST ใหญ่ที่สุดในต้นไม้แบบทวิภาคที่กำหนด
สำหรับทุกโหนด x ต้นไม้แบบทวิภาคจะเป็น BST หากเงื่อนไขต่อไปนี้เป็นจริง มีเฉพาะโหนดที่ข้อมูลน้อยกว่าโหนดพาเรนต์เท่านั้นที่ปรากฏในย่อยต้นไม้ซ้าย มีเพียงโหนดเดียวที่มีข้อมูลมากกว่าโหนดพาเรนต์ ย่อยต้นไม้ซ้ายและขวาทั้งคู่ควรเป็น Binary Search Trees (BST)
อัลกอริทึมจะเป็น −
เราจะเริ่มจากรูท (root) ของต้นไม้แบบทวิภาค และทำ in-order traversal โดยใช้การเรียกซ้ำ (recursion) สำหรับโหนดปัจจุบัน '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
สรุป
ในปัญหานี้ เราเรียนรู้ว่าต้นไม้แบบทวิภาคและ Binary Search Tree คืออะไร และวิธีหา BST ใหญ่ที่สุดในต้นไม้แบบทวิภาคที่กำหนดด้วยการเรียกซ้ำ ด้วยการเรียกซ้ำ เราจะหาว่าย่อยต้นไม้ภายใต้ทุกโหนดเป็น BST หรือไม่ และคืนค่าตามลำดับ
