0
$\begingroup$

The problem:

Find a formula for the total number of calls occurring during the insertion of n elements into an initially empty set. Assume that the insertion process fills up the binary search tree level-by-level. Leave your answer in the form of a sum.

code for INSERT function:

procedure INSERT(x: elementtype; var A: SET); 
begin
    if A = nil then begin
       A -> .element := x; 
       A ->.leftchild := nil; 
       A ->.rightchild := nil;
    end;
    else if x < A ->.element then
        INSERT(x, A->.leftchild);
    else if x > A ->.element then 
        INSERT(x, A ->.rightchild);
    end;
end;

The main confusion for me here is with leaving my answer in the form of a sum. I'm not all that great at sums (haven't taken Calc 2 yet), so I don't really know how to set them up or extract information from them all that well. Any help here would be greatly appreciated.

For clarity: This is a review problem where the answer is:

Let $2^k \leq n \leq 2^{k+1}$. Then $k = \log n$ and the number of calls equals,

$$ \sum_{i = 0}^{k - 1} (i + 1)2^i + (k + 1)(n - 2^k + 1) $$

I'd like to know the process behind getting this answer. Thank you.

$\endgroup$
1
$\begingroup$

The key observation here is that the input is assumed to be such that all insertions fill level 0 (the root level), then completely fill level 1, then completely fill level 2, and so on.

In filling level $i$ we will have constructed $2^i$ new nodes, each of which will require $i+1$ calls to INSERT, so the total cost to fill level $i$ will be $(i+1)2^i$. Thus, the cost to fill levels $0, 1,\dotsc, k-1$ will be $$ \sum_{i=0}^{k-1}(i+1)2^i $$ Now let's say we're finishing by filling level $k$ partially or fully. We're then inserting elements $n=2^k,2^k+1,2^k+2, \dotsc, 2^{k+1}-1$. Each of those will cost $k+1$ calls to INSERT, so for $n$ elements we will have used $n-2^k+1$ insertions, each of cost $k+1$ for a total of $(k+1)(n-2^k+1)$ calls. That must be added to the cost of filling the upper rows, so you get a total cost of inserting $n$ elements level-by-level equal to $$ \left(\sum_{i=0}^{k-1}(i+1)2^i\right) + (k+1)(n-2^k+1) $$

$\endgroup$
  • $\begingroup$ Thank you very much! This is the explanation I needed. Learned a bit more about sums from your answer as well :D $\endgroup$ – Matthew Freihofer Mar 1 '16 at 16:45
  • $\begingroup$ Am I right in assuming that we need i + 1 calls because, if we insert i nodes, then we need to make 1 more call to insert the root? $\endgroup$ – Matthew Freihofer Mar 1 '16 at 17:27
  • $\begingroup$ @MatthewFreihofer. Exactly. $\endgroup$ – Rick Decker Mar 1 '16 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.