JAVA CODE :

For this assignment you are going to look at the most basic characteristic of two Binary Search Trees:

an unbalanced binary search tree, and

a self-balancing binary search tree.

Create a Netbeans project named Lab111 and implement the following ADTs:

a TreeMap which will be the unbalanced binary search tree, and

an AVLTreeMap which will be self-balancing binary search tree.

Create a Client program that

creates an instance the unbalanced binary search tree, inserts 8,800 entries the tree, and prints out the information shown below.

creates an instance the self-balancing binary search tree, inserts 8,800 entries the tree, and prints out the information shown below.

========== Tree Map ==========

Before any insertions:

Tree Map Size = 1

Tree Map Height = 0

After 8,800 insertions:

Tree Map Size = 17,601

Tree Map Height = 8,800

========== AVL Tree Map ==========

Before any insertions:

AVL Tree Map Size = 1

AVL Tree Map Height = 0

After 8,800 insertions:

AVL Tree Map Size = 17,601

AVL Tree Map Height = 14

====================================

In order to create the TreeMap ADT and the AVLTreeMap ADT you will need to implement code that is not found in Code Fragments in the textbook. To make this assignment reasonable:

You may use the Java Source Code supplied by the authors.

You will find this code at:

the publishers website ->

The Student Companion Site ->

Browse by Resource ->

Source code

The download will be a file named sourcecode.zip

When you extract this archive you will end up with a file named sourcecode.jar

A jar file is a Java zip archive that contains .java files and .class files.

You can ignore the .class files.

An easy way to work with this archive is to rename it with a .zip extension and extract the files from the archive.

Once you have a directory containing the .java files from the textbook:

Use these files to implement the TreeMap ADT and the AVLTreeMap ADT.

Include in your project directory only those .java files that are required to implement the TreeMap ADT and the AVLTreeMap ADT.

All of the required .java files must be in your Netbeans project source code directory.

All of the required .java files must come from the textbook source code archive.

There will be a 10% point deduction for each unneeded .java file that is in your Netbeans project source code directory.

A mystery you must solve:

If you inspect the example output given above, it should be clear that something is wrong with my solution. I inserted 8,800 entries into the tress but my output shows a size of 17,601. You need to:

Write your client so that it outputs the correct size.

Explain what I most likely did wrong in my solution.

Explain why I may have made the mistake that I made.

Note, in outputting the size I did not make any calculation. I simply called an available method.

The answer to this question should be the first entry in your Word document.

One additional requirement:

To make it easy for the graders define a constant, N, at the top of your Client code that holds the number of entries to be inserted into each of the trees.