AVL testing

/**
 * Author: Sergey Kopeliovich ([email protected])
 * Date: 2015.01.24
 */

/** Template */

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

const int MAX_MEM = (int)1e5;

int mpos;
char mem[MAX_MEM];

inline void * operator new ( size_t n ) {
  char *res = mem + mpos;
  mpos += n;
  assert(mpos <= MAX_MEM);
  return (void *)res;
}

inline void operator delete ( void * ) { }
inline void * operator new [] ( size_t ) { assert(0); }
inline void operator delete [] ( void * ) { assert(0); }

/** Main part */

struct node {
  static node *null;
  int x, h;
  node *l, *r;

  void calc() { h = 1 + max(l->h, r->h); }
  node() { l = r = this, h = 0, x = 0; }
  node( int x, node* l = null, node* r = null ) : x(x), l(l), r(r) { calc(); }
};
node* node::null = new node();

node* rot_left( node* t ) { // (t->l, t)
  return new node(t->l->x, t->l->l, new node(t->x, t->l->r, t->r));
}
node* rot_right( node* t ) { // (t, t->r)
  return new node(t->r->x, new node(t->x, t->l, t->r->l), t->r->r);
}

void add( node* &t, int x ) {
  if (t == node::null) {
    t = new node(x);
    return;
  }
  if (x < t->x) {
    add(t->l, x);
    if (t->l->h > t->r->h + 1) {
      if (t->l->r->h > t->l->l->h)
        t->l = rot_right(t->l);
      t = rot_left(t);
    }
  } else {
    add(t->r, x);
    if (t->r->h > t->l->h + 1) {
      if (t->r->l->h > t->r->r->h)
        t->r = rot_left(t->r);
      t = rot_right(t);
    }
  }
  t->calc();
}

void add_slow( node* &t, int x ) {
  if (t == node::null) {
    t = new node(x);
    return;
  }
  if (x < t->x) {
    add_slow(t->l, x);
    if (t->l->h > t->r->h + 1)
      t = rot_left(t);
  } else {
    add_slow(t->r, x);
    if (t->r->h > t->l->h + 1)
      t = rot_right(t);
  }
  t->calc();
}

int main() {
  int T = 1e6;
  for (int N = 5; N <= 25; N++) {
    int ma = 0, p[N];
    forn(i, N)
      p[i] = i;

    forn(_, T) {
      mpos = 0;
      node *a = node::null;
      node *b = node::null;
      random_shuffle(p, p + N);
      forn(i, N) {
        add(b, p[i]);
        add_slow(a, p[i]);
      }
      ma = max(ma, a->h - b->h);
    }
    printf("n = %2d : max diff = %d\n", N, ma);
  }
  return 0;
}