Guest User

AVL testing

a guest
Feb 15th, 2015
1,029
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
  3.  * Date: 2015.01.24
  4.  */
  5.  
  6. /** Template */
  7.  
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  13.  
  14. const int MAX_MEM = (int)1e5;
  15.  
  16. int mpos;
  17. char mem[MAX_MEM];
  18.  
  19. inline void * operator new ( size_t n ) {
  20.   char *res = mem + mpos;
  21.   mpos += n;
  22.   assert(mpos <= MAX_MEM);
  23.   return (void *)res;
  24. }
  25.  
  26. inline void operator delete ( void * ) { }
  27. inline void * operator new [] ( size_t ) { assert(0); }
  28. inline void operator delete [] ( void * ) { assert(0); }
  29.  
  30. /** Main part */
  31.  
  32. struct node {
  33.   static node *null;
  34.   int x, h;
  35.   node *l, *r;
  36.  
  37.   void calc() { h = 1 + max(l->h, r->h); }
  38.   node() { l = r = this, h = 0, x = 0; }
  39.   node( int x, node* l = null, node* r = null ) : x(x), l(l), r(r) { calc(); }
  40. };
  41. node* node::null = new node();
  42.  
  43. node* rot_left( node* t ) { // (t->l, t)
  44.   return new node(t->l->x, t->l->l, new node(t->x, t->l->r, t->r));
  45. }
  46. node* rot_right( node* t ) { // (t, t->r)
  47.   return new node(t->r->x, new node(t->x, t->l, t->r->l), t->r->r);
  48. }
  49.  
  50. void add( node* &t, int x ) {
  51.   if (t == node::null) {
  52.     t = new node(x);
  53.     return;
  54.   }
  55.   if (x < t->x) {
  56.     add(t->l, x);
  57.     if (t->l->h > t->r->h + 1) {
  58.       if (t->l->r->h > t->l->l->h)
  59.         t->l = rot_right(t->l);
  60.       t = rot_left(t);
  61.     }
  62.   } else {
  63.     add(t->r, x);
  64.     if (t->r->h > t->l->h + 1) {
  65.       if (t->r->l->h > t->r->r->h)
  66.         t->r = rot_left(t->r);
  67.       t = rot_right(t);
  68.     }
  69.   }
  70.   t->calc();
  71. }
  72.  
  73. void add_slow( node* &t, int x ) {
  74.   if (t == node::null) {
  75.     t = new node(x);
  76.     return;
  77.   }
  78.   if (x < t->x) {
  79.     add_slow(t->l, x);
  80.     if (t->l->h > t->r->h + 1)
  81.       t = rot_left(t);
  82.   } else {
  83.     add_slow(t->r, x);
  84.     if (t->r->h > t->l->h + 1)
  85.       t = rot_right(t);
  86.   }
  87.   t->calc();
  88. }
  89.  
  90. int main() {
  91.   int T = 1e6;
  92.   for (int N = 5; N <= 25; N++) {
  93.     int ma = 0, p[N];
  94.     forn(i, N)
  95.       p[i] = i;
  96.  
  97.     forn(_, T) {
  98.       mpos = 0;
  99.       node *a = node::null;
  100.       node *b = node::null;
  101.       random_shuffle(p, p + N);
  102.       forn(i, N) {
  103.         add(b, p[i]);
  104.         add_slow(a, p[i]);
  105.       }
  106.       ma = max(ma, a->h - b->h);
  107.     }
  108.     printf("n = %2d : max diff = %d\n", N, ma);
  109.   }
  110.   return 0;
  111. }
RAW Paste Data