SHARE
TWEET

Untitled

a guest Jun 17th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include<string>
  3.  
  4. using namespace std;
  5.  
  6. struct Node {
  7.     Node *l, *r;
  8.     long long key, pr;
  9.     Node(int x) : key(x), pr(rand()), l(nullptr), r(nullptr) {}
  10. };
  11.  
  12. Node* merge(Node* L, Node* R) {
  13.     if (L == nullptr) return R;
  14.     if (R == nullptr) return L;
  15.     if (L->pr > R->pr) {
  16.         L->r = merge(L->r, R);
  17.         return L;
  18.     }
  19.     R->l = merge(L, R->l);
  20.     return R;
  21. }
  22.  
  23. pair < Node*, Node* > split(Node* tree, int k) {
  24.     if (tree == nullptr) return {nullptr, nullptr};
  25.     if (tree->key <= k) {
  26.         pair < Node*, Node* > p = split(tree->r, k);
  27.         tree->r = p.first;
  28.         return {tree, p.second};
  29.     }
  30.     auto p = split(tree->l, k);
  31.     tree->l = p.second;
  32.     return {p.first, tree};
  33. }
  34.  
  35. Node* insert(Node* tree, int k) {
  36.     auto p = split(tree, k);
  37.     Node* v = new Node(k);
  38.     return merge(merge(p.first, v), p.second);
  39. }
  40.  
  41. Node* erase(Node* tree, int k) {
  42.     if (tree == nullptr) return tree;
  43.     if (tree->key == k) return merge(tree->l, tree->r);
  44.     if (tree->key < k) {
  45.         tree->r = erase(tree->r, k);
  46.     } else {
  47.         tree->l = erase(tree->l, k);
  48.     }
  49.     return tree;
  50. }
  51.  
  52. bool search(Node* tree, int k) {
  53.     if (tree == nullptr) return false;
  54.     if (tree->key == k) return true;
  55.     if (tree->key < k) return search(tree->r, k);
  56.     return search(tree->l, k);
  57. }
  58.  
  59. int main() {
  60.     Node *root = nullptr;
  61.     string s;
  62.     long long k;
  63.     while (cin >> s) {
  64.         cin >> k;
  65.         if (s == "insert") {
  66.             bool f = search(root, k);
  67.             if (!f) root = insert(root, k);
  68.         } else if (s == "delete") {
  69.             bool f = search(root, k);
  70.             if (f) root = erase(root, k);
  71.         } else {
  72.             bool f = search(root, k);
  73.             if(f) cout << "true" << endl;
  74.             else cout << "false" << endl;
  75.         }
  76.     }
  77.     return 0;
  78. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top