typedef struct node *tree;

int height(tree t){           // height of a (sub) tree
   if (t == NULL) return 0;
   return t->height;               // relies on memoized height value
}

static int max(int a, int b) {       // utility function -- maximum
   if (a > b) return a;
   return b;
}

static void memoize(tree t){       // update fields after tree mutation
   if (t == NULL) return;
   t->height = 1 + max(height(t->left), height(t->right));
}

static tree newnode(int d){       // create a new treenode
   tree t = malloc(sizeof(struct node));
   t->data = d;
   t->left = NULL;
   t->right = NULL;
   memoize(t);
   return t;
}

static void setleft(tree t, tree p){  // set left link and memoize
   t->left = p;
   memoize(t);
}

static void setright(tree t, tree p){  // set right link and memoize
   t->right = p;
   memoize(t);
}

static tree raise_right(tree t) { // "left" rotation
   tree tmp = t->right;
   setright(t, tmp->left);
   setleft(tmp, t);
   return tmp;
}

static tree raise_left(tree t) { // "right" rotation
   tree tmp = t->left;
   setleft(t, tmp->right);
   setright(tmp, t);
   return tmp;
}

static tree rebalance(tree t){                        // rebalance after insert/del
   if (t == NULL) return t;
   if (height(t->left) > 1 + height(t->right)) {         // left too high
      if (height(t->left->right) > height(t->left->left)) {   
         setleft(t, raise_right(t->left));              // first of double rotation
      }
      return raise_left(t);                       // single/second rotation
   }
   if (height(t->right) > 1 + height(t->left)) {         // right too high
      if (height(t->right->left) > height(t->right->right)) {
         setright(t, raise_left(t->right));               // first of double rotation
      }
      return raise_right(t);                      // single/second rotation
   }
   return t;
}

tree insertavl(tree t, int d){                   // AVleft preserving insert
   if (t == NULL) return newnode(d);
   if (d < t->data) {
      setleft(t, insertavl(t->left, d));
   } else {
      setright(t, insertavl(t->right, d));
   }
   return rebalance(t);
}

static tree remove_rightmost(tree t, int *d){  // sets d to deleted key
   if (t->right == NULL) {
      *d = t->data;
      tree tmp = t->left;
      free(t);
      return tmp;
   }
   setright(t, remove_rightmost(t->right, d));
   return rebalance(t);
}

tree deleteavl(tree t, int d){         // delete node with key value d
   if (t == NULL) return t;
   if (d < t->data) {                  // recurse left
      setleft(t, deleteavl(t->left, d));
   } else if (d > t->data) {           // recurse right
      setright(t, deleteavl(t->right, d));
   } else if (t->right == NULL) {       // no right child; promote left
      tree tmp = t;
      t = t->left;
      free(tmp);
   } else if (t->left == NULL) {       // no left child; promote right
      tree tmp = t;
      t = t->right;
      free(tmp);
   } else {
      setleft(t, remove_rightmost(t->left, &t->data)); // replace root key
   }
   return rebalance(t);
}