Assignment $4$: Trees & Binary Search Trees $(8\%)$

Completion requirements

To do: Make a submission To do: Receive a grade

According to our suggested $13$ week course schedule, this programming project should be completed and submitted by the Monday of Week $11.$ It is worth $8\%$ of your final grade. Please refer to the $$Assignments Overview$$ for details on the marking rubric and submission of work.

Complete the implementation of a DecisionTree, introduced in Chapter $19.$ This will require completing a number of methods from the source code for this chapter, particularly for LinkedBinaryTree. Your initial test should be the BackPainAnalyzer output from Listing $19\mathrm{.}6$ on page $746.$ Show test cases for at least two other correct traversals of this tree.

Develop and demonstrate another decision tree that is more complex the BackPainAnalyzer tree. Provide at least two correct traversals of this tree, as well.

PP $20\mathrm{.}5($page $801)$

Complete all missing methods in LinkedBinarySearchTree. Show test cases for all implemented methods being sure to include edge cases for methods where applicable.

Then, implement a balance tree method for this class using the brute force method described in Section $20\mathrm{.}5$ of your textbook.

Show test cases for two different degenerate trees, outputting the height of the tree before and after balancing the tree. Then, demonstrate insertions into a balanced tree that result in degenerate trees and rebalance the tree again.

Hint: Copy the elements into an ArrayList using an in$-$order traversal. Recursively build a balanced tree using a binary partitioning.

Criteria

Weighting

Correctness of solution: Algorithm is implemented and produces correct results for the stated problem.

$/4$

Testing: Submission of test exhibits to indicate the solution works for a range of cases $($e$.$g$.,$ minimum and maximum inputs$)$ and handles unexpected exceptions.

$/2$

Comments and documentation: Source code contains comments that explain in plain English what the code is intended to do$.$ Note: Javadoc style is not required.

$/2$

Total

$/8$