Implement an AVL tree ADT. The design of the class is up to you. You may choose to use as much

or as little of lib$280-$asn$4$ as you desire $($including extending existing classes, implementing existing

interfaces, taking pieces of code for your own methods, or not using any of lib$280-$asn$4$ at all$)$ but you

will be graded on the appropriateness of your choices, so make good choices. Employ good software

engineering principles in making your decisions.

Regardless of your design decisions, you can earn full marks for correctness of implementation as

long as the following requirements are met:

$$ Your AVL tree ADT must be able to contain elements of any comparable object type, but all

elements in a single tree are the same type.

$$ Your ADT must support insertion of new elements, one at a time. Additionally, the insertion

algorithm implementation must have the following properties:

$$ It must be O$($log n$)$ in the worst case. This means you have to store subtree heights in the

nodes $($see previous section$)$ to avoid incurring the linear$-$time cost of a recursive height

method. Part marks will be given for solutions that are at worst O$($n log n$),$ but such a

solution will receive a major deduction. No marks will be given for solutions where insertion

and deletion is worse than O$($n log n$).$

$$ The tree must restore the AVL property after insertions using rotations.

$$ You are free to choose whether or not to allow duplicate items in the AVL tree.

$$ Your ADT must have an operation for determining whether a given element is in the tree.

$$ Your ADT must have an operation that deletes an element. The mechanism for specifying the

item to delete is up to you, but again your design decisions here will be assessed for their appropriateness. Additionally, the deletion algorithm implementation must have the following

properties:

$$ It must be O$($log n$)$ in the worst case. Again, part marks will be given for solutions that are

Page $4$

at worst O$($n log n$),$ but such a solution will receive a major deduction. No marks will be

given for solutions where insertion and deletion is worse than O$($n log n$).$

$$ It must restore the AVL property after deletions using rotations.

$$ You must include a test program $($in a main$()$ method$)$ that demonstrates the correctness of your

implementation. The purpose of this test program is to demonstrate to the markers that your

ADT meets the above requirements. Your program$$s output should be designed to convince the

marker that your insertion, rotation, and lookup, and search methods work correctly. Note that

the goals here are different from a normal "regression test", so console output even when there are

no errors is not only acceptable, but required. For example, you can print out the tree, describe

what operation is about to be performed, and then print the resulting tree. The onus is on you

to use your test program to demonstrate that your implementation works.. Thus you should

demonstrate cases that invoke all of the different kinds of rotations and special cases that might

arise. Your examples should be non$-$trivial, but simple enough that they can be easily verified by

inspection.

$$ You may not modify any existing classes in lib$280-$asn$4.$ But you may make new classes as you

see fit.

Design and Implementation Notes

$$ Start on this question early! It$$s not that the solution is particularly difficult, but it requires

planning. Make sure you give yourself ample time to attempt it$,$ and ask for help if you get stuck.

If you wait until the day before the due date begin, there is a high probability that you will not

complete this question. You don$$t need to finish early, but you should start planning early. Also

keep in mind that partial solutions can earn partial marks.

$$ Your early design choices can have an impact on how hard the implementation is $($indeed this is

true of any non$-$trivial software project!$).$ Think things through before you begin coding. Sketch

out the class architecture $($UML diagrams are good for this!$),$ and$/$or algorithms on paper first.

$$ Steal the toStringByLevel method $($found in LinkedSimpleTree$280)$ and modify it so that prints

the left and right subtree heights along with each node$$s contents. This will help immensely

with debugging because even if you implement insertions and rotations correctly, you$$ll get incorrect results if the subtree heights are recorded incorrectly. This is because incorrect subtree

heights will trigger rotations when none are actually needed, or prevent necessary rotations from

occurring.

$$ If you choose to use a cursor, your ADT need not have methods that allow the user full control

over the cursor position $($e$.$g$.$ goFirst$(),$ goForth$(),$ before$(),$ etc.$).$ That is$,$ your class does not

need to implement LinearIterator$280.$

$$ Make sure everything else is working correctly before you attempt the delete operation. If you

design things well, the delete operations should be able to re$-$use all of the work you did on

rotations fo