Description
Objectives: Programming
Write a C++ class to create a binary search tree. Your program shouldc calculate the average
search cost for each node in a tree and output a tree, level by level, in a text format.
1. Programming (80 points).
(a) (35 points) Write a class Binary Search Tree – include copy and move constructors, copy and
move assignment operators.
(b) (25 points) Populate a binary search tree according to the instructions provided below:
• Read integer data from the file designated by the user. Every line of the file contains one
unique integer number (no duplicates). The size of input file is not given and the termination
of input data is done by detecting the end-of-file.
• Print the input data on the screen for small input size.
• Create a binary search tree using the input data. Use the definition of a node and binary
search tree provided in the header file.
• Calculate the search cost for each node when it is inserted in a binary search tree node.
– A node element has at least two data fields: key and search_cost.
– For each node, count and store the number of comparisons required for searching a node
(i.e. the number of comparisons = the search cost for the node = 1+ the depth of the
node).
(c) (20 points) Application
• Print the tree data by performing in-order traversal operation. If the number of nodes is less
than 16, print on the screen the resulting tree along with the information about the nodes
(for each node, print its key and search cost). Otherwise, print this tree and information
about its nodes into a file. See the example below.
• Print the binary search tree on the screen level-by-level in the case when the number of nodes
is less than or equal to 16 along with the information about the nodes (for each node, print
its key and search cost). For trees larger than 16, do not print to a file as the file may be
large, see the example at 2.
• Calculate the average search cost for all nodes in the tree and print it.
• Sum up the search cost over all the nodes in your tree as you traverse the tree by the in-order
traversal.
• Divide the sum by the total number of nodes in the tree, and the result is the average search
cost for all the tree nodes
• Print the total number of nodes
2. Example:
Input data:
3
5
7
9
10
11
Create a binary search tree and provide information about each node when you display the tree.
2
Key Search Time
5 1
3 2
9 2
7 3
10 3
11 4
Total number of nodes is 6
Use the in-order traversal to output a tree on the screen or to a file. Each node is printed in the
following format:
Key[SearchCost], that is,
3[2] 5[1] 7[3] 9[2] 10[3] 11[4]
Sum of the search cost over all the nodes in the tree is: 2 + 1 + 3 + 2+3 + 4 = 15. Average search cost:
15/6 = 2.5.
Average search cost is 2.5
Output the tree level-by-level to a file (missing elements are denoted by X):
5[1]
3[2] 9[2]
X X 7[3] 10[3]
X X X X X X X 11[4]
3. Download files containing integer data from the course website.
(a) The files 1p, 2p, …, 12p contain 2
1 − 1, 2
2 − 1,…, and 2
12 − 1 integers respectively. The integers
make 12 perfect binary trees where all leaves are at the same depth. Calculate and record the
average search cost for each perfect binary tree.
(b) The files 1r, 2 r, …, 12r contain same number of integers as above. The integers are randomly
ordered and make 12 random binary trees. Calculate and record the average search cost for
each tree.
(c) The files 1l, 2l, …, 12l contain same number of integers as above. The integers are in increasing
order and make 12 linear binary trees. Calculate and record the average search cost for each
tree.
(d) Make a table and a plot showing the average search cost (y-axis) versus the number of tree nodes
(x-axis) of all perfect binary trees, random binary trees and linear binary trees.
(e) Provide the output in the text format for the files 1p–4p, 1r–4r, and 1l–4l. Another option for
tree drawing is to output elements under text mode using a queue. The nodes will be printed
according to their depth level. Missing nodes will be represented by the symbol X. A possible
solution is to fill the missing nodes with fake nodes in the data structure when printing the tree.
Example:
5[1]
3[2] 9[2]
X X 7[3] 10[3]
X X X X X X X 11[4]
4. Hints
(a) Besides using links/pointers to represent a binary search tree, you may store the binary tree in a
vector. This implementation might be useful, especially for the printing of a tree level by level.
(b) To output a binary search tree level-by-level, you may use breadth-first-search (BFS) algorithm
based on queue.
3
i. You may use the doubly linked list class, or use STL Queue
ii. The following is a pseudo-code of the BFS algorithm
output_BST_level_by_level(BinarySearchTree T)
Queue q
q.enqueue(T.root)
while (not q.empty()) do
TreeNode node = q.dequeue()
/* output a node (you need to determine whether to
output a newline) */
print node.key
if (there are still unenqueued non-nullptr nodes in the tree)
then
/* enqueue children here for later output */
endif
done
Report (20 points)
Write a brief report that includes the following:
1. A description of the assignment objective, how to compile and run your programs, and an explanation
of your program structure (i.e. a description of the classes you use, the relationship between the classes,
and the functions or classes in addition to those in the lecture notes).
2. A brief description of the data structure you create (i.e. a theoretical definition of the data structure
and the actual data arrangement in the classes).
3. A description of how you implemented the calculation of (a) individual search cost and (b) average
search cost and explain which tree operation (e.g. find, insert) was helpful. Analyze the time complexity
of (a) calculating individual search cost and (b) summing up the search costs over all the nodes.
4. Give an individual search cost in terms of n using big-O notation. Analyze and give the average search
costs of a perfect binary tree and a linear binary tree using big-O notation, assuming that the following
formulas are true (n denotes the total number of input data).
Plog2
(n+1)−1
d=0 2
d
(d + 1) ‘ (n + 1) · log2
(n + 1) − n and Pn
d=1 d ‘ n(n + 1)/2
5. Include a table and a plot of an average search costs you obtain. In your discussions of experimental
results, compare the curves of search costs with your theoretical analysis results in item 3.
4
