CS 241, Spring 99, Homework 4 Practice Exercises
  1. What are the maximum number of keys that can be stored in a B-tree of height two (the root plus two additional levels) with a minimum branching factor of t=500?
    Solution
  2. For the following B-tree where t=3 show the result when "B" and then "Q" are inserted.
    Solution
  3. Consider the following B-tree where t=2. Show the B-tree that results when deleting "W". NOTE: The solution just shows the final answer. If you did not get that answer, come see us for help figuring out where you made a mistake. In your homework solutions you are expected to show the intermediate trees so that we can see your work.
    Solution
  4. First show the result of extract-max on the binary heap A = 40,10,30,7,9,20,25,5,6,8,1,15,2. Then show the result of insert 35 on the resulting binary heap.

    Note: In this problem the 35 was inserted to the heap that resulted from extract-max. In your homework you are suppose to do the insertion on the original heap.
    Solution
  5. Give and analyze a procedure Delete(A,i) that deletes A[i] from binary heap A that currently has n elements. Be sure to carefully analyze the time complexity of your algorithm.
    Solution

Solution to #1)

To maximize the number of keys stored in a B-tree with t=500, each node will have 999 keys and 1000 children. Thus the number of nodes in such a B-tree of height two will be 1+1000+ 1000^2 = 1,001,001. Thus the number of keys is 999 x 1,001,001 = 999,999,999

Solution to #5)

In the below code, we assume the binary heap is stored in A[1..n] where both A and n are instance variables. (A is the array and n is the number of elements currently stored in it). 
Delete(i){
   temp = A[i]            \\ holds value we are deleting
   A[i] = A[n]            \\ put A[n] in place of A[i]
   n=n-1
   if (A[i] > temp){      \\  if the value of A[i] is increased
      value = A[i]         \\  move A[i] up tree (as needed) like in insert
      while ((i > 1) and A[parent(i)] < value){
         A[i] = A[parent(i)]
         i = parent(i)
      }
      A[i] = value
   }
   else                   \\ if we decreased the value of A[i]
       heapify(A,i)       \\ use heapify from text
}
If A[i] > temp then we have replaced A[i] with something larger. In this case we use a procedure like that used for insertion, to "insert" the new value in the right place in the chain of its ancestors. This takes O(log n) time (where n is the number of items in the heap) since the number of iterations is at most the height of the heap. Note that given when A[i] <= temp (i.e. we have replaced A[i] with something smaller) then we have exactly the conditions required for heapify to restore the heap. Thus the time complexity is that of heapify which is O(log n). Thus the overall time complexity is O(log n).