View difference between Paste ID: 1YkZA4NL and 9upa1Rf9

-/*
+
-Project 10.1
+
-Directions: Write a method that returns the minimum value in a 2-3-4 tree
+
 class Tree234
-Plan:
+
-- The 2-3-4 tree's minimum should ideally be the left most node's child (which will be a leaf)
+
-- ie. xxx
+
-     /   \
+
-   xxx    xxx
+
-   /        \
+
-  oxx       xxx
+
-  where o is the minimum value
+
            curNode = getNextChild(curNode, min);
-- return the min value, we should write a method that returns a long (value)
+
-- should just return the left most value
+
-- Node has a getMin() method that returns the item at the left most value (represents the smallest amount in current node)
+
-- if the parent at getMin() is not a leaf, go to the left child of that parent and call it again
+
-- stop once getMin() is actually at a leaf
+
-_ CANT FIGURE OUT HOW TO DO THIS
+
- */
+
       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