Tree234

////////////////////////////////////////////////////////////////
// An object of this class represents the entire tree
class Tree234
   {
   private Node root = new Node();            // make root node
// -------------------------------------------------------------
   // minimum value method
   public long minValue() {
       Node curNode = root; // current node = root
       long min = curNode.getMin();
       while(!curNode.isLeaf()) { // while current node is NOT a leaf
           curNode = getNextChild(curNode, min);
       } // end while
       return min;
   } // end minValue()
// -------------------------------------------------------------
   public int find(long key) // find data item with given key
      {
      Node curNode = root; // current node = root
      int childNumber; // reference to index of child
      while(true)
         {
          // we set childNumber to = the currentNode.findItem(key) which returns the index of the matching value
          // if the matching value is not found, findItem() returns -1
          // if childNumber is found, we return that index
         if(( childNumber=curNode.findItem(key) ) != -1)
            return childNumber;               // found it
         else if( curNode.isLeaf() ) // if the current node is a leaf, we can't go farther down
            return -1;                        // can't find it
         else                                 // search deeper, current node is not a leaf
            curNode = getNextChild(curNode, key); // figures out which of the node's children it should go to next
         }  // end while
      }
// -------------------------------------------------------------
   // insert a DataItem
   // like find, except it splits a full node if it finds one
   // goes until it finds a leaf node, then inserts data item into leaf
   public void insert(long dValue)
      {
      Node curNode = root;
      DataItem tempItem = new DataItem(dValue); // temp item used to safely store data

      while(true)
         {
         if( curNode.isFull() )               // if node full,
            {
            split(curNode);                   // split it up
            curNode = curNode.getParent();    // back up, current node now equals the current node's parent (one level up)
            curNode = getNextChild(curNode, dValue); // search once through the item array
            // we then find if the next child is greater than or less than the value given
            }  // end if(node is full)

         else if( curNode.isLeaf() )          // if node is leaf,
            break;                            // go to insert data item, break out of loop
         else          // node is not full, not a leaf; so go to lower level
            curNode = getNextChild(curNode, dValue); // after this executes, it returns to the first if statement
         }  // end while

      curNode.insertItem(tempItem);       // insert the new DataItem (when it is a leaf and has been split)
      }  // end insert()
// -------------------------------------------------------------
   // split is passed the node it will split
   public void split(Node thisNode)     // split the node
      {
      // assumes node is full
      DataItem itemB, itemC;
      Node parent, child2, child3;
      int itemIndex;
      // two right most items are removed from the node and stored
      itemC = thisNode.removeItem();    // remove items from
      itemB = thisNode.removeItem();    // this node
      child2 = thisNode.disconnectChild(2); // remove children
      child3 = thisNode.disconnectChild(3); // from this node

      Node newRight = new Node();       // make new node, goes to the right of the node being split

      if(thisNode==root)                // if this is the root,
         {
         root = new Node();                // make new root
         parent = root;                    // root is our parent
         root.connectChild(0, thisNode);   // connect to parent
         }
      else                              // this node not the root
         parent = thisNode.getParent();    // get parent

      // deal with parent
      itemIndex = parent.insertItem(itemB); // item B is inserted in the parent node
      int n = parent.getNumItems();         // total items?

      for(int j=n-1; j>itemIndex; j--)          // move parent's
         {                                      // connections
         Node temp = parent.disconnectChild(j); // one child
         parent.connectChild(j+1, temp);        // to the right
         }
                                   // connect newRight to parent
      parent.connectChild(itemIndex+1, newRight);

      // deal with newRight
      newRight.insertItem(itemC);       // item C to newRight
      newRight.connectChild(0, child2); // connect to 0 and 1
      newRight.connectChild(1, child3); // on newRight
      }  // end split()
// -------------------------------------------------------------
   // gets appropriate child of node during search for value
   // we put in a parent node, and a value which will determine which child we pick
   // we will either pick the right child of a value, or the left child depending on which is greater
   public Node getNextChild(Node theNode, long theValue)
      {
      int j;
      // assumes node is not empty, not full, not a leaf
      int numItems = theNode.getNumItems();
      for(j=0; j<numItems; j++)          // for each item in node
         {
         if( theValue < theNode.getItem(j).dData ) // is the value given less than the value at the first index of the array?
            return theNode.getChild(j);  // if so, return left child so we can use it at another point in time
         }  // end for                   // otherwise, our value is greater we're greater, so
      return theNode.getChild(j);        // we return right child (the child right after the value given, greater)
      }
// -------------------------------------------------------------
   public void displayTree()
      {
      recDisplayTree(root, 0, 0);
      }
// -------------------------------------------------------------
   private void recDisplayTree(Node thisNode, int level,
                                              int childNumber)
      {
      System.out.print("level="+level+" child="+childNumber+" ");
      thisNode.displayNode();               // display this node

      // call ourselves for each child of this node
      int numItems = thisNode.getNumItems();
      for(int j=0; j<numItems+1; j++)
         {
         Node nextNode = thisNode.getChild(j);
         if(nextNode != null)
            recDisplayTree(nextNode, level+1, j);
         else
            return;
         }
      }  // end recDisplayTree()
// -------------------------------------------------------------\
   }  // end class Tree234