Help in Treap split function

Revision en1, by purple_dreams, 2017-06-28 01:48:55

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English purple_dreams 2017-06-28 01:48:55 742 Initial revision (published)