Comp 212 Lab 14: B-Tree Insertion Algorithm

The main purpose of this lab is to write the insertion algorithm for the TreeN structure that will maintain its height balance and thus making it a B-tree.  Before we embark on this task, let's start with an easy warm up exercise.

Warm up exercise

Write a ATreeNAlgo visitor to check the host TreeN for emptiness.

Height-balance Insertion Algorithm

Here is the stub code for you to fill out.

package treeNAlgo;

import treeN.*;

/**
 *  InsertNAlgo  -  inserts the supplied parameter (key) into a TreeN
 *  preserving balance with a maximum number of elements per node.
 */
public class InsertNAlgo extends ATreeNAlgo {

  /**
   * Splits host upwards if its state > order and splices it into
   * its parent.    The supplied param is an ISpliceCmd used to do the
   * splicing.
   */
  private SplitUpAndSplice splitUpAndSplice;

  /**
   *
   * @param order -- the max possible number of elements in a node
   */
  public InsertNAlgo(int order) {
    splitUpAndSplice = new SplitUpAndSplice(order, noOpHostCmd);
    addCommand(new ICommand() { // for Empty case
      /**
       * @param n an Integer to be inserted into the host.
       */
      public Object apply(int idx, TreeN host, Object n) {
        return // STUDENT TO WRITE CODE
      }
    });

    setDefaultCmd(new ICommand() {  // for Non-empty case
      public Object apply(int idx, final TreeN host, final Object n) {
        host.execute(new ATreeNAlgo() {
          {
              final ATreeNAlgo me = this;
              //empty case: instantiate new tree and splice into parent
              addCommand(new ICommand() {
                  /**
                   * At this point the host is an empty subtree of some parent
                   * tree. Because the parent tree is balanced, it must be a
                   * leaf!
                   * @param h an empty subtree of some parent tree.
                   * @param cmd an ISpliceCmd
                   */
                  public Object apply(int idx, TreeN h, Object cmd) {
                    return // STUDENT TO WRITE CODE
                  }
              });

              setDefaultCmd(new ICommand() {
                /**
                 * For all non-empty trees.
                 * @param idx - state of the host
                 * @param host - a TreeN
                 * @param cmd - an ISpliceCmd
                 * @return TreeN
                 */
                public Object apply(int idx, final TreeN h, final Object cmd) {
                  final int[] x={0};  // trick to get past restrictions on final
                  // x[0] is the index of insertion location.
                  for(; x[0] < idx; x[0]++) {// find insertion location
                    int d = h.getDat(x[0]).intValue();
                    if (d >= ((Integer)n).intValue()) {
                      if (d == ((Integer)n).intValue())
                          return h; // no duplicate keys allowed
                      else break;
                    }
                  }
                  h.getChild(x[0]).execute(me, new ILambda() {
                    /**
                     * @param child a TreeN subtree of h.
                     */
                    public Object apply(Object child){
                      // splice child tree into parent
                      return // STUDENT TO WRITE CODE
                    }
                  });
                    // split up host if necessary
                    return // STUDENT TO WRITE CODE
                }
              });
            }
          }, new ILambda() {// NO-OP COMMAND AS THE PARAMETER FOR THE FIRST CALL TO THE HELPER FROM THE ROOT NODE
              /**
               * @param child not used.
               */
              public Object apply(Object child){
                return host;  //no-op for this one
              }
          });
        return host;
      }
    });
  }
}

 

Before writing any code, download the following GUI test program: SBTGUI.jar and run it to see its behavior.  The command to run this program is:

java -classpath .:SBTGUI.jar t234Client.Application1

Now, create a subdirectory called sbt and copy SBTGUI.jar to sbt.

Go to sbt and extract SBTGUI.jar via the command: 

jar -xfv SBTGUI.jar

You will see a subdirectory structure containing all the needed class files to run the GUI program.  In particular, you will see the class files for the insertion algorithm in the subdirectory treeNAlgo.  These files all have the prefix InsertNAlgo. When you edit and compile the above stub code, the compiler will generate new InsertNAlgo class files and overwrite the existing ones.

To run the GUI application, enter the command:

java t234Client.Application1

ENJOY!