advanced data structures and implementation insertion into the treap is simpleafter an item is added as leafwe rotate it up the treap until its priority satisfies heap order it can be shown that the expected number of rotations is less than after the item to be deleted has been foundit can be deleted by increasing its priority to and rotating it down through the path of low-priority children once it is leafit can be removed the routines in figure and figure implement these strategies using recursion nonrecursive implementation is left for the reader (exercise for deletionnote that when the node is logically leafit still has nullnode as both its left and right children consequentlyit is rotated with the right child after the rotationt is nullnodeand the left childwhich now stores the item to be deletedcan be freed note also that our implementation assumes that there are no duplicatesif this is not truethen the remove could fail (why?the treap implementation never has to worry about adjusting the priority data member one of the difficulties of the balanced tree approaches is that it is difficult to track down errors that result from failing to update balance information in the course of an operation in terms of total lines for reasonable insertion and deletion packagethe treapespecially nonrecursive implementationseems like the hands-down winner /*internal method to insert into subtree is the item to insert is the node that roots the tree set the new root of the subtree (randomnums is uniformrandom object that is data member of treap *void insertconst comparable xtreapnodet ift =nullnode new treapnodexnullnodenullnoderandomnums nextint}else ifx element insertxt->left )ift->left->priority priority rotatewithleftchildt )else ift->element insertxt->right )ift->right->priority priority rotatewithrightchildt )/else duplicatedo nothing figure treapsinsertion routine