COMP2003J: Data Structures and Algorithms 2 - Assignment 1: AVL & Splay Trees
Assignment 1: AVL & Splay Trees
COMP2003J: Data Structures and Algorithms 2 Weight: 10% of final grade Document Version: 1.0
Introduction
This assignment is intended to give you experience implementing AVL and Splay trees. It is also a good exercise to gain experience about how generics, inheritance and object references work in Java. Source code that you can start from has been posted to BrightSpace in the file Assignment1-Source.zip. This also contains the Javadoc API documentation for the classes that have been provided (in the “doc” folder). Import this project into Eclipse in the usual way.
Tasks
The main tasks for this assignment are: • Implement the key methods for an AVL Tree. • Implement the key methods for a Splay Tree. • 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. 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 void insert( T value ) – insert a value into the AVL tree.
- public void remove( T value ) – remove a value from the AVL tree.
- 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
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.
Implementation of Splay Tree Methods
The source code contains a partial implementation of a Splay Tree in a file called SplayTree.java in the dsa.impl package. 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:
- private void splay( IPosition
p ) – splay a position in the tree. - public void insert( T value ) – insert a value into the splay tree.
- public void remove( T value ) – remove a value from the splay tree.
- public boolean contains( T value ) – check to see if a value is contained in the splay tree. Returns true if the value is in the tree, or false if not. Remember, this method also causes a splay(…) operation.
Testing the Tree Implementations
It is important to check whether your implementations are correct. A good way to do this is to use your tree 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. 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 and measures how quickly it runs. This is a good way to test the efficiency of your implementation.
Create some test classes for your implementation (called Test1, Test2, etc.). You can follow these examples or have your own ideas. In your tests, you should test all the different types of restructuring that are possible (e.g. for a Splay Tree they should cause zig, zig-zig and zig-zag splays to both sides, and at the root and deeper in the tree). 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 SplayTree.java, AVLTree.java and test files (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. It is not necessary to submit your entire Eclipse project.
Assignment 1 Grading Rubric
This document shows the grading guidelines for Assignment 1 (implementation of AVL Trees and Splay Trees). Below are the main criteria that will be applied for the major grades (A, B, C, etc.). Other aspects will also be taken into account to decide minor grades (i.e. the difference between B+, B, B-, etc.).
Readability and organisation of code (including use of appropriate functions, variable names, helpful comments, etc.). Quality of solution (including code efficiency, minor bugs, etc.).
Passing Grades
D Grade Good implementation of an AVL Tree or Splay Tree, plus some basic testing. A "good" implementation is one where all the key methods work correctly in the vast majority of cases (i.e. some occasional bugs will be tolerated). C Grade Good implementation of an AVL Tree and a Splay Tree, plus some basic testing of both; OR Good implementation of an AVL Tree or a Splay Tree, plus comprehensive testing of the tree in question. "Comprehensive" testing should make sure that the different operations of the tree(s) are all tested (e.g. for a Splay Tree "Zig" operation, it would check both situations where the node is a left child and where the node is a right child. For a "Zig-Zig" operation, this should also be tested for both sides, as well as being tested where the splay operation happens at the root and where it happens deeper in the tree). B Grade Excellent implementation of an AVL Tree and a Splay Tree, plus comprehensive testing of both; OR Excellent implementation of an AVL Tree and a Splay Tree, with some basic testing and an efficient approach to height calculation for AVL trees. A Grade Excellent implementations of AVL Tree and Splay Tree, with comprehensive testing of both and an efficient approach to height calculation in AVL Trees.
Failing Grades ABS/NM Grade No submission received/no relevant work attempted. G Grade Code does not compile; OR Little or no evidence of meaningful work attempted. F Grade Some evidence of work attempted, but few (if any) methods operate in the correct manner. E Grade AVL Tree and/or Splay Tree have been attempted, but there are too many implementation errors for the implementation to be useful in practice.
