首页 > > 详细

代写COMP2014J、Java编程设计辅导

Assignment 1:
AVL Trees and Tree Maps
COMP2014J: Data Structures and Algorithms 2
Lecturer: Dr. David Lillis (david.lillis@ucd.ie)
Weight: 15% of final grade
Due Date: 23:59 Tuesday May 9th 2023 (Week 12)
Document Version: 1.0
Introduction
This assignment is intended to give you experience implementing AVL trees
and using an AVL 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:
• Implement the key methods for an AVL Tree, according to the provided
interfaces and base classes.
• Adapt your AVL Tree implementation to implement the key methods of
a Tree Map, according to the provided IMap interface.
• Develop a strategy to test if your implementations are correct.
Implementation of AVL Tree Methods
The source code contains a partial implementation of an AVL Tree in a file
called AVLTree.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.
You must implement the following methods:
• public boolean insert(T value) – insert a value into the AVL tree.
Returns true if the value was inserted (i.e. it was not already in the
tree), or false if not.
• public boolean remove(T value) – remove a value from the AVL tree.
Returns true if the value was removed, or false if not (i.e. the tree did
not contain that value).
• public boolean contains(T value) – check to see if a value is contained
in the AVL tree. Returns true if the value is in the tree, or false if not.
• private void restructure(IPosition x) – trinode restructuring (the
three nodes are x, its parent and its grandparent).
If you wish, you may create other methods that help you to complete the task
(e.g. rightRotate(IPosition n), leftRotate(IPosition n), etc.).
Some hints and tips
• Remember your AVLTree extends several other classes, so you can use
some of their helpful methods (e.g. expandExternal(…)).
• The expandExternal(…) method uses newPosition(…) to create all position
objects, so all the positions in the tree will be AVLPosition instances.
• You can cast an IPosition to an AVLPosition 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.
Tree Map Implementation of IMap Methods
The source code contains a skeleton implementation of a map based on an
AVL Tree in a file called AVLTreeMap.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.
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 IMap

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!