Exam 2

Sample 2, 50 Minutes

Solutions

(a): To perform the operation, we can do a level-order traversal of the binary tree. The last element visited in this order is the deepest element. During the visit step, we simply record the element visited in a variable last. Upon termination of the traversal, this variable contains the deepest element. The code is given below. The relevant files are ebinary.*.


template <class T>
T BinaryTree<T>::DeepestElement()
{// Return the deepest element in the tree.
 // Throw BadInput exception is the tree is empty.
   if (!root) // no deepest element
      throw BadInput();

   // do a level-order traversal keeping track of
   // the most recently seen element
   LinkedQueue<BinaryTreeNode<T>*> Q;
   BinaryTreeNode<T> *t = root;
   T last;  // last element encountered
   while (t) {
      last = t->data;
      if (t->LeftChild) Q.Add(t->LeftChild);
      if (t->RightChild) Q.Add(t->RightChild);
      try {Q.Delete(t);}
      catch (OutOfBounds) {return last;}
      }
}

(b): Each node of the binary tree is visited once and a constant amount of work is done during each visit. If the traversal is successful, the complexity is Theta(n), where n is the number of nodes in the binary tree.

(a): The code for ChangeMin is very similar to that for DeleteMin. The code is given below and in the files minheap4.*.


template<class T>
void MinHeap<T>::Initialize(T a[], int size, int ArraySize)
{// Initialize min heap to array a.
   delete [] heap;
   heap = a;
   CurrentSize = size;
   MaxSize = ArraySize;

   // make into a min heap
   for (int i = CurrentSize/2; i >= 1; i--) {
      T y = heap[i]; // root of subtree

      // find place to put y
      int c = 2*i; // parent of c is target
                   // location for y
      while (c <= CurrentSize) {
         // make c point to smaller sibling
         if (c < CurrentSize &&
             heap[c] > heap[c+1]) c++;

         // can we put y in heap[c/2]?
         if (y <= heap[c]) break;  // yes

         // no
         heap[c/2] = heap[c]; // move heap[c] up
         c *= 2;              // move c down a level
         }
      heap[c/2] = y;
      }
}

(b): Since a heap is a complete binary tree, the height of a min heap that has CurrentSize = n elements is Theta(log n). The change min algorithm spends constant time at a level and goes through at most as many levels as the height of the min heap. So the complexity is O(log n).

(a)
Since S _n = 1 + alpha/2 <= 7, alpha <= 12
Also, since U _n = (1 + alpha)/2 <= 12, alpha <= 23.
So alpha <= min{12, 23} = 12.
Hence n/b = alpha <= 12 and so b >= ceil(n/12) = ceil(81/12) = 7.

When division is used, the number of buckets equals the divisor D. So D >= 7. Also since D should be a prime number or should have no prime divisors less than 20, we choose D = 7, which is a prime number.

(b)
This is Lemma 8.1 in the book. See the proof of this lemma.
(c)
Examine the preorder output from left to right. In this order, the first element A is the root of the binary tree. Also A comes between the left and right subtree in inorder. So the left subtree is empy and BCDEFGHIJ is the inorder output of the right subtree. The next element in preorder D is the root of the left subtree unless the left subtree is empty (in which case it is the root of the right subtree). Using this information and what we have already learnt from the inorder sequence, we see that D is the root of the right subtree and BC are in the left subtree of D and EFGHIJ are in its right subtree. Proceeding in this way we can construct the entire binary tree. The unique binary tree from which the given inorder and preorder outputs came is:
```
                       A
                        \
                           D
                        /    \
                      B        J
                       \      /   
                         C   G      
                            / \       
                           F   H
                          /      \           
                         E         I
             
              
```

BACK