Tree insertAtRoot(Tree t, Item it)
{ 
   if (t == NULL) return newNode(item);
   int diff = cmp(key(it), key(t->value));
   if (diff == 0)
      t->value = it;
   else if (diff < 0) {
      t->left = insertAtRoot(t->left, it);
      t = rotateR(t);
   }
   else if (diff > 0) {
      t->right = insertAtRoot(t->right, it);
      t = rotateL(t);
   }
   return t;
}