सी ++ में बाइनरी सर्च ट्री में निकटतम तत्व खोजें

मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री (BST) और दूसरा लक्ष्य मान है; हमें उस दिए गए BST में k मान ज्ञात करना है जो लक्ष्य के सबसे निकट है। यहां लक्ष्य मान एक फ़्लोटिंग-पॉइंट नंबर है। हम मान सकते हैं कि k हमेशा मान्य होता है, और k कुल नोड्स।

तो, अगर इनपुट पसंद है

लक्ष्य =3.714286, और k =2, तो आउटपुट [4,3]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• पुशस्मॉलर () फ़ंक्शन को परिभाषित करें, यह नोड, स्टैक सेंट और लक्ष्य लेगा,

• जबकि नोड मौजूद नहीं है, करें -

  • यदि नोड का मान <लक्ष्य है, तो -

    • सेंट में नोड डालें

    • नोड:=नोड के दाईं ओर

  • अन्यथा

    • नोड :=नोड के बाईं ओर

• एक फ़ंक्शन पुशलार्जर () को परिभाषित करें, यह नोड, स्टैक सेंट, लक्ष्य,

  . लेगा

• जबकि नोड खाली है, करें -

  • यदि नोड का मान>=लक्ष्य है, तो −

    • सेंट में नोड डालें

    • नोड :=नोड के बाईं ओर

  • अन्यथा

    • नोड:=नोड के दाईं ओर

• मुख्य विधि से निम्न कार्य करें -

• एक सरणी रिट परिभाषित करें

• एक स्टैक को छोटा परिभाषित करें

• एक स्टैक को बड़ा परिभाषित करें

• pushLarger(रूट, बड़ा, लक्ष्य)

• pushSmaller(रूट, छोटा, लक्ष्य)

• जबकि k गैर-शून्य है, प्रत्येक चरण में k घटाएं, −

  . करें

  • यदि छोटा खाली नहीं है और (बड़ा खाली है या |लक्ष्य - छोटे के शीर्ष तत्व का मान| <|लक्ष्य - बड़े का शीर्ष तत्व|)

    • curr =छोटे का शीर्ष तत्व

    • तत्व को छोटे से हटाएं

    • रिट के अंत में वैल का वैल डालें

    • pushSmaller(बाएं कर्व, छोटा, लक्ष्य)

  • अन्यथा

    • curr =बड़े का शीर्ष तत्व

    • एलिमेंट को बड़े से हटाएं

    • रिट के अंत में वैल का वैल डालें

    • pushSmaller(दाहिने कर्व, बड़ा, लक्ष्य)

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
         right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   vector<int> closestKValues(TreeNode* root, double target, int k){
      vector<int> ret;
      stack<TreeNode*> smaller;
      stack<TreeNode*> larger;
      pushLarger(root, larger, target);
      pushSmaller(root, smaller, target);
      while (k--) {
         if (!smaller.empty() && (larger.empty() || (abs(target - smaller.top()->val) < abs(target - larger.top()->val)))) {
            TreeNode* curr = smaller.top();
            smaller.pop();
            ret.push_back(curr->val);
            pushSmaller(curr->left, smaller, target);
         }
         else {
            TreeNode* curr = larger.top();
            larger.pop();
            ret.push_back(curr->val);
            pushLarger(curr->right, larger, target);
      }
   }
   return ret;
}
void pushSmaller(TreeNode* node, stack <TreeNode*>& st, double target){
   while (node) {
      if (node->val < target) {
         st.push(node);
         node = node->right;
      }
      else {
         node = node->left;
      }
   }
}
void pushLarger(TreeNode* node, stack <TreeNode*>& st, double target){
   while (node) {
      if (node->val >= target) {
         st.push(node);
         node = node->left;
      }
      else
         node = node->right;
      }
   }
};
main(){
   Solution ob;
   vector<int> v = {4,2,5,1,3};
   TreeNode *root = make_tree(v);
   print_vector(ob.closestKValues(root, 3.7142, 2));
}

इनपुट

{4,2,5,1,3}, 3.7142, 2

आउटपुट

[4, 3, ]