এখানে আমরা দেখব, কিভাবে 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
