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

C++ Programming

Project ID: #5129283

About the project