SHARE
TWEET

Untitled

a guest Dec 8th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define int long long
  4. #define TASKNAME "bstsimple"
  5. using namespace std;
  6.  
  7.  
  8.  
  9. struct bts{
  10.     struct Node {
  11.         Node *l , *r ;
  12.         int val;
  13.         Node(int x) {
  14.             l = nullptr;
  15.             r = nullptr;
  16.             val = x;
  17.         }
  18.     };
  19.  
  20.     Node *root = nullptr;
  21.  
  22.     bool exists(int x) {
  23.         Node *cur = root;
  24.         while (cur) {
  25.             if (x > cur->val) {
  26.                 cur = cur->r;
  27.             } else if (x < cur->val) {
  28.                 cur = cur->l;
  29.             } else {
  30.                 return true;
  31.             }
  32.         }
  33.         return false;
  34.     }
  35.  
  36.  
  37.     void push(int x) {
  38.         if (root == nullptr) {
  39.             root = new Node(x);
  40.             return;
  41.         }
  42.         Node *cur = root;
  43.         while (cur) {
  44.             if (x > cur->val) {
  45.                 if (cur->r == nullptr) {
  46.                     cur->r = new Node(x);
  47.                     return;
  48.                 }
  49.                 cur = cur->r;
  50.             } else if (x < cur->val) {
  51.                 if (cur->l == nullptr) {
  52.                     cur->l = new Node(x);
  53.                     return;
  54.                 }
  55.                 cur = cur->l;
  56.             } else {
  57.                 return;
  58.             }
  59.         }
  60.         return;
  61.     }
  62.  
  63.  
  64.     void rem(int x) {
  65.         Node *to_delete = root;
  66.         Node *parent = nullptr;
  67.         bool left = false;
  68.         while (to_delete) {
  69.             if (x > to_delete->val) {
  70.                 parent = to_delete;
  71.                 left = false;
  72.                 to_delete = to_delete->r;
  73.             } else if (x < to_delete->val) {
  74.                 parent = to_delete;
  75.                 left = true;
  76.                 to_delete = to_delete->l;
  77.             } else {
  78.                 break;
  79.             }
  80.         }
  81.         if (to_delete == nullptr || to_delete->val != x) return;
  82.         if (to_delete->l != nullptr) {
  83.             Node *r_node = to_delete->r;
  84.             Node *temp = to_delete->l;
  85.             while (temp->r != nullptr) {
  86.                 temp = temp->r;
  87.             }
  88.             temp->r = r_node;
  89.             to_delete = to_delete->l;
  90.         } else if (to_delete->l == nullptr) {
  91.             to_delete = to_delete->r;
  92.         }
  93.         if (parent != nullptr) {
  94.             if (left) {
  95.                 parent->l = to_delete;
  96.             } else {
  97.                 parent->r = to_delete;
  98.             }
  99.         } else {
  100.             root = to_delete;
  101.         }
  102.     }
  103.  
  104.     int next(int x) {
  105.         if (root == nullptr) {
  106.             return INT_MIN;
  107.         }
  108.         Node *cur = root;
  109.         int ans = INT_MAX;
  110.         while (cur) {
  111.             if (x >= cur->val) {
  112.                 if (cur->r == nullptr) {
  113.                     return ans;
  114.                 }
  115.                 cur = cur->r;
  116.             } else if (x < cur->val) {
  117.                 ans = cur->val;
  118.                 if (cur->l == nullptr) {
  119.                     return ans;
  120.                 }
  121.                 cur = cur->l;
  122.             } else {
  123.                 return ans;
  124.             }
  125.         }
  126.         return ans;
  127.     }
  128.  
  129.     int prev(int x) {
  130.         if (root == nullptr) {
  131.             return INT_MIN;
  132.         }
  133.         Node *cur = root;
  134.         int ans = INT_MIN;
  135.         while (cur) {
  136.             if (x > cur->val) {
  137.                 ans = cur->val;
  138.                 if (cur->r == nullptr) {
  139.                     return ans;
  140.                 }
  141.                 cur = cur->r;
  142.             } else if (x <= cur->val) {
  143.                 if (cur->l == nullptr) {
  144.                     return ans;
  145.                 }
  146.                 cur = cur->l;
  147.             } else {
  148.                 return ans;
  149.             }
  150.         }
  151.         return ans;
  152.     }
  153. };
  154.  
  155.  
  156. // #define DEV
  157. int32_t main() {
  158.     #ifndef DEV
  159.         freopen(TASKNAME".in", "r", stdin);
  160.         freopen(TASKNAME".out", "w", stdout);
  161.     #endif
  162.     string s;
  163.     bts kek;
  164.     while (cin >> s) {
  165.         if (s == "insert") {
  166.             int x; cin >> x;
  167.             kek.push(x);
  168.         }
  169.         if (s == "delete") {
  170.             int x; cin >> x;
  171.             kek.rem(x);
  172.         }
  173.         if (s == "exists") {
  174.             int x;
  175.             cin >> x;
  176.             if (kek.exists(x)) {
  177.                 cout << "true" << endl;
  178.             } else {
  179.                 cout << "false" << endl;
  180.             }
  181.         }
  182.         if (s == "next") {
  183.             int x;
  184.             cin >> x;
  185.             int ans = kek.next(x);
  186.             if (ans == INT_MIN || ans == INT_MAX) {
  187.                 cout << "none\n";
  188.             } else {
  189.                 cout << ans << endl;
  190.             }
  191.         }
  192.         if (s == "prev") {
  193.             int x;
  194.             cin >> x;
  195.             int ans = kek.prev(x);
  196.             if (ans == INT_MIN || ans == INT_MAX) {
  197.                 cout << "none\n";
  198.             } else {
  199.                 cout << ans << endl;
  200.             }
  201.         }
  202.  
  203.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top