fork(1) download 
  1. /*
  2.   Copyright 2012 Marek "p2004a" Rusinowski
  3.   Splay tree
  4. */
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <ctime>
  8. #include <set>
  9.  
  10. #define left s[0]
  11. #define right s[1]
  12.  
  13. template <class T> class Splay {
  14.   class node;
  15.   node *root;
  16.  
  17.  public:
  18.   Splay() : root(NULL) {}
  19.  
  20.   ~Splay() {
  21.     if (root) delete root;
  22.   }
  23.  
  24.   void insert(const T &value) {
  25.     root = root ? root->insert(value) : new node(value, NULL);
  26.   }
  27.  
  28.   void erase(const T &value) {
  29.     if (root) {
  30.       root = root->find(value);
  31.       if (root->elem == value) {
  32.         node *tmp = root;
  33.         if (root->left == NULL) {
  34.           root = root->right;
  35.         } else if (root->right == NULL) {
  36.           root = root->left;  
  37.         } else {
  38.           root = root->left;
  39.           while (root->right != NULL) { 
  40.             root = root->right->rotate();
  41.           }
  42.           root->right = tmp->right;
  43.           root->right->parent = root;
  44.         }
  45.         root->parent = NULL;
  46.         tmp->left = tmp->right = NULL;
  47.         delete tmp;
  48.       }
  49.     }
  50.   }
  51.  
  52.   bool find(const T &value) {
  53.     if (root) {
  54.       root = root->find(value);
  55.       if (root->elem == value) return true;
  56.     }
  57.     return false;
  58.   }
  59. };
  60.  
  61. template <class T> class Splay<T>::node {
  62.   node *s[2];
  63.   node *parent;
  64.   T elem;
  65.  
  66.   /* return true if i'm right son or false if i'm left son */
  67.   bool direction() const {
  68.     return this->parent->right == this ? true : false;
  69.   }
  70.  
  71.  public:
  72.   node(T value, node *par) : parent(par) {
  73.     this->elem = value;
  74.     this->right = this->left = NULL;
  75.   }
  76.  
  77.   ~node() {
  78.     if (this->left) delete this->left;
  79.     if (this->right) delete this->right;
  80.   }
  81.  
  82.   /* my parent become my son, and my son became my grandson */
  83.   node *rotate() {
  84.     bool dir = this->direction();
  85.     node *q = this->s[!dir];
  86.     node *p = this->parent;
  87.     // setting my parent as my parent parent
  88.     this->parent = p->parent;
  89.     // if i'm not root, change my new parent son from my old parent to me
  90.     if (this->parent != NULL) {
  91.       this->parent->s[p->direction()] = this;
  92.     }
  93.     // setting me as my parent and my parent as my son
  94.     this->s[!dir] = p;
  95.     p->parent = this;
  96.     // setting my old son as my old parent son
  97.     p->s[dir] = q;
  98.     // if my old son exist, set his parent to my old parent (now my son)
  99.     if (q != NULL) {
  100.       q->parent = p;
  101.     }
  102.     return this;
  103.   }
  104.  
  105.   node *splay() {
  106.     while (this->parent != NULL) {
  107.       if (this->parent->parent == NULL) { // my parent is a root - Zig
  108.         this->rotate();
  109.       } else if (this->direction() == this->parent->direction()) { // Zig-Zig
  110.         this->parent->rotate();
  111.         this->rotate();
  112.       } else { // Zig-Zag
  113.         this->rotate();
  114.         this->rotate();
  115.       }
  116.     }
  117.     return this;
  118.   }
  119.  
  120.   node *insert(const T &value) {
  121.     if (value == this->elem) {
  122.       return this->splay();
  123.     } else {
  124.       bool dir = value > this->elem;
  125.       if (this->s[dir]) {
  126.         return this->s[dir]->insert(value);
  127.       } else {
  128.         this->s[dir] = new node(value, this);
  129.         return this->s[dir]->splay();
  130.       }
  131.     }
  132.   }
  133.  
  134.   node *find(const T &value) {
  135.     if (value < this->elem && this->left) {
  136.       return this->left->find(value);
  137.     } else if (value > this->elem && this->right) {
  138.       return this->right->find(value);
  139.     } else {
  140.       return this->splay();
  141.     }
  142.   }
  143.  
  144.   friend class Splay<T>;
  145. };
  146.  
  147. inline int los(int a, int b) {
  148.   return rand() % (b - a + 1) + a;
  149. }
  150.  
  151. int main() {
  152.   srand(time(NULL));
  153.   Splay<int> tree1;
  154.   std::set<int> tree2;
  155.   for (int i = 0; i < 1000000; ++i) {
  156.     int losowa = los(1, 1000);
  157.     switch(los(1, 3)) {
  158.       case 1: {
  159.         tree1.insert(losowa);
  160.         tree2.insert(losowa);
  161.         break;
  162.       }
  163.       case 2: {
  164.         tree1.erase(losowa);
  165.         tree2.erase(losowa);
  166.         break;
  167.       }
  168.       case 3: {
  169.         if (tree1.find(losowa) != (tree2.find(losowa) != tree2.end())) {
  170.           printf("something went wrong...\n");
  171.           return 1;
  172.         }
  173.         break;
  174.       }
  175.     }
  176.   }
  177.   return 0;
  178. }
  179.  
Success #stdin #stdout 0.42s 2812KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/FaJgC
Splay tree
language:
C++ (gcc 8.3)
created:
12 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!