代写 Java Tasks

Tasks
The main tasks for this assignment are:
• Implemented the Binary Tree Traversal methods
• Implement the core functionalities for an AVL Tree
• Test if your AVL implementation is correct
• Improve the efficiency of your AVL implementation
1. Implementing Binary Tree Traversal Methods
The source code contains a partial implementation of Binary Tree Traversals in a file called Traversal.java in the dsa.impl package. Your work in this section must be in this class.
You must implement the following methods:
• private void visitNode( BTNode x ) – print the element in the node x.
• public void preOrderTraversal( Object bt ) – preOrderTraversal of the tree bt.
• public void preOrderTraversal( Object bt ) – inOrderTraversal of the tree bt.
• public void postOrderTraversal( Object bt ) – postOrderTraversal of the tree bt.
Note that before implementing the methods preOrderTraversal, inOrderTraversal and postOrderTraversal, you need to replace the type Object with the most suitable type for the parameter bt and indicate in comment the reason for your choice:
• ITree • AbstractBinaryTree
• ProperLinkedBinaryTree • BinarySearchTree
• AVL
2. Implementing 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.
You must implement the following methods:
• private void rotate( INode x ) – trinode restructuring (the three nodes are: x, its parent and its grandparent).
Hint: You can cast to an INode to a BTNode in the same way as you did in Worksheet 4.
• public void insert( T element ) – insert a value into the AVL tree.
• public void remove( T element) – 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.
If you wish, you may create other methods that help you to complete the task (e.g. rightRotate(INode n), leftRotate(INode n), etc.).
3. Testing Your AVL Implementation

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.
In the Main class, write code that will automatically perform some operations on your tree implementations, to check if they are correct. Here are some suggestions:
– A simple test: perform some operations on the trees, then print the tree using you previously implemented Binary Tree Traversal methods and manually compare it to what you expect the output to be. You need to use as many traversal methods as needed to capture the structure of the tree.
– A more complex test: A Binary Search Tree (BST) implementation has been provided. Write a method to compare the structure and contents of your AVL with a BST that represents the correct output.
– More complex again: Create text files that represent operations to be performed on different types of trees (e.g. Insert 10 to insert 10 into the tree, Remove 25 to remove 25, etc.). Write code to read these files and perform the operations on the trees, then compare the outputs.
In all of the above cases, you need to know what the correct output of your implementation should be. The operations you perform should test all the different types of rotations that are possible (they should cause LL, RR, LR and RL rotations, and both at the root and deeper in the tree).
4. Improving Efficiency of Your AVL Implementation
In this implementation, the height of each node must be recalculated every time it is needed, which in practice makes both the insert(…) and remove(…) methods O(n) operations, where n is the number of nodes in the tree.
Adjust the implementation of the AVL tree so that each node stores its own height, and these are updated only when necessary (Hint: updating the heights of nodes should be no worse than O(h) complexity following an insert(…) or remove(…) operation, where h is the height of the tree).
For this task, you must not change the public API of the AVLTree class. All your code must be inside the AVLTree.java file.
All code should be well-formatted and well-commented to describe what it is trying to do.

• If you write code outside the Main.java, Traversal.java and AVL.java files, it will not be noticed when grading. Write code only in these files.
• Submit a single .zip file to Moodle.
o This should include only the ‘src’ folder from your project that contains all your code.