typedef struct tree_node Tree;
struct tree_node {
    Tree * left, * right;
    int item;
};

Tree * splay (int i, Tree * t) {
/* Simple top down splay, not requiring i to be in the tree t.  */
/* What it does is described above.                             */
    Tree N, *l, *r, *y;
    if (t == NULL) return t;
    N.left = N.right = NULL;
    l = r = &N;

    for (;;) {
    	if (i < t->item) {
    	    if (t->left == NULL) break;
    	    if (i < t->left->item) {
        		y = t->left;                           /* rotate right */
        		t->left = y->right;
        		y->right = t;
        		t = y;
        		if (t->left == NULL) break;
    	    }
    	    r->left = t;                               /* link right */
    	    r = t;
    	    t = t->left;
    	} else if (i > t->item) {
    	    if (t->right == NULL) break;
    	    if (i > t->right->item) {
        		y = t->right;                          /* rotate left */
        		t->right = y->left;
        		y->left = t;
        		t = y;
        		if (t->right == NULL) break;
    	    }
    	    l->right = t;                              /* link left */
    	    l = t;
    	    t = t->right;
    	} else {
    	    break;
    	}
    }
    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;
    return t;
}