epos4u Posted March 31, 2019 Share Posted March 31, 2019 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 More sharing options...
Freeman35 Posted April 1, 2019 Share Posted April 1, 2019 use SQLite :) sort & search on it :) Link to comment Share on other sites More sharing options...
epos4u Posted April 1, 2019 Author Share Posted April 1, 2019 49 minutes ago, Freeman35 said: use SQLite sort & search on it thanks, but need to hard code it using BST with code Link to comment Share on other sites More sharing options...
Recommended Posts
Please sign in to comment
You will be able to leave a comment after signing in
Sign In Now