advanced data structures and implementation void removeconst comparable if!containsx return/item not founddo nothing /if is foundit will be splayed to the root by contains binarynode *newtreeifroot->left =nullnode newtree root->rightelse /find the maximum in the left subtree /splay it to the rootand then attach right child newtree root->leftsplayxnewtree )newtree->right root->rightdelete rootroot newtreefigure top-down deletion procedure and makeempty duplicate instead of reinserting xwe preserve newnode for future insertion and return immediately if the new root contains value larger than xthen the new root and its right subtree become right subtree of newnodeand root' left subtree becomes the left subtree of newnode similar logic applies if root' new root contains value smaller than in either casenewnode becomes the new root in we showed that deletion in splay trees is easybecause splay will place the target of the deletion at the root we close by showing the deletion routine in figure it is indeed rare that deletion procedure is shorter than the corresponding insertion procedure figure also shows makeempty simple recursive postorder traversal to reclaim the tree nodes is unsafe because splay tree may well be unbalancedeven while giving good performance in that casethe recursion could run out of stack space we use simple alternative that is still ( (though that is far from obvioussimilar considerations are required for operator red-black trees historically popular alternative to the avl tree is the red-black tree operations on red-black trees take (log ntime in the worst caseandas we will seea careful nonrecursive implementation (for insertioncan be done relatively effortlessly (compared with avl trees