Hi UniGui family,
any one with experience of BST search, can you help an old man with this, want to do this in UniGui and then have a chart to display result. thank you
T1. Run empirical studies to compute the average length of a path to a random node in a
BST (Binary Search Tree) built by insertion of N random keys into an initially empty tree,
for N from 100 to 10,000. Do 1,000 trials for each tree size;
(a) For a given tree size N,build a BST by insertion of N random keys;
e.g., randomly shuffle numbers of 0 to N − 1
and insert them into an (initially empty) BST.
(b) Randomly pick a node in the BST; e.g., randomly
pick a number between 0 and N − 1.
(c) Compute the length of a path to the node, i.e.,
the number of compare’s carried out while searching the node in the BST.
(d) Repeat Step 1b and 1c for 1,000 trials and get the average number of compare’s.
Plot the results with the horizontal axis representing treesize N and the
vertical axis representing(average) number of compare’s; The plotting can be done
using any external software such as spreadsheets.
T2. Run similar empirical studies to compute the average number of compare's in Binary Search
with an (sorted) array. Note that this has nothing to do with inserting sorted data into a BST.
Plot the results.
T3. Compare those plots from T1and T2; e.g., overlay the plots together.
Discuss whether one could draw a conclusion that the search with BST is
more efficient than Binary Search with an (sorted) array or the other way around, etc.