Homework #2 – Binary Search Trees

 Homework #2 – Binary Search Trees
You should prepare the answers of Questions 1 and 3 using a word processor (in other words, do not submit images of handwritten answers).

Question 1 – 15 points
(a) [5 points] What are the preorder, inorder, and postorder traversals of the binary tree below:
M
O
L
A
G
H
R T
I
(b) [5 points] Insert 50,40,80,30,45,70,90,10,60,75,85 to an empty Binary Search Tree. Show only the final tree after all insertions. Then delete 45,40,80,75,50 in given order. Show only the final tree after all deletion operations. Use the exact algorithms shown in lectures. Verify your answers by using this visualization tool.
(c) [5 points]Abinarysearchtreehasapreordertraversalof P,F,B,M,K,S,R,Z. What is its postorder traversal? Reconstruct the tree from those traversals and draw it.
Page 2
Fundamental Structures of Computer Science II
Question 2 – 70 points
(a) [30 points] Write a pointer-based implementation of Binary Search Tree named as PbBST for maintaining a list of integer keys. Implement insert, deleteKey and getHeightmethodsforPbBSTclass. PutyourcodeintoPbTreeNode.h,PbTreeNode.cpp, PbBST.h and PbBST.cpp files. Prototypes of required methods: void insert(int key); // 10 points void deleteKey(int key); // 15 points int getHeight(); // 5 points
(b) [10 points] Write another method for PbBST class to return the median of numbers in that BST in linear time (linear in the number of items). Your method should have the following prototype: double medianOfBST();
(c) [15 points] Implement a method for PbBST class which prints the keys in a given range (side by side) in O(logn + m) time, where n is the number of nodes in the tree and m is the size of the range. You will not get any credit if your implementation runs asymptotically slower. Your method should have the following prototype (assume a < b): void rangeSearch(int a, int b);
(d) [15 points] Height of BST is a very important property which affects the performance of search, delete, and insert operations directly. In this part, you will analyze how the height of BST changes as you insert and delete random number into/from the tree. Write a global function, void heightAnalysis(); which does the following:
(1) Creates an array of 20000 random numbers and starts inserting them into an empty BST. At each 1000 insertions, outputs the height of the tree. (2) Shufflesthearraycreatedinpartd1. Theniteratesoveritanddeletesthenumbers from the tree. After each 1000 deletions, outputs the height of the tree.
Add your code to analysis.cpp file. When heightAnalysis function is called, it needs to produce an output similar to the following one:
Page 3
Fundamental Structures of Computer Science II
Listing 2: Sample output Part f - Analysis of BST height - part 1 ----------------------------------------Tree Size Tree Height ----------------------------------------1000 x 2000 x ...
Part f - Analysis of BST height - part 2 ----------------------------------------Tree Size Tree Height ----------------------------------------19000 x 18000 x ...
(e) [0 points] Create a main.cpp file which does the followings: • creates an empty BST and inserts the following numbers into it: {40,50,45, 30,60,55,20,35,10,25} • prints the height of the tree • deletes 45 and 50 from the tree • finds the median of numbers by using medianOfBST method • prints numbers between 15 and 53 by using rangeSearch method • calls heightAnalysis function
At the end, write a basic Makefile which compiles all your code and creates an executable file named hw2. Check out these tutorials for writing a simple make file: tutorial 1, tutorial 2. Please make sure that your Makefile works properly on the dijkstra server.
Question 3 – 15 points
After running your programs, you are expected to prepare a single page report 1 about the experimental results that you obtained in Question 2 d. With the help of a spreadsheet program (Microsoft Excel, Matlab or other tools), plot number of elements in tree versus height of tree after each 1000 insertions and deletions. On the same figure, plot number 1Please make sure that your report does not exceed the specified page limit too much, otherwise you may lose points
Page 4
Fundamental Structures of Computer Science II
of elements in tree versus theoretical average height of BST. A sample figure is given in Figure 1 (these values do not reflect real values).
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
x 10 4
0
5
10
15
20
25
Number of elements in tree
Tree height
Analysis of Average BST Height
After insertions After deletions Theoretical values
Figure 1: Sample figure
In your report, you need to discuss the following points:
• Do your findings related to average height of BST agree with the theoretical values? State the theoretical value and discuss how close these values are to the values you obtained.
• How would the height of the tree change if you inserted sorted numbers into it instead of randomly generated numbers?
Page 5