Prepare an implementation of splay trees that uses bottom-up splaying as described in this chapter and another

Question:

Prepare an implementation of splay trees that uses bottom-up splaying as described in this chapter and another that uses top-down splaying as described in Exercise C-10.23. Perform extensive experimental studies to see which implementation is better in practice, if any.


Data from in Exercise C-10.23

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.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Data Structures And Algorithms In C++

ISBN: 9780470383278

2nd Edition

Authors: Michael T. Goodrich, Roberto Tamassia, David M. Mount

Question Posted: