• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?