Description
1. Project Overview
In this project, you will implement a self-adjusting binary search tree called the splay tree. It carries out selfoptimization based on the heuristic that recently accessed elements are quick to access again. With n nodes,
the tree has the amortized running time of O(logn) per operation. (This is the time averaged over a worst-case
sequence of operations.) Next, you will use a splay tree to simulate customer rental and return transactions at
a video store.
The class SplayTree implements the data structure of splay tree. The class Video represents a video with rental
information, while the class VideoStore makes use of a SplayTree object to simulate video transactions. You
also need to implement the class Transactions to simulate video rental and return activities. To these four
classes you may add new instance variables and methods. You cannot, however, rename or remove any
existing ones, or change any from public to protected (or private), or vice versa.
2. Splay Tree
The SplayTree class has been completed for you. You do not need to implement SplayTree.
If you would like to learn more about the inner workings of splay trees, please refer to the provided code, the
included javadocs, and the attached splayTrees.pptx. A description of parts of the the classes functionality
follows.
The splay tree is implemented by the following generic class:
public class SplayTree
A node in the tree is fully implemented by the public class Node within SplayTree.
2.1 Tree Construction, Methods, and Iterator
Three constructors are provided for the SplayTree class:
public SplayTree()
public SplayTree(E data)
public SplayTree(SplayTree
The first constructor creates an empty tree (with null root).
The second constructor merely creates a tree root to store given data. The rest of the tree needs to be
constructed by repeatedly calling the following method which performs a binary search tree addition:
public boolean addBST(E data)
For efficiency of tree initialization, the method does not splay at the newly created node.
The third constructor copies over the structure of an existing splay tree.
The class has a private iterator class SplayTreeIterator. No iterator method splays at a node.
2.2 Tree Display
The toString() method has been overridden to display the configuration of the splay tree under the following
rules:
Every node of the tree occupies a separate line with its data written out only. (Assume that the toString()
method for the data class E has been properly overridden.)
The data stored at a node at depth d is printed with indentation 4d (i.e., preceded by 4d blanks).
Starting at the root (at depth 0), it displays the nodes in a preorder traversal. More specifically, suppose
a node n is shown at line l. Then, starting at line l+1 , it
recursively prints all nodes in the left subtree (if any) of n;
recursively prints all nodes in the right subtree (if any) of n.
If a node has a left child but no right child, prints its right child as null.
If a node has a right child but no left child, prints its left child as null.
If a node is a leaf, it is printed with no further recursion.
The toString() method for the class E is assumed to be properly overridden. Shown next is a splay tree with 12
nodes to store integers (E instantiated as int). What follows is the expected output that would be generated
from calling the toString() and System.out.println().
50
30
25
10
null
20
null
35
31
37
55
53
60
null
62
3. Video Store
The class VideoStore simulates rental and return transactions at a video store. Videos are objects of the Video
class such that a single Video object represents all video copies of the same film.
public class Video implements Comparable
Transaction: 1
Film to rent: Brokeback Mountain
Transaction: 3
Film to return: Slumdog Millionaire (2)
Transaction: 1
Film to rent: The Silence of the Lambs
Film The Silence of the Lambs is not in inventory
Transaction: 1
Film to rent: Singin’ in the Rain (2)
Transaction: 4
Video file (return): videoList3.txt
Transaction: 5
Rented films:
Brokeback Mountain (1)
Singin’ in the Rain (2)
Slumdog Millionaire (1)
The Godfather (1)
Films remaining in inventory:
A Streetcar Named Desire (1)
Forrest Gump (1)
Psycho (1)
Slumdog Millionaire (4)
Taxi Driver (1)
Transaction: 6
Your code needs to print out text messages in the same format for user interactions. Please note the
following:
To request for the rental or return of a single video, simply enter the film title. You may also enter “(1)”
after the title though it is redundant.
To request for multiple copies of the same film, enter the number of copies within a pair of parentheses
after the film title.
The transaction numbered 5 in the above scenario lists rented films and unrented films in the
alphabetical order decided by the compareTo() method for String objects.
5. Submission
Write your classes in the edu.iastate.cs228.hw5 package. Turn in the zip file not your class files. Please follow
the guideline posted under Documents & Links on Canvas.
You are not required to submit any JUnit test cases. Nevertheless, you are encouraged to write JUnit tests for
your code. Since these tests will not be submitted, feel free to share them with other students.
Include the Javadoc tag @author in every class source file you have made changes to. Your zip file should be
named Firstname_Lastname_HW5.zip.
