The standard splaying step requires two passes, one downward pass to find the node x to splay, followed by an upward pass to splay the node x . Describe a method for splaying and searching for x in...

The standard splaying step requires two passes, one downward pass to

find the node
x
to splay, followed by an upward pass to splay the node

x. Describe a method for splaying and searching for
x
in one downward

pass. Each substep now requires that you consider the next two nodes

in the path down to
x, with a possible zig substep performed at the end.

Describe how to perform the zig-zig, zig-zag, and zig steps.