Register

BST

• recategorized by
573 views
1 votes
1 votes
certain file system stores records as per binary search tree principles.If the preorder traversal is 90,40,30,190,140,100,290.What is the expected number of comparisons when we randomly request one of the records?
• recategorized by
User Avatar

1 Answer

2 votes
2 votes
Construct bst from given sequence ..now there will be 1 node at level 0,2 at level 1 ,3 at level 2 and 1 at level 3 no of expected comparisons=1*1+2*2+3*3+1*4/7=18/7=2.57
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
2 answers
1
rajoramanoj asked Nov 6, 2017
862 views
NO. OF BST POSSIBLE
User Avatar
3 votes
3 votes
1 answer
2
iita asked Jan 19, 2017
3,246 views
number of BST
The number of BST possible with 6 nodes numbered 1, 2, 3, 4, 5 and 6 with exactly one leaf node __________
The number of BST possible with 6 nodes numbered 1, 2, 3, 4, 5 and 6 with exactly one leaf node __________
User Avatar
0 votes
0 votes
1 answer
3
aditi19 asked Oct 1, 2018
626 views
Optimal BST
what are the applications of optimal binary search tree?
what are the applications of optimal binary search tree?
User Avatar
0 votes
0 votes
1 answer
4
K ANKITH KUMAR asked Aug 29, 2018
1,829 views
Recurrence Relation of BST
Let T (n) be the number of comparisons needed in a binary search of a list of n elements. What is the recurrence relation? Explain. 1) T(n) = T(n/2) + 2 2) T(n) = T(n/2) + 1
Let T (n) be the number of comparisons needed in a binary search of a list of n elements. What is the recurrence relation? Explain. 1) T(n) = T(n/2) + 22) T(n) = T(n/2) +...
User Avatar
Link Copied!