CS 162 Spring 2000 Assignment 11 – Trees and Efficiency 100 points

Assigned: 05/02/2000

Due: 05/08/2000 at the start of the final – but try to finish in lab.

Pairs: You may work in pairs if you want. Note, during the course of the semester, you cannot pair with any one person more than twice. If you work in a pair, turn in ONE copy that is the work of both of you, with both of your names on it. Each member of the pair will receive the same grade for that lab.

Main Assignment:

There are two executable files under F:\DATA\Redmond\162 - bstdrv.exe and avldrv.exe. These are programs for basic binary search trees and avl trees respectively (Completed by Dr. Turk of La Salle based on code from the textbook author). These programs are set up for trees searching on single char values (actually they are general except for display tree, but we will use display tree extensively). Your job is to use both to create binary trees, and to analyze the efficiency of addition and search using simple binary search trees, avl trees, and simple lists (assume items pushed on back of list, and search is from front). Other questions to be answered at the end.

Details:

1) Build your trees by inserting the following values one at a time in the following order: a f q x n e k b y p j z u c i w

Watch carefully, and report the total number of comparisons needed in each approach during building the trees. For AVL trees report the total number of rotations as well (there are some rotations more complicated than what we have seen in class so far – e.g. when j is added).

Also, for simple lists, how many comparisons would be used?

2) Run inorder traversal capability for each tree - are the results the same using both trees?

3) By hand, determine the total number of comparisons needed using the simple tree, avl tree, and simple list to find the following values, (or that they aren't there): o n s e p a r t i f w d x c b m

Report the results.

4) The menu presented by the programs are basically the same. Key options include: 2 - add one value, 4 - traverse in order, 8 - display tree, and 11 - quit

Hand-in:

1) Your answers to the questions above – typed. A simple summary comparison such as shown below (not real results) would be useful:

Insert Search

Comparisons Rotations Comparisons

Simple Tree 35 - 80

AVL Tree 31 3 70

Simple List ? - 105

Also helpful would be a more detailed breakdown such as illustrated (partially) below (not real results):

Insert

Char Simple Tree Comparisons AVL Tree Comparisons AVL Tree Rotations List ?

a 0 0 0 ?

f 1 1 0 ?

q 2 2 1 ?

...

Find Simple Tree Comparison AVL Tree Comparisons List Comparisons

O 6 5 8

n 5 1 6

...

2) Answers to the following questions:

a) do you think the results that you found are representative of relative efficiencies if the number of different values were 500? Why or why not?

b) do you think the results that you found are representative of relative efficiencies of finds if thousands of finds were done over the course of a day or week? Why or why not?

c) thought question - how much time do you think comparisons take compared to rotations?

Miscellaneous:

1) If you have any questions about what should be done, please ask!!

2) Due to the unique nature of the assignment, do not talk to other people (non-partners) about the answers.