Compute the average number of key comparisons needed

Assignment Help Computer Engineering

Reference no: EM131857483

Problem

You are to build binary search trees with nodes consisting of key & count fields. Keys are inserted in the given order into the tree - each new key with initial count 1 otherwise increment the count at the node containing the key by 1. For the following two input key sequences, you are to compare the heights of the four resulting binary trees, two without special balancing effort and two red-black trees.

1. A sequence of 500 random numbers each between 1 & 100.

2. 1, 3, 5,.....99, 2, 4, 6,..., 100, followed by 400 random numbers between 1 & 100.

Also find the average number of key comparisons needed for a successful search in each of the four resulting trees, assuming that the counts represent the relative frequencies of the keys being sought. Compare the results.

Note. The height of the tree represents the worst-case performance of a successful search. The average weighted path lengths represents average performance of a successful search.

Files need to be submitted:

1) Your Code

2) Output screenshots

3) Project report

Put all the files in a folder and make it a zipped folder

The source code should be included as appendices. You can use any programming language(preferably using java) to implement this.

Reference no: EM131857483

Questions Cloud

Explain the mathematical calculations : Could you please explain the mathematical calculations for KEPLERS LAW and Newtons law of gravitation

What are challenges of observing : What are challenges of observing and making images of planets around stars?

Determining how fast a distance galaxy : For each of the following, decide what type of observation (imaging, spectroscopy, timing) you would need to make. Explain clearly.

How many mars volumes would equal one jupiter volume : a. How many of the planet Mars would you need to be the same mass as one Jupiter mass? b. How many Mars volumes would equal one Jupiter volume?

Compute the average number of key comparisons needed : Also compute the average number of key comparisons needed for a successful search in each of the four resulting trees.

What exactly does galileo observe with the telescope : What exactly does Galileo observe with the telescope, as described in The Starry Messenger? Why are these observations so important?

Identify the internet browsers that you used : Identify the Internet Browser(s) that you used:[Outcome #1]. Identify a minimum of two (2) search engines that you used:[Outcome #1].

Determining the atoms in body : Atoms in Your Body. A human body is mostly water; it contains ~ 2/3 hydrogen, 1/4 oxygen, 1/10 carbon, and less than 1 percent higher-mass elements like iron.

Identify the pros and cons of each choice : You manufacture wine goblets (fine glassware) in the U.S. In mid-June you receive an order for 10,000 goblets from Japan.

User Account

All Pages