Dalgerok's blog

By Dalgerok, 7 years ago, translation, In English

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

  • Vote: I like it
  • -35
  • Vote: I do not like it