SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // корень
  6. struct TNode {
  7.     int x, y;
  8.     TNode *left, *right;
  9. };
  10.  
  11. // объединить два корня
  12. TNode* merge(TNode* left, TNode* right) {
  13.     if (!left)
  14.         return right;
  15.     if (!right)
  16.         return left;
  17.     if (left->y < right->y) {
  18.         left->right = merge(left->right, right);
  19.         return left;
  20.     } else {
  21.         right->left = merge(left, right->left);
  22.         return right;
  23.     }
  24. }
  25.  
  26. // разделить два корня
  27. pair<TNode*, TNode*> split(TNode* root, int x) {
  28.     if (!root)
  29.         return {nullptr, nullptr};
  30.     if (root->x > x) {
  31.         auto t=split(root->left, x);
  32.         root->left = t.second;
  33.         return {t.first, root};
  34.     } else {
  35.         auto t=split(root->right, x);
  36.         root->right = t.first;
  37.         return {root, t.second};
  38.     }
  39. }
  40.  
  41. // создать новый корень
  42. TNode* new_node(int x) {
  43.     return new TNode({x, rand(), nullptr, nullptr});
  44. }
  45.  
  46. // вставить новый корень
  47. TNode* insert(TNode* root, int x) {
  48.     TNode* node = new_node(x);
  49.     auto t=split(root, x);
  50.     return merge(t.first, merge(node, t.second));
  51. }
  52.  
  53. // удаляем корень
  54. TNode* erase(TNode* root, int x) {
  55.     auto t=split(root, x);
  56.     auto tt=split(t.first, x-1);
  57.     if (!tt.second)
  58.         return merge(tt.first, t.second);
  59.     else {
  60.         TNode* node = merge(tt.second->left, tt.second->right);
  61.         return merge(tt.first, merge(node, tt.second));
  62.     }
  63. }
  64.  
  65. // существует ли элемент
  66. bool exists(TNode* root, int x) {
  67.     if (!root)
  68.         return false;
  69.     if (root->x == x)
  70.         return false;
  71.     if (root->x > x)
  72.         return exists(root->left, x);
  73.     else
  74.         return exists(root->right, x);
  75. }
  76.  
  77. int main() {
  78.  
  79. }
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