0
$\begingroup$

The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $z.p = y$ instruction does. wouldn't the algorithm work without it?

abr_insert(T, z) //z is the node that must be inserted
    {
            y = NULL;
            x = T.root;
            while(x != NULL)
            {
                    y  = x;
                    if(z.key < x.key)
                            x = x.left;
                    else
                            x = x.right;
            }
            z.p = y; //here is the instruction that I don't understand
            if(y = NULL)
                T.root = z;
            else if(z.key < y,key)
                    y.left = z;
            else
                    y.right = z;
    }
$\endgroup$
1
  • $\begingroup$ The insert algorithm may not use z.p, but it is possible that another BST method relies on the existence and correctness of the value of z.p. It look like z.p stores a pointer to the parent of the node that is to be inserted. $\endgroup$ May 8 '20 at 16:01
3
$\begingroup$

It seems like this algorithm is keeping track of parent pointers. Each node N has three fields: N.left (left child), N.right (right child), and N.p (parent). The variable y is used to keep track of the most recent parent, so when we fall off the tree (i.e. when x == NULL) we can use y as the parent of the new node z.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.