advanced data structures and implementation figure top-down splay rotationszigzig-zigand zig-zag xthat is the root of its subtreethis is represented in our diagrams as the "middletree tree stores nodes in the tree that are less than xbut not in ' subtreesimilarly tree stores nodes in the tree that are larger than xbut not in ' subtree initiallyx is the root of tand and are empty if the rotation should be zigthen the tree rooted at becomes the new root of the middle tree and subtree are attached as left child of the smallest item in rx' left child is logically made nullptr as resultx is the new smallest item in note carefully that does not have to be leaf for the zig case to apply if we are searching for an item that is smaller than yand has no left child (but does have right child)then the zig case will apply for the zig-zig casewe have similar dissection the crucial point is that rotation between and is performed the zig-zag case brings the bottom node to the top in the middle treeand attaches subtrees and to and lrespectively note that is attached toand then becomesthe largest item in the zig-zag step can be simplified somewhat because no rotations are performed instead of making the root of the middle treewe make the root this is shown in figure this simplifies the coding because the action for the zig-zag case becomes for simplicity we don' distinguish between "nodeand the item in the node in the codethe smallest node in does not have nullptr left link because there is no need for it this means that printtree(rwill include some items that logically are not in