CIS-3012 Homework #5: Splay Trees

Due: Friday, December 1, 2023

Reading: The Splay Trees slides might be useful references, particularly the slides showing the rotation transformations and the Zig-Zag and Zig-Zig transformations. The Wikipedia page on Splay Trees contains some useful information and other diagrams. It even has a C++ implementation that you might find interesting. Be advised that the implementation on Wikipedia does not meet all of my requirements; do not copy it.

The Smart Pointers slides might also be useful. Chapter 12 in the primary text also discusses smart pointers. Josuttis's book on the C++ Standard Library discusses smart pointers, including weak pointers in Chapter 5. Unfortunately, the only link is to the start of the chapter, so you have to scroll down to section 5.2 manually for the smart pointer information. On the other hand, Josuttis discusses pairs and tuples at the beginning of the chapter, which might also be interesting to you. Be aware that Josuttis's book only covers C++ 2011. Newer standards may have additional features.

Part 1

The attached file, homework-05.zip, contains the partially implemented header SplayTree.hpp, a test program, and a Makefile. For this assignment, you should only have to edit the header. If you feel a need to edit the test program or Makefile, let me know, so I can apply any corrections to the primary copy.

The short version of what you need to do is this: complete the methods in SplayTree.hpp marked with "Finish Me!" This includes the insert and find methods, the iterator operator++ and operator-- methods, and the necessary supporting methods (rotate_left, rotate_right, and splay).

The steps below describe my recommended approach for completing this assignment. The intention is for you to complete and test parts of the assignment incrementally rather than all at once. Finding and fixing problems in a limited part of the entire job is much easier than trying to get everything working at the same time. That said, it is not necessary that you follow this approach.

Start by implementing a basic binary search tree insert in the insert method. Do not worry about the splaying yet. The "initialization list check" in the test program only checks the binary search tree properties and not the splaying, so after this part that test should pass (as opposed to, for example, throwing an exception).
Study my provided implementation of rotate_left and make sure you understand how it works. Take note, particularly, of how the smart pointers are handled. You might find the diagram on the rotations in the Splay Trees slides helpful. The Smart Pointers slides might also be helpful. Note that the names chosen in the code for nodes x and y match those used in the diagram in the Splay Trees slides.
Implement rotate_right based on the rotate_left code. It should be approximately a "mirror image" of rotate_left, but be sure you understand what is happening, so you don't make any mistakes.
Implement the splay method following the pseudocode in the file. This method makes heavy use of the rotate methods. Modify your insert method to call splay at the appropriate times. After this step the "insert check" in the test program should pass, but you will see an exception about a missing implementation of find.
Implement find using the usual method for binary search trees, but be sure to call splay on the node found. After this step the "find check" in the test program should pass, but you will see an exception about a missing implementation of operator++ in the iterator class.
Implement operator++ in the iterator class following the provided pseudocode. After this step you will see an exception from the test program about a missing implementation of operator-- in the iterator class.
Implement operator-- in the iterator class following the rough pseudocode. After this step the test program should execute successfully. You are done!

Submission

Submit your modified SplayTree.hpp file to Canvas. You do not need to submit the other files unless you also modified them. However, let me know if you plan to submit a modified test program or Makefile.