1. (100 pts) Write a program to randomly pick an element of a binary search tree

Question

1. (100 pts) Write a program to randomly pick an element of a binary search tree randomly. All the elements should have about equal probability of being selected. Consider the following binary search tree as an example If you simulate flipping a coin and choose left or right based on the outcome, node 7 will be selected 50% of the time. We want the probability of node 7 to be selected to be 1 /7. Note that the elements in the tree need not be the numbers. Don't assume anything abont individual the user as shown below and use your proposed scheme to estimate the probabilitics. y numbered. There may be gaps between Just read the numbers from fox01assignbonus Enter the set of numbers for the tree 60 41 72 23 57 1 32 Probabslities after 1000 randoa selections are p(60)-0.135000 P(41) 0.135000 p(72) 0.152000 p(23) - 0.147000 p(57)0.156000 p1)0. 147000 p(32)-0128000 Insert the numbers into the trees in the order they are listed. Once you build the tree, pick a randon element 1000 times and estimate and print the probabilities

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main()
{
int n,i,j,k;
printf("Enter the number of elements in the tree:");
scanf("%d",&n);
printf("Enter the set of numbers for the tree: ");
int a[n];
double count[n];
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
count[i]=0;
}
srand(time(NULL));
for(i=0;i<1000;i++)
{
int m = rand()%n;
//printf("%d ",m);
count[m]+=1;
}
for(i=0; i<n; i++)
{
printf("p(%d) = %f ",a[i],count[i]/1000);
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.