( Java code)

Design and implement an AVL tree node class that must support insert, and option-

ally remove operations.

Design and implement a Left-Leaning Red-Black tree node class that must support insert, and optionally remove operations.

Design and implement a main method that does the following:

(a) Create an array that contains a list of integers, in an ascending order, from 1 to a large enough number (e.g., 1000000 so that the running time of building a tree containing those numbers will be at least 1 second).

(b) Create an array that contains a list of integers that is the same as the 1st but in descending order (e.g., from 1000000 to 1).

(c) Create an array that has the same numbers as above, but the order of the numbers (e.g., 1 - 1000000) is random. You can use a random number generator to decide and put a number into the array.

(d) AVL-insert, into a separate AVL tree that is initially empty, the numbers in each array sequentially from the start to the end. Measure and print out the elapsed time of building each tree.

(e) RB-insert, into a separate LLRB tree that is initially empty, the number in each array sequentially from the start to the end. Measure and print out the elapsed time of building each tree.

Deliverables:

Source code.

Performance analysis document that will record, compare, and analyze the running times of building different AVL and LLRB trees.