Description
1. Project Overview
In this project, you will implement a self-adjusting binary search tree called the splay tree. It carries out self-optimization based on the heuristic that recently accessed elements are quick to access again. With 𝑛 nodes, the tree has the amortized running time of 𝑂(log 𝑛) 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
For an introduction to splay trees, we refer to the lecture notes splayTrees.pptx posted on Canvas under the Apr 12 folder. The splay tree is implemented by the following generic class: public class SplayTree> extends AbstractSet 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 tree) • 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. Tree operations shall be implemented following their descriptions in the lecture notes. Also, refer to their javadocs for extra requirements if any. The class has a private iterator class SplayTreeIterator. No iterator method splays at a node.
2.2 Tree Display
You need to override the toString() method 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 𝑑 is printed with indentation 4𝑑 (i.e., preceded by 4𝑑 blanks). • Start at the root (at depth 0) and display the nodes in a preorder traversal. More specifically, suppose a node 𝑛 is shown at line 𝑙. Then, starting at line 𝑙 + 1, – recursively print all nodes in the left subtree (if any) of 𝑛; – recursively print all nodes in the right subtree (if any) of 𝑛. • If a node has a left child but no right child, print its right child as null. • If a node has a right child but no left child, print its left child as null. • If a node is a leaf, print it 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
