Reference no: EM132134791
Can Someone please help me with this please:
Task:
The purpose of this assignment is to empirically measure attributes for binary search trees.
Steps:
Create a program that will build a binary search tree (BST) by adding new elements one at a time.
You may use whatever data structure you wish for this BST.
For any node in the BST, the left subtree contains keys <= the root, and the right subtree keys > the root.
Predict the average number of nodes you must visit to determine if a given key is in a BST consisting of 100 nodes, where keys are integers between 1 and 100, based on a tree's height.
Use your program to create 100, 100 node BSTs by randomly adding integers between 1 and 100.
For each of these 100, randomly generated BSTs, determine (a) its height, and (b) the average number of nodes visited to determine if a key is in the tree.
Search for all values between 1 and 100.
Create, using Excel, a graph plotting tree height versus average search length, using both your predicted and empirical data.
Create a Word doc comparing your predicted average search lengths with your empirically derived values. If they differ, discuss why. If they are the same, discuss why.
Submit:
Source code
Excel workbook
Word doc summarizing experimental findings