I was reading about Treap data structure on [cp-algorithms](https://cp-algorithms.com/data_structures/treap.html).↵
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?↵
↵
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?↵
↵
