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. Quote Link to comment Share on other sites More sharing options...
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.