यहां हम देखेंगे कि बीएसटी से फ्लोर और सीलिंग वैल्यू कैसे पता करें। उदाहरण के लिए, यदि हम एक मेमोरी मैनेजमेंट सिस्टम बनाना चाहते हैं, जहां BST में फ्री नोड्स की व्यवस्था की जाती है। इनपुट अनुरोध के लिए सबसे उपयुक्त खोजें। मान लीजिए कि हम कुंजी मान से बड़े छोटे डेटा वाले पेड़ को नीचे ले जा रहे हैं, तो तीन संभावित मामले हैं।
- जड़ कुंजी है। तब मूल मान अधिकतम मूल्य होता है
- यदि रूट डेटा <कुंजी है, तो सीलिंग वैल्यू लेफ्ट सबट्री पर नहीं होगी, फिर राइट सबट्री पर आगे बढ़ें, और प्रॉब्लम डोमेन को कम करें
- यदि रूट डेटा> कुंजी है, तो सीलिंग मान दाएं सबट्री पर हो सकता है, हमें बाएं सबट्री में कुंजी की तुलना में बड़े डेटा वाला नोड मिल सकता है, यदि ऐसा कोई तत्व मौजूद नहीं है, तो रूट सीलिंग वैल्यू है।
मान लीजिए पेड़ इस तरह है -
0, 1, 2 की सीलिंग 2 है, 3 की सीलिंग है, 4 है और इसी तरह आगे भी
यहां हम केवल सीलिंग फंक्शन देखेंगे, अगर हम इसे थोड़ा संशोधित करते हैं, तो हम फ्लोर वैल्यू प्राप्त कर सकते हैं।
उदाहरण
#include <iostream>
using namespace std;
class node {
public:
int key;
node* left;
node* right;
};
node* getNode(int key) {
node* newNode = new node();
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int ceiling(node* root, int num) {
if (root == NULL)
return -1;
if (root->key == num)
return root->key;
if (root->key < num)
return ceiling(root->right, num);
int ceil = ceiling(root->left, num);
return (ceil >= num) ? ceil : root->key;
}
int main() {
node* root = getNode(8);
root->left = getNode(4);
root->right = getNode(12);
root->left->left = getNode(2);
root->left->right = getNode(6);
root->right->left = getNode(10);
root->right->right = getNode(14);
for (int i = 0; i < 16; i++)
cout << i << "\tCeiling: " << ceiling(root, i) << endl;
} आउटपुट
0 Ceiling: 2 1 Ceiling: 2 2 Ceiling: 2 3 Ceiling: 4 4 Ceiling: 4 5 Ceiling: 6 6 Ceiling: 6 7 Ceiling: 8 8 Ceiling: 8 9 Ceiling: 10 10 Ceiling: 10 11 Ceiling: 12 12 Ceiling: 12 13 Ceiling: 14 14 Ceiling: 14 15 Ceiling: -1