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
