# optimal binary search algorithm

PROJECT:

Write a program to generate a optimal binary search tree for the given (ordered) keys and the number of times each key is searched.

You may reuse the pseudocode algorithms provided in lecture notes.

Use the following Data Set:

A < B < C < D < E < F < G < H < I < J < K < L < M < N < O < P < Q < R

995 22 23 562 33 8 60 118 30 723 807 626 15 89 21 128 626 621

In the class, we worked with probability of searching for each item. Here, we have given the number of times each item is searched - which makes for easier integer comparison/arithmetic. Simply treat this number as the probability.

In addition, your program must contain the logic to generate and output the optimum binary search tree (see below), from the dynamic programming table.

Do NOT HARD CODE the tree in your program. It must be calculated and output by the program. The only hard coding you can do is for the input(s) (i.e., data set) given here (see below).

OUTPUT(s):

The program should output the dynamic programming table (see below).

It should also output a optimum binary search tree (see below).

SUBMISSION:

Use the sample output format given below. Note that the output should be reasonably formatted for easy readability.

Submit your work (as you did before) into Angel in the "Project 2" drop box, before class on due date.

SAMPLE OUTPUT:

Table:

- A B C D E F G H I J K L M N O P Q R

A X X X X X X X X X X X X X X X X X X

B 0 X X X X X X X X X X X X X X X X X

C 0 0 X X X X X X X X X X X X X X X X

D 0 0 0 X X X X X X X X X X X X X X X

E 0 0 0 0 X X X X X X X X X X X X X X

F 0 0 0 0 0 X X X X X X X X X X X X X

G 0 0 0 0 0 0 X X X X X X X X X X X X

H 0 0 0 0 0 0 0 X X X X X X X X X X X

I 0 0 0 0 0 0 0 0 X X X X X X X X X X

J 0 0 0 0 0 0 0 0 0 X X X X X X X X X

K 0 0 0 0 0 0 0 0 0 0 X X X X X X X X

L 0 0 0 0 0 0 0 0 0 0 0 X X X X X X X

M 0 0 0 0 0 0 0 0 0 0 0 0 X X X X X X

N 0 0 0 0 0 0 0 0 0 0 0 0 0 X X X X X

O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 X X X X

P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 X X X

Q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 X X

R 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 X

Binary Tree:

Do it like the folder view (file/directory structure shown like a tree) in a file explorer. Basically, “output” the nodes in “pre-order”.

For example, in Page 225 of the book, for the binary tree in exercise 6.3.1 (a), (the tree with nodes [2, 3, 5, 6, 8]) it will be output as:

5

3

2

-

6

-

8

( 19 comentários ) Huntsville, United States

ID do Projeto: #5129283

## Premiar a:

vano101

Hello. Generally it is easy but there is need to provide additional information. For instance I would like to have PDF/DOC/etc with lecture notes, where algorithm pseudocodes are described

\$37 USD em 1 dia
(128 Avaliações)
5.7

## 4 freelancers are bidding on average \$60 for this job

samitXI

Hi Sir, I am ready to work for you.I have 9 years of experience in C/C++ , java, PHP and, MySQL. please see some of my works also check my reviews you will get better idea about my skill.I deliver quality work within Mais

\$103 USD em 1 dia
(55 Comentários)
6.4
dobreiiita

Hello, I'm C++ expert and can surely help you with this project, I will complete asap, Please let me know if you are interested. Thank You

\$64 USD em 1 dia
(111 Comentários)
5.9
nani01029x

I have done some projects in programming. I have very strong profile with some positive feedbacks from the students around the world. You can check my profile for more detail. Let me help you. I'm ready to get started Mais

\$35 USD em 1 dia
(26 Comentários)
4.3