The trick is in the procedure that finds a vertex with a given key and deletes it. There is a code on the e-maxx.ru:
void erase (pitem & t, int key) {
if (t->key == key)
merge (t, t->l, t->r);
else
erase (key < t->key ? t->l : t->r, key);
}
Let's add some magic:
void erase (pitem & t, int key) {
if (t->key == key){
pitem to_del = t;
merge (t, t->l, t->r);
delete to_del;
}
else
erase (key < t->key ? t->l : t->r, key);
}
Now the vertex is really deleted, thus we save a lot of memory.
UPD: added into https://cp-algorithms.com/data_structures/treap.html