0
$\begingroup$

I was given this as a homework exercise, yet I don't know whether my solution is sound:

Given a complete binary search tree where blocks are formed in order of the value of the nodes. What would the amount of IOs be to reach any leaf from the root?

I think I can define the amount of IOs recursively as follows: 

search(A) = search(A/2)+1 if n>B/2
          = 0 otherwise

Where n is the size of A and B is the block size.
Since I think storing in order would always store a complete subtree of size B/2 in the same block.
This would then give log2(2n/B) IO operations for any root to leaf traversal.

Firstly, is that a correct bound? Secondly, is the storing of a complete B/2 sized subtree guaranteed with block size B?

Note that the bound is for amount of IO operations, not time complexity.

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't think the storing of a complete subtree with B/2 size is correct, but I do think there is some constant for which it holds. $\endgroup$
    – b9s
    Oct 10, 2016 at 15:57
  • $\begingroup$ I think I've got some bounds. In the optimal case, B is exactly the size of a subtree (2^n-1), so only log(n/B) IOs are necessary. However, the worst case is when just one node of a subtree isn't loaded. Then the largest complete subtree has one less level and B is at most 4*size of subtree +1 (since a B higher than that must have a subtree of a higher size). So in that case you obtain log(4*n/B) IOs $\endgroup$
    – b9s
    Oct 10, 2016 at 16:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.