Emiliatan

__treap

Jan 27th, 2019
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5. typedef long long int64;
  6. typedef unsigned int uint;
  7.  
  8. template<typename T>
  9. class __treap
  10. {
  11.     private:
  12.  
  13.     struct node
  14.     {
  15.         node *left, *right;
  16.         T value;
  17.         int priority, wi;
  18.     }*root;
  19.  
  20.  
  21.     void rotate_right(node *&now)
  22.     {
  23.         node *tmp = now -> left;
  24.         now -> left = tmp -> right;
  25.         tmp -> right = now;
  26.         now = tmp;
  27.     }
  28.  
  29.     void rotate_left(node *&now)
  30.     {
  31.         node *tmp = now -> right;
  32.         now -> right = tmp -> left;
  33.         tmp -> left = now;
  34.         now =tmp;
  35.     }
  36.  
  37.     void erase(node *&now, T value)
  38.     {
  39.         if(now == NULL) return;
  40.         if(now -> value == value)
  41.         {
  42.             if(now -> left == NULL)
  43.                 now = now -> right;
  44.             else if(now -> right == NULL)
  45.                 now = now -> left;
  46.             else
  47.             {
  48.                 if(now -> left -> priority < now -> right -> priority)
  49.                 {
  50.                     rotate_right(now);
  51.                     erase(now -> right, value);
  52.                 }
  53.                 else
  54.                 {
  55.                     rotate_left(now);
  56.                     erase(now -> left, value);
  57.                 }
  58.             }
  59.         }
  60.         else if(value < now -> value) erase(now -> left, value);
  61.         else erase(now -> right, value);
  62.     }
  63.  
  64.     void insert(node *&now, T &value)
  65.     {
  66.         if(now == NULL)
  67.         {
  68.             now = new node;
  69.             now -> left = now -> right = NULL;
  70.             now -> value = value;
  71.             now -> priority = rand();
  72.         }
  73.         else if(value <= now -> value)
  74.         {
  75.             insert(now -> left, value);
  76.             if(now -> left -> priority < now -> priority)
  77.                 rotate_right(now);
  78.         }
  79.         else
  80.         {
  81.             insert(now -> right, value);
  82.             if(now -> right -> priority < now -> priority)
  83.                 rotate_left(now);
  84.         }
  85.     }
  86.  
  87.     bool find(node *&now, T value)
  88.     {
  89.         if(now == NULL) return false;
  90.         if(now -> value == value) return true;
  91.         if(now -> value > value) return find(now -> left, value);
  92.         else return find(now -> right, value);
  93.         return false;
  94.     }
  95.  
  96.     T find_max(node *now)
  97.     {
  98.         while(now -> right != NULL)
  99.             now = now -> right;
  100.         return now -> value;
  101.     }
  102.  
  103.     T find_min(node *now)
  104.     {
  105.         while(now -> left != NULL)
  106.             now = now -> left;
  107.         return now -> value;
  108.     }
  109.  
  110.     void clear(node *&now)
  111.     {
  112.         if(now != NULL)
  113.         {
  114.             clear(now -> left);
  115.             clear(now -> right);
  116.             delete now;
  117.             now = NULL;
  118.         }
  119.     }
  120.  
  121.     public:
  122.  
  123.     __treap()
  124.     {
  125.         root = NULL;
  126.     }
  127.     ~__treap()
  128.     {
  129.         clear(root);
  130.     }
  131.     void insert(T value)
  132.     {
  133.         insert(root, value);
  134.     }
  135.     void erase(T value)
  136.     {
  137.         erase(root, value);
  138.     }
  139.     bool find(T value)
  140.     {
  141.         return find(root, value);
  142.     }
  143.     T find_max()
  144.     {
  145.         return find_max(root);
  146.     }
  147.     T find_min()
  148.     {
  149.         return find_min(root);
  150.     }
  151. };
  152.  
  153. /**
  154.  
  155. __treap< Type > treap;                     //Create
  156.  
  157. treap.insert(x);                           //insert(x)
  158.  
  159. bool IsFound = treap.find(x);              //find(x)
  160.  
  161. if(IsFound) {...}
  162. else {...}
  163.  
  164. treap.erase(x);                            //erase(x)
  165.  
  166. T x = treap.find_min()/find_max();         //find_max() or min()
  167.  
  168. */
Advertisement
Add Comment
Please, Sign In to add comment