এখানে আমরা দেখব কিভাবে BST থেকে ফ্লোর এবং সিলিং মান বের করা যায়। উদাহরণস্বরূপ, যদি আমরা একটি মেমরি ম্যানেজমেন্ট সিস্টেম তৈরি করি, যেখানে ফ্রি নোডগুলো BST-তে সাজানো থাকে। ইনপুট রিকোয়েস্টের জন্য বেস্ট ফিট বের করতে হবে। ধরুন আমরা ট্রি নিচে নামছি সবচেয়ে ছোট ডেটা যা কী ভ্যালুর চেয়ে বড়, তখন তিনটি কেস সম্ভব:
- রুটই কী। তবে রুট ভ্যালুই সিলিং ভ্যালু।
- যদি রুট ডেটা < কী, তবে সিলিং ভ্যালু বাম সাবট্রিতে নয়, তাই ডান সাবট্রিতে যান এবং সমস্যা ডোমেইন কমানো।
- যদি রুট ডেটা > কী, তবে সিলিং ভ্যালু ডান সাবট্রিতে হতে পারে, আমরা বাম সাবট্রিতে কী থেকে বড় ডেটা वाला নোড খুঁজে পেতে পারি, যদি এমন কোনো উপাদান না থাকে, তবে রুটই সিলিং ভ্যালু।
ধরুন ট্রিটি নিচের মত:
০, ১, ২-এর সিলিং ২, ৩, ৪-এর সিলিং ৪ এবং এভাবেই।
এখানে আমরা শুধু সিলিং ফাংশন দেখব, একটু মডিফাই করলে ফ্লোর মানও পাওয়া যাবে।
উদাহরণ
#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
