COMP2014J代做、Java程序设计代写

日期：2025-04-24 10:20

Assignment 1:

Sorted Maps with AVL Trees and

Splay Trees

COMP2014J: Data Structures and Algorithms 2

Weight: 20% of final grade

Due Date: 23:59 Friday May 9th 2025

Document Version: 1.1

Introduction

This assignment is intended to give you experience of using an AVL tree and a

Splay Tree to implement a different type of data structure (a type of sorted Map

known as a Tree Map). It is also a good exercise to gain experience about how

generics, inheritance and object references work in Java.

Source code that you must start from has been posted to Brightspace in the file

Assignment1-Source.zip. This also contains the Javadoc for the classes and

interfaces provided (in the “doc” folder). Import this project into IntelliJ in the

usual way.

You must use the interfaces and data structure implementations that are

provided. Do not use any interfaces or implementations from the built-in Java

Collections Framework. If you are in doubt, ask!

Tasks

The main tasks for this assignment are:

• Create an efficient implementation of a sorted map, using an AVL Tree

to store the entries, according to the provided interfaces and base

classes.

• Create an efficient implementation of a sorted map, using a Splay Tree

to store the entries, according to the provided interfaces and base

classes.

• Develop a strategy to test if your implementations are correct.

Tree Map Implementation of ISortedMap Methods

The source code contains a skeleton implementation of a map based on an

AVL Tree (in a file called AVLTreeMap.java) and a Splay Tree (in a file called

SplayTreeMap.java) in the dsa.impl package. All of your work in this section

must be in this class and it must use the interfaces that are provided.

These classes both extend a sorted map that uses a Binary Search Tree

implementation. Your task is to replace the following methods with appropriate

implementations that include the relevant AVL and Splay Tree operations

(checking for balance, tri-node restructuring, splaying).

As you have learned in Data Structures and Algorithms 1, a Map is an ADT

contains key/value pairs (called “entries”). Keys are used to uniquely identify

values. By default, entries in a map have no particular order. The

ISortedMap<K,V> interface is provided (where K is the generic type of the keys

and V is the generic type of the values) and contains the following methods:

• public V put( K key, V value ) – add a new key/value pair to the

map. If this key was already contained in the map, the old value

associated with it is returned and the new value is stored in the map

instead. Otherwise it returns null.

• public V get( K key ) – get the value associated with the given key,

or null if that key is not contained in the map.

• public V remove( K key ) – remove the entry with the given key

from the map. Returns the value associated with that key if it was

contained in the map, or null otherwise.

If you wish, you may create other methods that help you to complete the task

(e.g. restructure(…), rightRotate(…), leftRotate(…), splay(…), etc.).

Some hints and tips

• Remember your AVLTreeMap and SplayTreeMap extends several other

classes, so you can use some of their helpful methods (e.g.

expandExternal(…), remove(…)).

• The expandExternal(…) method uses newPosition(…) to create all

position objects, so for an AVL Tree all the positions in the tree will be

AVLPosition instances (so that the height is stored). In the

SplayTreeMap, all the positions in the tree will be BTPosition instances.

• You can cast an IPosition<T> to an AVLPosition or BTPosition in the

same way as you did in previous worksheets.

• Remember, every parent/child relationship works in two directions.

Every time you change one of these references, you must change both.

• In the lectures we talk about attaching subtrees. BUT when we program

this, we notice that the subtree structure does not change at all. We just

need to put the root of the subtree in the right place.

• An AVLPosition object has a height attribute. You will need to efficiently

calculate the height of the positions in the tree when the tree changes.

Calculating the heights of all positions every time the tree changes will

be at best O(n). An efficient implementation would be at worst O(h) when

an insert(…) or remove(…) operation is called.

• The TreePrinter class has been provided, so you can print the contents

of your tree and see what it contains.

A Map that is implemented using any type of binary search tree (often called a

“Tree Map”) can be said to be a kind of sorted map, where all entries can be

accessed according to the natural ordering of their keys.

For example, consider the following key/value entries stored in a map:

{"zh", "Chinese"}, {"ga", "Irish"}, {"de", "German"}, {"en", "English"}

When iterating the keys, the order would be (i.e. in alphabetical order):

- "de", "en", "ga", "zh"

When iterating the values, the order would be (i.e. in order of their keys):

- "German", "English", "Irish", "Chinese"

When iterating the entries, the order would be the same, i.e.:

- {"de", "German"}, {"en", "English"}, {"ga", "Irish"}, {"zh", "Chinese"}

This is because the trees store use the keys to decide where to store the

entries, so an inorder traversal of the tree yields the entries in key order.

Testing the Implementations

You must also write some code to check whether your implementations are

correct. A good way to do this is to use your implementation to perform some

operations, and then check if the outcome is correct. This is best done using a

program, rather than doing it manually every time.

An example is given in the AVLTreeStructureTest class in the dsa.example

package. This performs some operations (only insert) on an AVL Tree Map. To

check if the final AVL tree is correct, it compares it with a Binary Search Tree

that has the final expected shape (I worked this out manually).

Another example is shown in the AVLTreeSpeedTest class. This performs several

operations on an AVL Tree Map and measures how quickly it runs. This is a

good way to test the efficiency of your implementation.

Mandatory Tests:

- Adjust the AVLTreeStructureTest so that all of the key operations will

be called when it is run (i.e. there are different types of trinode

restructurings, and it will be done differently at the root compared to

deeper in the tree).

- Create a similar SplayTreeStructureTest that does the same for the

SplayTreeMap implementation.

Other Tests:

Create some test classes for your implementations (called Test1, Test2, etc.).

In your tests, you should test all whether the behaviour of the methods that

you have implemented work correctly in different circumstances (e.g. inserting

a new entry with a new key, replacing the value for an existing key, etc.).

Each test class must have a comment to explain the purpose of the test and

what the outcome was.

Submission

• This is an individual programming assignment. Therefore, all code

must be written by yourself. There is some advice below about avoiding

plagiarism in programming assignments.

• All code should be well-formatted and well-commented to describe what

it is trying to do.

• If you write code outside the AVLTreeMap.java, SplayTreeMap.java

and test files (AVLTreeStructureTest.java,

SplayTreeStructureTest.java, Test1.java, Test2.java, etc.), it will

not be noticed when grading. Write code only in these files.

• Submit a single .zip file to Brightspace.

o This should include only the files you have written code in. Do

not submit your entire IntelliJ project.

Grading

The following grading scheme will be used to grade the assignment:

Item Weight

Correct and efficient implementation of

AVL Tree Map operations

30%

Correct and efficient implementation of

Splay Tree Map operations

30%

Testing of AVL Tree Map 15%

Testing of Splay Tree Map 15%

Code clarity, organisation, commenting 10%

Plagiarism in Programming Assignments

• This is an individual assignment, not a group assignment.

• This means that you must submit your own work only.

If you submit somebody else's work (including AI-generated code) and

pretend that you wrote it, this is plagiarism.

• Plagiarism is a very serious academic offence.

Why should you not plagiarise?

• You don't learn anything!

• It is unfair to other students who work hard to write their own solutions.

• It's cheating! There are very serious punishments for students who

plagiarise. The UCD policy on plagiarism can be found online1.

- A student found to have plagiarised can be exclude from their

programme and not allowed to graduate.

Asking for Help

If you find things difficult, help is available.

• TAs are available.

• Your lecturer is available in the lab.

• You can post questions in the Brightspace discussion forum.

• You can email the lecturer (david.lillis@ucd.ie).

• You can get help from your classmates.

• Getting help to understand something is not the same as

copying a solution!

The best way to get useful answers is to ask good questions.

Don't just send a photo of your computer screen and ask "Why does this not

work?" (N.B. images are not a good way to send code).

Do:

• Send/post your Java file(s) as an attachment. We can't run code that's

in a photograph to test it out!

• Say what error message you got when you tried to run the code (if

any).

• Say what the code did that you did not expect.

• Say what the code did not do that you did expect.

1 https://www.ucd.ie/t4cms/UCD%20Plagiarism%20Policy%20and%20Procedures.pdf

How to avoid plagiarism: Helping without copying.

If you are trying to help a classmate with a programming assignment, there

are two golden rules:

Never, ever give your code to somebody else.

• You don't know what they will do with it or who they will give it to.

• If somebody else submits code that is the same as yours, you will be

in trouble too.

Don't touch their keyboard

Don't type solutions for them! It will end up looking a lot like your code. Also,

they don't learn anything.

Here are some other ways you can help a friend with an assignment, without

risking plagiarism:

• If their code doesn't work, it's OK to explain what is wrong with it.

• If they don't understand a concept, draw a diagram to explain.

• Tell them about useful methods that I have provided that can help

achieve their goals.

• Describe an algorithm that will help.

• Describe it in words or diagrams, not in code!

• E.g. "You could try saving the node's right child as a variable.

Then you could use a loop to keep getting that node's left child

until you reach the bottom of the tree".

Problems?