यहां हम देखेंगे कि BST से फ्लोर और सीलिंग मान कैसे प्राप्त करें। उदाहरण के लिए, यदि हम एक मेमोरी प्रबंधन प्रणाली बनाना चाहते हैं, जहां फ्री नोड्स BST में व्यवस्थित हैं। इनपुट अनुरोध के लिए सर्वोत्तम फिट ढूंढें। मान लीजिए हम कुंजी मान से बड़े सबसे छोटे डेटा के साथ ट्री में नीचे जा रहे हैं, तो तीन संभावित मामले हैं।
- रूट ही कुंजी है। तब रूट मान सीलिंग मान है
- यदि रूट डेटा < कुंजी, तो सीलिंग मान बाएं सबट्री में नहीं होगा, फिर दाएं सबट्री में आगे बढ़ें, और समस्या डोमेन को कम करें
- यदि रूट डेटा > कुंजी, तो सीलिंग मान दाएं सबट्री में हो सकता है, हम बाएं सबट्री में कुंजी से बड़ा डेटा वाला नोड ढूंढ सकते हैं, यदि ऐसा कोई तत्व मौजूद नहीं है, तो रूट सीलिंग मान है।
मान लीजिए ट्री ऐसा है -
0, 1, 2 की सीलिंग 2 है, 3, 4 की सीलिंग 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
