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.

  • $\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


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.