Trong cây nhị phân, chỉ có hai nút (trái và phải) trong mỗi nút con. Cấu trúc cây chỉ đơn giản là biểu diễn dữ liệu. Cây tìm kiếm nhị phân (BST) là loại cây nhị phân đặc biệt đáp ứng các điều kiện này -
-
So với nút cha của nó, nút con bên trái nhỏ hơn
-
Nút cha của nút con bên phải lớn hơn nút con
Giả sử chúng ta được cung cấp một cây nhị phân và chúng ta phải tìm ra cây tìm kiếm nhị phân (BST) lớn nhất bên trong nó.
Trong tác vụ này, chúng ta sẽ tạo một hàm để tìm BST lớn nhất trong cây nhị phân. Khi bản thân cây nhị phân là một BST, có thể xác định kích thước của toàn bộ cây nhị phân. Ví dụ -
Đầu vào
10 /\ 5 15 /\ \ 1 8 7
Như đã trình bày, BST Subtree được đánh dấu, trong trường hợp này, là lớn nhất. '3' là kích thước của cây con, vì vậy giá trị trả về là kích thước của cây con.
Đầu vào
52 / \ 37 67 /\ / \ 12 27 57 77 /\ 72 87
Đầu ra
5
Các cây con có các nút có chiều dài nhỏ hơn chiều dài của các nút cha của chúng có tối đa ba nút BST có kích thước.
Phương pháp tiếp cận để tìm ra BST lớn nhất trong Cây nhị phân đã cho
Đối với mọi nút x, cây nhị phân là BST nếu các điểm sau hợp lệ. Chỉ các nút có dữ liệu nhỏ hơn dữ liệu của nút cha của chúng mới xuất hiện trong cây con bên trái của nút. Chỉ có thể có một nút có nhiều dữ liệu hơn nút cha của nó. Cả cây con trái và phải được đặc trưng bởi cây tìm kiếm nhị phân (BST).
Thuật toán sẽ -
Chúng ta sẽ bắt đầu từ gốc của cây nhị phân và thực hiện việc duyệt theo thứ tự bằng cách sử dụng đệ quy. Đối với nút hiện tại 'ROOT', chúng tôi sẽ thực hiện như sau-
-
Nếu nó là gốc của BST hợp lệ, chúng tôi trả về kích thước của nó.
-
Ngoài ra, chúng tôi sẽ tìm thấy BST lớn nhất trong các cây con bên trái và bên phải.
Ví dụ
#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;
} Đầu ra
Size of the largest BST is 2
Kết luận
Trong bài toán này, chúng ta đã tìm hiểu cây nhị phân &cây tìm kiếm nhị phân là gì và cách tìm ra BST lớn nhất trong cây nhị phân đã cho với sự trợ giúp của đệ quy. Với sự trợ giúp của đệ quy, chúng ta sẽ tìm hiểu xem cây con dưới mọi nút có phải là BST hay không và trả về các giá trị tương ứng.