Data Structures, Algorithms, & Applications in Java
Chapter 15, Exercise 25

(a)

The code for removeGreaterThanOrEqual is obtained by combining the code for getGreaterThanOrEqual, which finds the element that is to be deleted, with the portion of the code of remove, which deletes an element once we know which node it is in. The resulting code is given below.

---

public class ExtendedDBinarySearchTree extends DBinarySearchTreeWithGE
{
   /** @return and delete/remove element with smallest key >= theKey
     * @return null if no element has key >= theKey */
   public Object removeGreaterThanOrEqual(Object theKey)
   {
      // first find the element to delete
      BinaryTreeNode q = root,     // search pointer
                     pq = null,    // parent of q
                     p = null,     // pointer to node with smallest
                                   // key >= theKey found so far
                     pp = null;    // parent of p
      // search the tree
      while (q != null)
      {
         // is q a candidate?
         if (((Data) q.element).key.compareTo(theKey) >= 0)
         {// yes, q is a candidate
            p = q;  // q is a better candidate than old p
            pp = pq;
            // smaller keys (better candidates) in left subtree only
            pq = q;
            q = q.leftChild;
         }
         else
         {// no, q.key too small, try right subtree
            pq = q;
            q = q.rightChild;}
         }
   
      if (p == null)
         // no element has key >= theKey
         return null;
   
      // save smallest element with key >= k
      Object theElement = ((Data) p.element).element;
   
      // proceed to delete this element from the tree
   
      // handle case when p has two children
      if (p.leftChild != null && p.rightChild != null)
      {// two children
         // convert to zero or one child case
         // find element with largest key in left subtree of p
         BinaryTreeNode s = p.leftChild,
                        ps = p;  // parent of s
         while (s.rightChild != null)
         {// move to larger element
            ps = s;
            s = s.rightChild;
         }
   
         // move largest element from s to p
         p.element = s.element;
         p = s;
         pp = ps;
      }
   
      // p has at most one child, save this child in c
      BinaryTreeNode c;
      if (p.leftChild == null)
         c = p.rightChild;
      else
         c = p.leftChild;
   
      // remove node p
      if (p == root) root = c;
      else
      {// is p left or right child of pp?
         if (p == pp.leftChild)
            pp.leftChild = c;
         else
            pp.rightChild = c;
      }
   
      return theElement;
   }
}

(b)

With the availability of the method removeGreaterThanOrEqual, we can combine the the invocations of getGreaterThanOrEqual and remove made in Program 15.12 into a single step. The modifed version of bestFitPack is given below. Changes from the original are shown in red. A test program, input, and output are given in the files BestFit2.*.

---

public class BestFit2
{
   // top-level nested class
   public static class BinNode
   {
      // data members
      int id,             // bin identifier
          unusedCapacity;

      // constructor
      public BinNode(int theId, int theCapacity)
      {
         id = theId;
         unusedCapacity = theCapacity;
      }
   }
   
   /** output best fit packing into bins of size binCapacity
     * @param objectSize[1:objectSize.length-1] are the object sizes */
   public static void bestFitPack(int [] objectSize, int binCapacity)
   {
      int n = objectSize.length - 1;    // number of objects
      int binsUsed = 0;
      ExtendedDBinarySearchTree theTree;  // tree of bin capacities
      theTree = new ExtendedDBinarySearchTree();
      
      // pack objects one by one
      for (int i = 1; i <= n; i++)
      {// pack object i
         // find best bin
         BinNode bestBin = (BinNode) theTree.removeGreaterThanOrEqual
                               (new Integer(objectSize[i]));
         if (bestBin == null)
            // no bin large enough, start a new bin
            bestBin = new BinNode(++binsUsed, binCapacity);
      
         System.out.println("Pack object " + i + " in bin " + bestBin.id);
   
         // update unused capacity and put bin
         // in tree unless unused capacity is zero
         bestBin.unusedCapacity -= objectSize[i];
         if (bestBin.unusedCapacity > 0)
            theTree.put(new Integer(bestBin.unusedCapacity), bestBin);
      }
   }
}

(c)

The new code will run faster because we have eliminated the front part of remove which searched for the element that is to be deleted.