redblacknode *parentredblacknode *grandredblacknode *great/usual recursive stuff void reclaimmemoryredblacknode * )void printtreeredblacknode * constredblacknode cloneredblacknode const/red-black tree manipulations void handlereorientconst comparable item )redblacknode rotateconst comparable itemredblacknode *theparent )void rotatewithleftchildredblacknode )void rotatewithrightchildredblacknode )}/*construct the tree neginf is value less than or equal to all others *explicit redblacktreeconst comparable neginf nullnode new redblacknodenullnode->left nullnode->right nullnodeheader new redblacknodeneginf }header->left header->right nullnodefigure (continuedthat is red (inductivelyby the invariant we are trying to maintain)and that and are black (because we can' have two consecutive red nodesthere are two main cases firstsuppose has two black children then there are three subcaseswhich are shown in figure if also has two black childrenwe can flip the colors of xtand to maintain the invariant otherwiseone of ' children is red depending on which one it is, we can apply the rotation shown in the second and third cases of figure note carefully that this case will apply for the leafbecause nullnode is considered to be black if both children are redwe can apply either rotation as usualthere are symmetric rotations for the case when is right child that are not shown