I came across this implementation of treap split function
void split(pnode root, int key, pnode &l, pnode &r){
if(!root){
l = NULL;
r = NULL;
}
else if(key < root->key){
split(root->l,key,l,root->l);
r = root;
}
else{
split(root->r,key,root->r,r);
l = root;
}
}
where pnode is pointer to node. I have a difficulty in understanding the call to split function. if key < root->key, I understood that we need to make root as the root of the right subtree so r = root. And we need to split left child. So split(root->l,key,?,?) the doubt is why we pass l as left pointer and root->l as right pointer. Thank you
split operation basically divides the current treap into two treaps such that left treap contains all the elements with keys less than "key" and right treap with all the elements having key greater than "key".... so according to your code if first condition gets satisfied(keykey) then... r=root... now since the right subtree of root always contain elements with key greater than key of root(remember it has to be a BST) so we are left with two pointer "l"(that you have passed as argument) and "root->l"(left subtree of root) so basically the question again boils down to split the treap into such that left will be rooted by "l" and contains key less than your specified "key" and right treap will be pointed by root->l and contains keys greater than "key"..**but remember the treap to be splitted here is left subtree of original treap because you are done with its right subtree and now wants check the same in left subtree ** now if again you find the key of root(remember root is now root->l) less than "key" then you will again do ** r=root ** but r is now root->l(remember previous recursion) and if that does not holds true then second last condition gets executed and l=root(root is now root->l )...let me suppose l=root got executed then what should our current treap be look like....**its right subtree is pointed by "r"(that you have passed during function call) and left subtree of our original treap is pointed by "l"(that again you have passed during function call) ... so now we are left with right subtree of left child of current node and two pointers which are not being provided any reference and these pointers are root->l and root-l->r ** (try to do it using pen and paper its not that tough actually everytime we make use of fact that if current node contains key greater than "key" then we donot need to check its right subtree because all those will contain key greater than their parent and same is the case with left subtree if current element contains key less than that of "key" then all elements to its left will contain key less than their parent and everytime we are left with two pointer .....we keep on splitting these treaps till we reach leaf node..) though it is not that clear but i hope it helps...
I got it somewhat, thanks. Could you tell what arguments do we call the initial split function with. Say i want to split at key = 5.
the only thing you have before splitting is head node or you can say node that points to the treap which is to be splitted ,now you declare two pointers denoting left subtree and rightsubtree(before call they are NULL pointers)....now split function is called and these two newly declared pointers "l" and "r" are passed to it along with "key" and "head_node" pointer that points to treap before splitting(REMEMBER "l" and "r" HAVE TO BE PASSED BY REFERENCE) because you want those changes made to original treap being reflected in "l" and "r" and the only way to achieve this is to either pass their address and use pointer to pointer or pass them by reference....after that split function will adjust some of the links and you will finally have left treap pointed by "l" and right treap pointed by "r".