Recently, I started learning about Treaps. I watched the Algorithms Live video on youtube and read the cp-algorithms blog on Treaps, however the way they implement the treap is different. I tried reading the code on cp-algorithms and i cannot understand how the split operation works.
void split (pitem t, int key, pitem & l, pitem & r) {
if (!t)
l = r = NULL;
else if (key < t->key)
split (t->l, key, l, t->l), r = t;
else
split (t->r, key, t->r, r), l = t;
}
I don't understand how the references to l and r works and how the values are assigned. Is there an easy way to understand how it works?
Thanks in advance. Here is a link to the full tutorial: https://cp-algorithms.com/data_structures/treap.html