advanced data structures and implementation of red-black trees is the relatively low overhead required to perform insertionand the fact thatin practicerotations occur relatively infrequently an actual implementation is complicated not only by the host of possible rotations but also by the possibility that some subtrees (such as ' right subtreemight be emptyand the special case of dealing with the root (which among other thingshas no parentthuswe use two sentinel nodesone for the rootand nullnodewhich indicates nullptr pointer as it did for splay trees the root sentinel will store the key and right link to the real root because of thisthe searching and printing procedures need to be adjusted the recursive routines are trickiest figure shows how the inorder traversal is rewritten the printtree routines are straightforward the test != ->left could be written as !=nullnode howeverthere is trap in similar routine that performs the deep copy this is also shown in figure the copy constructor calls clone after other initialization is complete but in clonethe test ==nullnode does not workbecause nullnode is the target' nullnodenot the source' (that isnot rhs'sthus we use trickier test figure shows the redblacktree skeletonalong with the constructor nextfigure (page shows the routine to perform single rotation because the resultant tree must be attached to parentrotate takes the parent node as parameter rather than keeping track of the type of rotation as we descend the treewe pass item as parameter since we expect very few rotations during the insertion procedureit turns out that it is not only simplerbut actually fasterto do it this way rotate simply returns the result of performing an appropriate single rotation finallywe provide the insertion procedure in figure (on page the routine handlereorient is called when we encounter node with two red childrenand also when we insert leaf the trickiest part is the observation that double rotation is really two single rotationsand is done only when branching to (represented in the insert method by currenttakes opposite directions as we mentioned in the earlier discussioninsert must keep track of the parentgrandparentand great-grandparent as the tree is descended since these are shared with handlereorientwe make these class members note that after rotationthe values stored in the grandparent and great-grandparent are no longer correct howeverwe are assured that they will be restored by the time they are next needed top-down deletion deletion in red-black trees can also be performed top-down everything boils down to being able to delete leaf this is because to delete node that has two childrenwe replace it with the smallest node in the right subtreethat nodewhich must have at most one childis then deleted nodes with only right child can be deleted in the same mannerwhile nodes with only left child can be deleted by replacement with the largest node in the left subtreeand subsequent deletion of that node note that for red-black treeswe don' want to use the strategy of bypassing for the case of node with one child because that may connect two red nodes in the middle of the treemaking enforcement of the red-black condition difficult