Data Structures: Assignment 2
My PlayStation Friends
SP2, 2017
James Baumeister
March 2017
1 Introduction
Needing a way to manage all your PlayStation friends, you decide to build a
back-end system for adding, removing and maintaining them. The idea is to
organise your friends so you can search for individuals, search for players who
have the same games as you, determine rankings, and view player information
and trophies. At the same time, you'd like your search queries to be fast,
ruling out basic structures like arrays and linked lists. Deciding that the most
important factor for ordering your friends is level, you build a binary search tree
(BST) structure, using the level (actually a function on level, see section 4) as
the key.
In this assignment we will build a BST structure, with each node repre-
senting a PlayStation friend. Each friend node contains information about that
player, including their username, level and date of birth, along with attached
data structures for their games (single linked-list) and trophies (ArrayList). In
accordance with the rules of BSTs, each friend has a parent node and two child
nodes, left and right. From any one node, all nodes to the left are less (lower
level) and all nodes to the right are greater (higher level). Due to this, searching
for higher or lower-levelled players is, on average, a
O
(log
n
) process.
This assignment consists of a number of parts. In part A you will setup the
basic class structure, ensuring that the test suite is able to run without error. In
part B you will implement the basic structures needed by
User
to hold multiple
Trophy
and
Game
objects. In part C you will create your BST-based friend
database. Finally, in part D you will improve the eciency of your tree by
implementing AVL balancing. You are free to add your own methods and elds
to any of the classes in the
Database
package, but do not change any existing
method prototypes or eld de nitions. A testing suite has been provided for you
to test the functionality of your classes. These tests will be used to mark your
assignment, but with altered values. This means that you cannot hard-code
answers to pass the tests. It is suggested that you complete the assignment in
1
the order outlined in the following sections. Many of the later-stage classes rely
on the correct implementation of their dependencies.
1.1 Importing into eclipse
The Assignment has been provided as an eclipse project. You just need to
import the project into an existing workspace. See Figure 1 for a visual guide.
Make sure that your Java JDK has been set, as well as the two jar les that you
need for junit to function. This can be found in Project
!
Properties
!
Java
Build Path
!
Libraries. The jar les have been provided within the project;
there is no need to download any other version and doing so may impact the
testing environment.
Figure 1: Importing the project through File
!
Import
2 Part A
If you run the testing suite, you will be lovingly presented with many errors.
Your rst task is to complete the class implementations that the tests expect
(including instance variables and basic methods) to remove all errors from the
testing classes.
2
Table 6:
avlTester
mark allocation
Test
Marks
avlStage1 6
avlStage2 5
avlStage3 5
Total:
16
14