figure simplified top-down zig-zag identical to the zig case this would seem advantageous because testing for host of cases is time-consuming the disadvantage is that by descending only one levelwe have more iterations in the splaying procedure once we have performed the final splaying stepfigure shows how lrand the middle tree are arranged to form single tree note carefully that the result is different from bottom-up splaying the crucial fact is that the (log namortized bound is preserved (exercise an example of the top-down splaying algorithm is shown in figure we attempt to access in the tree the first step is zig-zag in accordance with ( symmetric version offigure we bring the subtree rooted at to the root of the middle tree and attach and its left subtree to next we have zig-zig is elevated to the root of the middle treeand rotation between and is performedwith the resulting subtree being attached to the search for then results in terminal zig the middle tree' new root is and and its left subtree are attached as right child of ' largest node the reassemblyin accordance with figure terminates the splay step we will use header with left and right links to eventually contain the roots of the left and right trees since these trees are initially emptya header is used to correspond to the min or max node of the right or left treerespectivelyin this initial state this way the code can avoid checking for empty trees the first time the left tree becomes nonemptythe right pointer will get initialized and will not change in the futurethus it will contain the root of the left tree at the end of the top-down search similarlythe left pointer will eventually contain the root of the right tree the splaytree class interfacealong with its constructor and destructorare shown in figure the constructor allocates the nullnode sentinel we use the sentinel nullnode to represent logically nullptr pointerthe destructor deletes it after calling makeempty figure final arrangement for top-down splaying