fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class splay_tree{
  5. private:
  6.     struct node{
  7.         node *left,*right,*parent;
  8.         int key,sz;
  9.         node(int key): key(key), sz(1), left(0), right(0), parent(0) {}
  10.         node() {}
  11.     } *root;
  12.  
  13.     void recalc(node *v){
  14.         if(!v) return;
  15.         v->sz=1;
  16.         if(v->left) v->sz+=v->left->sz;
  17.         if(v->right) v->sz+=v->right->sz;
  18.     }
  19.  
  20.     bool is_root(node *x){
  21.         if(!x) return false;
  22.         if(x->parent) return true;
  23.         return false;
  24.     }
  25.  
  26.     void right_rotate(node *x){
  27.         node *y=x->left;
  28.         node *B=y->right;
  29.         if(is_root(x)) root=y; else
  30.         if(!is_root(x)){
  31.             node *P=x->parent;
  32.             if(P->left==x) P->left=y;
  33.                 else P->right=y;
  34.         }
  35.         x->left=B;
  36.         if(B) B->parent=x;
  37.         y->right=x;
  38.         y->parent=x->parent;
  39.         x->parent=y;
  40.         recalc(y->parent);
  41.         recalc(x);
  42.         recalc(y);
  43.     }
  44.  
  45.     void left_rotate(node *x){
  46.         node *y=x->right;
  47.         node *B=y->left;
  48.         if(is_root(x)) root=y; else
  49.         if(!is_root(x)){
  50.             node *P=x->parent;
  51.             if(P->left==x) P->left=y;
  52.                 else P->right=y;
  53.         }
  54.         x->right=B;
  55.         if(B) B->parent=x;
  56.         y->left=x;
  57.         y->parent=x->parent;
  58.         x->parent=y;
  59.         recalc(y->parent);
  60.         recalc(x);
  61.         recalc(y);
  62.     }
  63.  
  64.     void splay(node *x){
  65.         if(!x) return;
  66.         while(!is_root(x)){
  67.             node *p=x->parent;
  68.             if(is_root(p)){
  69.                 if(p->left==x) right_rotate(p);
  70.                     else left_rotate(p);
  71.             } else
  72.             if(p->parent->left==p && p->left==x){
  73.                 right_rotate(p->parent);
  74.                 right_rotate(p);
  75.             } else
  76.             if(p->parent->right==p && p->right==x){
  77.                 left_rotate(p->parent);
  78.                 left_rotate(p);
  79.             } else
  80.             if(p->parent->left==p && p->right==x){
  81.                 left_rotate(x->parent);
  82.                 right_rotate(x->parent);
  83.             } else {
  84.                 right_rotate(x->parent);
  85.                 left_rotate(x->parent);
  86.             }
  87.         }
  88.     }
  89.  
  90.     node *subtree_min(node *x){
  91.         while(x->left) x=x->left;
  92.         return x;
  93.     }
  94.     node *subtree_max(node *x){
  95.         while(x->right) x=x->right;
  96.         return x;
  97.     }
  98.  
  99.     void replace( node *p, node *v ) {
  100.         if( !p->parent ) root = v;
  101.         else if( p == p->parent->left ) p->parent->left = v;
  102.         else p->parent->right = v;
  103.         if( v ) v->parent = p->parent;
  104.         recalc(p);
  105.         recalc(v);
  106.     }
  107.  
  108. public:
  109.     splay_tree(): root(0) {}
  110.  
  111.     void insert(const int& key){
  112.         if(!root){
  113.             root=new node(key);
  114.             return;
  115.         }
  116.         node *z=root,*p=0;
  117.         while(z){
  118.             p=z;
  119.             if(z->key<key) z=z->right;
  120.                 else z=z->left;
  121.         }
  122.         z=new node(key);
  123.         z->parent=p;
  124.         if(!p) root=z; else
  125.         if(p->key<key) p->right=z;
  126.             else p->left=z;
  127.         for(;p;p=p->parent) p->sz++;
  128.         splay(z);
  129.     }
  130.  
  131.     node *find(int key){
  132.         node *z=root;
  133.         while(z){
  134.             if(z->key>key) z=z->left; else
  135.             if(z->key<key) z=z->right;
  136.                 else return z;
  137.         }
  138.         return 0;
  139.     }
  140.  
  141.     ///          TO DO
  142.     void erase(int key){
  143.         node *z=find(key);
  144.         if(!z) return;
  145.         splay(z);
  146.         if(!z->left && !z->right){
  147.             root=0;
  148.             return;
  149.         }
  150.         if(!z->left) replace(z,z->right); else
  151.         if(!z->right) replace(z,z->left); else {
  152.             node *y=subtree_min(z->right);
  153.             if(y->parent!=z){
  154.                 replace(y,y->right);
  155.                 y->right=z->right;
  156.                 y->right->parent=y;
  157.             }
  158.             replace(z,y);
  159.             y->left=z->left;
  160.             y->left->parent=y;
  161.         }
  162.         delete(z);
  163.     }
  164.  
  165.     void write(){
  166.         queue<node*> q;
  167.         q.push(root);
  168.         while(!q.empty()){
  169.             node *v=q.front();
  170.             q.pop();
  171.             printf("key=%d size=%d",v->key,v->sz);
  172.             if(v->left){
  173.                 q.push(v->left);
  174.                 printf(" left=%d",v->left->key);
  175.             }
  176.             if(v->right){
  177.                 q.push(v->right);
  178.                 printf(" right=%d",v->right->key);
  179.             }
  180.             printf("\n");
  181.         }
  182.     }
  183.  
  184.     ///   TO CHECK
  185.     int& operator [](int k){
  186.         node *z=root;
  187.         int tmp=0;
  188.         while(z){
  189.             int q=tmp;
  190.             if(z->left) q+=z->left->sz;
  191.             if(q+1==k) return z->key;
  192.             if(q>k) z=z->left; else {
  193.                 z=z->right;
  194.                 tmp++;
  195.                 if(z->left) tmp+=z->left->sz;
  196.             }
  197.         }
  198.     }
  199.  
  200. };
  201.  
  202. main(){
  203.     srand(0);
  204.     splay_tree t;
  205.  
  206.     vector<int> a;
  207.     for(int i=0;i<20;i++) a.push_back(i+1);
  208.     random_shuffle(a.begin(),a.end());
  209.     for(int i=0;i<10;i++) t.insert(a[i]);
  210.     t.erase(a[0]);
  211.  
  212.     t.write();
  213.  
  214.     return 0;
  215. }
Runtime error #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4tpkw9
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!