Tree insertRandom(Tree t, Item it)
{
   if (t == NULL) return newNode(it);

   int chance = rand() % (size(t)+1);
   if (chance < K) return insertAtRoot(t, it);
   int diff = cmp(key(it), key(t->value));
   if (diff == 0)
      t->value = it;
   else if (diff < 0)
      t->left = insert(t->left, it);
   else if (diff > 0)
      t->right = insert(t->right, it);
   t->nnodes = count(t);
   return t;
}