Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ค่าทรีการค้นหาไบนารีที่ใกล้ที่สุด II ใน C++


สมมติว่าเรามีแผนผังการค้นหาแบบไบนารีและค่าเป้าหมาย เราต้องหาค่า k ใน BST นั้นที่ใกล้กับเป้าหมายมากที่สุด เราต้องจำไว้ว่าค่าเป้าหมายเป็นตัวเลขทศนิยม เราสามารถสมมติได้ว่า k ถูกต้องเสมอ และ k ≤ โหนดทั้งหมด

ดังนั้นหากอินพุตเป็นแบบ

ค่าทรีการค้นหาไบนารีที่ใกล้ที่สุด II ใน C++

เป้าหมาย =3.714286 และ k =2 จากนั้นผลลัพธ์จะเป็น [4,3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • กำหนดฟังก์ชัน pushSmaller() ซึ่งจะใช้ node,stack st และ target

  • ในขณะที่ไม่มีโหนด ให้ทำ -

    • ถ้า val ของโหนด <เป้าหมาย แล้ว −

      • แทรกโหนดลงใน st

      • โหนด :=ด้านขวาของโหนด

    • มิฉะนั้น

      • โหนด :=ด้านซ้ายของโหนด

  • กำหนดฟังก์ชัน pushLarger() ซึ่งจะรับ node, stack st, target

  • ขณะที่โหนดว่าง ให้ทำ -

    • ถ้า val ของโหนด>=เป้าหมาย แล้ว −

      • แทรกโหนดลงใน st

      • โหนด :=ด้านซ้ายของโหนด

    • มิฉะนั้น

      • โหนด :=ด้านขวาของโหนด

  • จากวิธีหลัก ให้ทำดังต่อไปนี้ −

  • กำหนดอาร์เรย์ ret

  • กำหนดหนึ่งกองที่เล็กกว่า

  • กำหนดหนึ่งกองที่ใหญ่ขึ้น

  • pushLarger(รูท ใหญ่กว่า เป้าหมาย)

  • pushSmaller(รูท เล็กกว่า เป้าหมาย)

  • ในขณะที่ k ไม่ใช่ศูนย์ ให้ลด k ในแต่ละขั้นตอน ทำ -

    • ถ้าเล็กกว่าไม่ว่างเปล่าและ (ขนาดใหญ่กว่าว่างเปล่าหรือ |target - ค่าขององค์ประกอบด้านบนของที่เล็กกว่า| <|เป้าหมาย - องค์ประกอบด้านบนของขนาดใหญ่กว่า|)

      • curr =องค์ประกอบด้านบนของที่เล็กกว่า

      • ลบองค์ประกอบออกจากที่เล็กกว่า

      • ใส่ val ของ curr ที่ส่วนท้ายของ ret

      • pushSmaller(ซ้ายของสกุลเงิน เล็กกว่า เป้าหมาย)

    • มิฉะนั้น

      • curr =องค์ประกอบด้านบนของที่ใหญ่กว่า

      • ลบองค์ประกอบออกจากที่ใหญ่กว่า

      • ใส่ val ของ curr ที่ส่วนท้ายของ ret

      • pushSmaller(ด้านขวาของสกุลเงิน, ใหญ่กว่า, เป้าหมาย)

  • รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   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, ]