Оптимизация декартова дерева по памяти, о которой знают не все.

Фишка в процедуре erase() (находит вершину с заданным ключем и удаляет ее). На 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);
}

Добавим капельку магии:

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);
}

Ну вот, теперь вершина действительно удаляется, тем самым мы экономим немного памяти.

UPD: добавлено в https://cp-algorithms.com/data_structures/treap.html