Jump to content

Binary search tree


Recommended Posts

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.

Link to comment
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
×
×
  • Create New...