Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<string>
- using namespace std;
- long long getRand() {
- return (rand() << 15) + rand();
- }
- struct Node {
- long long key, pr;
- Node *left, *right;
- Node(int k) : key(k), pr(getRand()), left(NULL), right(NULL) {}
- };
- Node *root;
- bool search(Node *tree, int key) {
- while(tree) {
- if(tree->key == key) return true;
- if(tree->key < key) tree = tree->right;
- if(tree->key > key) tree = tree->left;
- }
- return false;
- }
- pair < Node*, Node* > split(Node *tree, int k) {
- if(!tree) return make_pair((Node*)0, (Node*)0);
- if(tree->key <= k) {
- pair < Node*, Node* > p = split(tree->right, k);
- tree->right = p.first;
- return make_pair(tree, p.second);
- } else {
- pair < Node*, Node* > p = split(tree->left, k);
- tree->left = p.second;
- return make_pair(p.first, tree);
- }
- }
- Node* merge(Node* L, Node* R) {
- if(!L) return R;
- if(!R) return L;
- if(L->pr <= R->pr) {
- L->right = merge(L->right, R);
- return L;
- } else {
- R->left = merge(L, R->left);
- return R;
- }
- }
- Node* insert(Node* tree, int k) {
- Node* newnode = new Node(k);
- pair < Node*, Node* > p = split(tree, k);
- return merge(merge(p.first, newnode), p.second);
- }
- void delete_tree(Node* tree) {
- if(!tree) return;
- delete_tree(tree->left);
- delete_tree(tree->right);
- delete(tree);
- }
- Node* erase(Node* tree, int k) {
- pair < Node*, Node* > p = split(tree, k);
- pair < Node*, Node* > p2 = split(tree, k);
- delete_tree(p2.second);
- return merge(p2.first, p.second);
- }
- int main() {
- string s;
- while(cin >> s) {
- int k;
- cin >> k;
- if(s == "insert") {
- insert(root, k);
- }
- if(s == "delete") {
- erase(root, k);
- }
- if(s == "exists") {
- bool f = search(root, k);
- if(f) cout << "true" << endl;
- else cout << "false" << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement