set the predecessor's pointer ( the right pointer in this case)
setright(predecessor,p);