COMP2014J: Data Structures and Algorithms 2

Lecturer: Rem Collier ([email protected])

Weight: 20% of final grade

Due Date: 23:59 Friday May 9th 2025

Document Version: 1.1

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.

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.

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.

• 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.

• 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.

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

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

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

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

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.

Mandatory 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. insertinga new entry with a new key, replacing the value for an existing key, etc.).

• 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.javaand 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.
• This should include only the files you have written code in. Do not submit your entire IntelliJ project.

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

• 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.

• 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.

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 ([email protected]).
• 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.

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.

How to avoid plagiarism: Helping without copying

If you are trying to help a classmate with a programming assignment, there are two golden rules:

• 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 type solutions for them! It will end up looking a lot like your code. Also,they don't learn anything.

• 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".

If you notice any problems or errors either in this document or in the source code provided, please let me know as soon as possible via email: [email protected]

v1.0, 2024/04/09, Initial Version