set the predecessor's pointer ( the right pointer in this case)

setright(predecessor,p);