I was reading about Treap data structure on cp-algorithms. I looked at split function and I found out that new node's left child becomes the element with highest possible priority in the left sub-tree and smaller key, and right child becomes the element with highest possible priority in the right sub-tree and greater key. According to the code:
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;
}
void insert (pitem & t, pitem it) {
if (!t)
t = it;
else if (it->prior > t->prior)
split (t, it->key, it->l, it->r), t = it;
else
insert (it->key < t->key ? t->l : t->r, it);
}
We are going to the leaf node and going back again. For example if I have the tree shown below and I want insert new element I will do following operations:
Isn't it better to just return back after we find out left and right child for the new node, without going to the leaf?