i can comile my B+ Tree program but i can't run it ...
Any help can be appricated
From output ... About to add key 1 Exception in thread "main" java.lang.NullPointerExceptio at BTree$BTreeNode.split(BTree.java:695) at BTree$BTreeNode.access$400(BTree.java:336) at BTree.add(BTree.java:195) at BTreeTest.main(BTreeTest.java:33)
i suspected the error is in split method of the BTreeNode class my program source...
/** * Class BTree is an implementation of the B+ version of B-trees. * <p/> * This class is provided as a skeleton class for Assignment 5 in Objects and Algorithms. * <p/>Implementation Details: * <p>For the assignment you need to: * <ol> * <li>Complete sufficient of the classes BTree and BTreenode add (key+data) pairs to the B-Tree * and to search the B-Tree bykey. * <li>Add to the classes BTree and BTreeNode the links in the leaf nodes of the tree needed to enable * the provided iterator class to function correctly. * <li>For bonus marks, add the functionality to the classes BTree and BTreeNode for the delete operation to work. * </ol> * You should only need to modify code that has been removed from my initial solution to this problem. * <p>Comments have been provided in the JavaDoc to assist you in implementing this assignment. Read through * the code provided in conjunction with the assignment document. * <p>Plan before you change things, and make sure you keep backup copies of your code at various points - it is * easy to make changes that introduce errors into code that previously seemed to work. * <p>The test program may not print everything out that you need to work out where your code is going wrong - you may * need to print out additional information when getting your classes to work. * <p>When you are modifying the code, <b>DRAW DIAGRAMS</b> and make sure you understand what changes you need to * make to the nodes of the B-Tree (and the B-Tree object itself) before you code up. <b>You can't simply start * adding code without doing any planning.</b> Even if you have not need to plan much in previous assignments, for * data structures such as this you need to understand the changes you are going to make the data structure in detail * before you code. * * @author a.sobey * @version 1.0 */ public class BTree { /** * The order of the B-Tree. All nodes of the B-Tree can store up to 2*order key values. */ private int order; /** * The number of key (with associated data values) stored in the B-Tree. */ private int count; /** * The root node of the B-Tree */ private BTreeNode root; /** * The first leaf node in the B-Tree. This field is used to give the starting point for sequential * access to the keys and data stored in the leaf nodes. */ private BTreeNode first; /** * The last leaf node in the B-Tree. This field is used to give the starting point for reverse * sequential access to the keys and data stored in the leaf nodes. */ private BTreeNode last; /** * A change count that can be used to invalidate iterators. This field is updated whenever a key plus data pair * is added to the B-Tree (or the data associated with a key is changed), or when a key plus data pair are * deleted from the B-Tree. */ private int changeCount = 0;
// // WHEN DOING ASSIGNMENT 5, DO NOT ADD ANY ADDITIONAL FIELDS TO THIS CLASS // You will loose marks if you add additional fields to this class. The fields above are all that // you need. If you need a variable in a method, use a local variable. I have seen too many // assignments where students add fields rather than create local variables. Hopefull the threat // of loosing (quite a few) marks will help reduce this habit. //
/** * A general exception class for errors when constructing or manipulating a B-Tree. Use the string * parameter to the constructor to say what the error really is. */ public class BTreeError extends RuntimeException { public BTreeError(String reason) { super(reason); } }
/** * A constructor that creates an empty B-Tree of the given order. * <p/>This is the only constructor provided at the moment for this BTree class. Could consider * adding the equivalent of a 'copy constructor' that creates a new BTree object from an existing * BTree object.Constructor * creates the root of a btree */
/** * A constructor that creates an empty B-Tree of the given order. * <p/>This constructor need to copy the order parameter to the field of same name, and initialise the * root, cound, first and last fields of the BTree object. * * @param order The order of the BTree. */ public BTree(int order) { count = 0; this.order = order; root = new BTreeNode(true, null, -1, null, null); first = root; last = root; }
/** * A method to return a SequentialIterator object that is positioned just before the first key * of the BTree object. * <p/>Do not modify this method. * * @return A SequentialIterator object. */ public SequentialIterator iterator() { return new BTreeIterator(); }
/** * A mehtod to return a SequentialIterator object that is positioned at a key found through a call * to the searchFor() method. * <p/>Do not modify this method. * * @param position A SearchPosition() object that usually has been returne by a call to the searchFor() method. * @return A SequentialIterator object initialised to start at particular key in the BTree. */ public SequentialIterator iterator(SearchPosition position) { return new BTreeIterator(position); }
/** * A method to return a string representationo the BTree. * <p>The format of the string is: * <pre>BTree: Order=<digits>, size=<digits>, root=<BTreeNode string></pre> * <p/>Do not modify this method. * * @return A string to represent the BTree */ public String toString() { StringBuffer s = new StringBuffer("BTree: Order="); s.append(order).append(", size=").append(size()).append(", root=").append(root.toString()); return s.toString(); }
/** * Method to determine the number of records stored in the B-Treee. * <p/>Do not modify this method * * @return the number of records in the B-Tree. */ public int size() { return count; }
/** * method to return the order of the B-Tree. * <p/> * <p>This is the smallest number of key values for all nodes * except the root node. The maximum number of key values in a node is 2*order, and the maximum number * of child nodes for a node is 2*order+1. * <p/>Do not modify this method. * * @return The order of the B-tree. */ public int order() { return order; }
/** * Insert a key plus data value into the BTree. * <p/>This method needs to locate the leaf node in which the key + data value should be * inserted, and then call the insertLeaf() method of BTreeNode to do the insertion. * <p/>This method will always result in a change to the BTree, so it should increment * the change count. * <p/>The method may result in only the data associated with an existing ke being changed, * so incrementing the count field should be done in the BTreeNode method (if needed). * <p/>This is one of the method you need to complete for assignment 5. * * @param key The key associated with the data value to be added to the B-Tree * @param data The data value to be added (with it's associated key) to the B-Tree. */
public void add(Comparable key, Object data) { // you need to add the code for this method
// i added BTreeNode btNode = root; while (!btNode.isLeaf) { int i=0; while(key.compareTo(btNode.keys) > 0) { i++; if (i == btNode.numberOfKeys) break; } btNode = btNode.childNodes; } btNode.insert(key,data); if (root.numberOfKeys == order*2-1) root.split(order); }
/** * insert a object with the given key into the tree */ /** { //KeyNode keyNode = new KeyNode(key, data);
// BTreeNode keyNode = new BTreeNode(key,data);
BTreeNode btNode = root; while (!btNode.isLeaf) { int i=0; while(key.compareTo(btNode.key(i)) > 0) { i++; if (i == btNode.numberOfKeys())
if (root.numberOfKeys == order*2-1) { System.out.println("hmm3"); root.split(order);
System.out.println("hmm4");
} }
}**/ /** * This method searches the B-Tree for an occurence of the key in a leaf node and returns the result * of the search in a SearchPosition object. * <p/>Note that the key may occur in an interior node of the BTree without occuring in the leaf * nodes. This can be the result of a deletion operation. This method need to search down to the * leaf node that should contain the key if the key and associated data is in the B-Tree, and then * scan through the keys in the leaf node for the search key. * <p/>The result of the search is returned as a SearchPosition object, as this allow the return * of the success or failure of the search, as well as the data belonging to the key. It also * allows position information to be returned so that an interator can be initialised with the * key as the starting position for subsequent sequential access to adjacent keys. * <p/>This is one of the method you need to implement. * <p/>Implementation nodes:<br> * You need to find the leaf node that may contain the key (same code as for add()), then * scan the leaf BTreeNode for the search tree. You can do this within this method, as you * have total access to the fields and methods of BTreeNode (as BTreeNode is an inner class * of BTree). If you find the key, construct and return a SearchPosition object with the appropriate * details of the position, otherwise construct add return a SearchPosition object that indicates the * search failed. * @param key The key to search for in the BTree * @return A SearchPosition object returning the data and position information for the search */
public SearchPosition searchFor(Comparable key) { // // You need to add the code for this method. The code below simply creates a // SearchPosition object which indicates an unsuccessful search. // return new SearchPosition(false, null, -1); }
/** * A method to delete a node from the BTree. * <p/>The method should return the data object that was deleted when the key plus data object pair * are deleted from the B-tree. * <p/>The method should throw a BTreeError exception (with an appropriate reason string) if the * key is not found in the B-tree. * <p/>This is a method you can implement for bonus marks in Assignment 5. * <p/>Implementation notes:<br> * The easiest way to proceed is to use searchFor() to determine if they key is in the BTree, and * (if it is in the B-tree) to return position information about the key. Throw an exception if the * key is not in the B-tree, otherwise keep a copy of the data assocaited with the key (to return), * then for the leaf node containing the key (a BTreeNode object), call the deleteLeafNodeKey() method, * passing across the leaf key index of the key (so you don't have to find it again in the leaf node). * After this method deletes the key, return the data you saved as the method result. * * @param key The key to delete (along with it's associated data) from the B-tree. * @return The data associated with the key that was deleted. */ public Object delete(Comparable key){ // // You need to add the code for this method. // return null; }
/** * The inner class BTreeNode is used to represent the nodes in the B-Tree. * * <p/>The nodes in the BTree are of two types: * <ol> * <li>Leaf nodes that contain the keys and associated data values, stored in ascending key order.<br> * These leaf nodes have next and previous pointers to adjacent leaf nodes to allow an easy * implementation of an iterator class to provide bi-directional sequential access to the keys stored * in the BTree nodes. * <li>Interior nodes that contain keys and links to child nodes (that are either all internal nodes * or all leaf nodes), organised as the node of a multi-way search tree. The interior nodes have * one more child node link than keys. The child node link at index k is to a node with keys that * are all less than the key at index k in this node. The link at index k+1 is to a child node * with keys that are all greater than or equal to the key at index k. * </ol> * The BTreeNode class allows you to create these two 'types' of nodes, depending on the parameters * passed to the constructor. * <p/>There are methods that should only be called for leaf nodes and methods that should only be * called for interior nodes. These methods should throw an exception if called by the wrong node * type. This class should really be designed using inheritance to mimic the pascal/C++ variant * record structure, but this design is relatively easy to understand and to implement. * <p/>Note that this class is an inner class of BTree, and so all objects will have an implict * reference to the BTree container object. This class has direct access to all the fields of the * BTree contaner object. In particular, the order of the BTree is available, hence this class * does not need to keep a copy of the order as a field. * <p/>Skeleton class provided for Objects and Algorithms Assignment 5 * <p/>Only modify the methods where the JavaDoc indicates that you need to provide code. * * @author a.sobey * @version 1.0 * Date: 16/05/2005 */ public class BTreeNode { /** * The actual number of key values stored in the BTreeNode. <br>Note that the BTree node has an implicit * reference to the containing BTree object, and the maximum number of nodes that can be stored in a * a BTreeNode (except temporarily during the split operation) is twice the <i>order</i> of the BTree.<br> * This field is valid for both internal and leaf nodes. */ private int numberOfKeys = 0; /** * The array of pointers to child nodes of this node. Only <i>(numberOfKeys+1)</i> are valid if <i>numberOfKeys</i> * is non-zero.<br> * This array is only valid and created for internal nodes - this array is not created for leaf nodes.<br> * There is space in the array created for one additional child node link - this makes the coding for * splitting of an internal node easier to implement. */ private BTreeNode[] childNodes; /** * A reference to the parent node of this node.<br> * This link is null if this node is the root node of the tree of BTreeNodes.<br> * This node is valid for both internal and leaf nodes. */ private BTreeNode parent; /** * The index in the parent node's array of links (the <i>childNodes</i> array) for the link to this node.<br> * This value should be set to -1 if this node is the root node (and so has no parent node).<br> * This field is valid for both internal and leaf nodes. */ private int parentIndex; /** * A link to the next leaf node in the B-tree, provided to allow easy sequential access of the keys * and values stored in the B-tree.<br> * This field is only valid if the node is a leaf node. For non-leaf nodes set the value to null.<br> * For leaf nodes, set the value to null if this node is the last leaf node in the B-tree. */ private BTreeNode next; /** * The link to the previous leaf node in the B-tree, provided ot allow easy reverse sequential access of the keys * and values stored in the B-Tree.<br> * This values should be set to null if this node is a leaf node but is the first leaf node in the B-Tree, or * if this node is not a leaf node.<br> * This field is only used in leaf nodes. */ private BTreeNode previous; /** * An array of comparable key objects that are stored in this node of the B-tree.<br> * Only the first <i>numberOfKey</i> values in the array are valid.<br> * The maximum number of keys in a node is 2*<i>order</i>, however there is space in this array * for one additional value to make the coding of the node splitting operation easier to implement.<br> * This field is valid for both internal and leaf nodes. */ private Comparable[] keys; /** * An array of data values associated with the keys stored in this leaf node of the B-tree.<br> * Only the first <i>numberOfKey</i> values are valid.<br> * The maximum number of data values in a node is 2*<i>order</i>, however there is space in this array * for one additional value to make the codingof the leaf node splitting operation easier to implement.<br> * This field is only valid for leaf nodes - for interior nodes this array is not created. */ private Object[] data; /** * A boolean value to indicate if the node is a leaf node or not. The structure of the remainder of the node * depends on this value (would be nice to have variant records in Java ...).<br> * This field is valid for both leaf and internal nodes. */ private boolean isLeaf;
// // WHEN DOING ASSIGNMENT 5, DO NOT ADD ANY ADDITIONAL FIELDS TO THIS CLASS // You will loose marks if you add additional fields to this class. The fields above are all that // you need. If you need a variable in a method, use a local variable. I have seen too many // assignments where students add fields rather than create local variables. Hopefull the threat // of loosing (quite a few) marks will help reduce this habit. //
private int order; /** * The constructor for a BTreeNode. * <p/>The code for the constructor is provided - do not modify this constructor. * * @param isLeaf True if this node is a leaf node. * @param parent A link to the parent node or null if this node is the root node of the B-Tree * @param parentIndex The index of the link in the array of child node linkes in the parent node that points to this node. * @param previous A link to the previous leaf node for sequentail access, or null if not a leaf node or no previous leaf nodes. * @param next A link to the next leaf node for sequential access, or null if not a leaf node or the last leaf node. */ public BTreeNode(boolean isLeaf, BTreeNode parent, int parentIndex, BTreeNode previous, BTreeNode next) { this.parent = parent; this.parentIndex = parentIndex; this.previous = previous; this.next = next; this.isLeaf = isLeaf; if (isLeaf) data = new Object[2 * order + 1]; else childNodes = new BTreeNode[2 * order + 2]; keys = new Comparable[2 * order + 1];
}
public BTreeNode( int order, BTreeNode parent) { this.order = order; this.parent=parent; this.keys = new Comparable[2*order-1]; this.data = new Object[2*order-1]; this.childNodes=new BTreeNode[2*order]; this.isLeaf=true; }
/** * Returns the number of keys in this BTreeNode. Note that within the code in BTree you have access * to all the fields of BTreeNode, so this method is not strictly necessary. * @return The number of keys in this BTreeNode object. */ public int numberOfKeys() { return numberOfKeys; }
/** * Returns the container BTree object for this BTreeNode object. You may like to check that container objects * are the same when manipulating two BTreeNode objects. * @return the containing BTree object. */ public BTree container() { return BTree.this; }
/** * A private method to return a string representation of the array <i>keys</i>. This method is used in * the toString() method for this class.<br> * Do not modify the code provided for this method. * @return A string representation of this nodes array of keys. */ private String keyString() { StringBuffer s = new StringBuffer("{"); for (int index = 0; index < numberOfKeys; index++) s.append(index > 0 ? "," + keys[index] : keys[index]); return s.append("}").toString(); }
/** * A private method to return a string representation of the array of data values stored in a leaf node.<br> * This method is used in the toString() method of BTreeNode. The method does not check if this node is a * leaf node, as it is not intended to be called directly from outside of this class, and the toString() * method only calls this method if the node is a leaf node.<br> * Do not modify the provided code for this method. * @return a string representation of the data values array of a BTreeNode. */ private String dataString() { StringBuffer s = new StringBuffer("("); for (int index = 0; index < numberOfKeys; index++) s.append(index > 0 ? "," + data[index] : data[index]); return s.append(")").toString(); }
/** * A private method to return a string prepresentation of the array of child node links in an interior node.<br> * This method is used in the toString() method. This method does not check if this node is an interior * node, so you must take care to only call this method for interior nodes.<br> * Do not modify the provided code for this method. * @return A string representation of the array of child nodes of this BTreeNode. */ private String childString() { StringBuffer s = new StringBuffer("<"); for (int index = 0; index < numberOfKeys + 1; index++) s.append(childNodes[index] + (index == numberOfKeys ? "" : ",")); return s.append(">").toString(); }
/** * The toString method provides a string representation of a BTreeNode.<br> This particular method does not * include the details of all the fields of a BTreeNode. While debugging your code, you may like to include * more information (such as the parentIndex value), but in your final submission you must have the code * as provided in the skeleton BTreeNode class provided to you. * @return A string representation of a BTreeNode. */ public String toString() { if (isLeaf) return (new StringBuffer("[")).append(numberOfKeys) // .append(',').append(parentIndex) // uncomment this line if need to check parentIndex values .append(',').append(keyString()).append(',').append(dataString()).append(']').t oString(); else return (new StringBuffer("[")).append(numberOfKeys) //.append(',').append(parentIndex) // uncomment this line if need to check parentIndex values .append(',').append(keyString()).append(',').append(childString()).append(']'). toString(); }
/** * Returns the key with the given index in this node. Throws a BTreeError exception if the index is not valid.<br> * Do not modify this provided code. * * @param index The index of the key. * @return The key value at the given index. */ public Comparable key(int index) { if (index < 0 || index >= numberOfKeys) throw new BTreeError("Key index out of range - value = " + index); return keys[index]; }
/** * Returns the child node at the provided index into the childNodes array.<br> * A BTreeError exception is thrown if the node is not an internal * node or if the index is not valid. * <p/>Note that the child node returned will have keys that are all less than the key stored * in the <i>keys</i> array of this node at the given index value (except the last childNode * at index numberOfkeys, as this node has keys that are all greater than or equal to the last * key value stored in this node).<br> * Do not modify the provided code for this method. * * @param index The index into the array of child nodes for this internal BTreeNode object. * @return The child node link. */ public BTreeNode child(int index) { if (isLeaf) throw new BTreeError("child() called for a leaf node"); if (index < 0 || index > numberOfKeys) throw new BTreeError("Child node index out of range - value = " + index); return childNodes[index]; }
/** * Returns the data value associated with the key at the given index. An BTreeError exception is thrown if the * node is not a leaf node or if the index is invalid. * <p/>Do not modify the provided code for this method. * * @param index The index of the key assocaited with the data value. * @return The data value associated with the key with given index. */ public Object data(int index) { if (!isLeaf) throw new BTreeError("data() called for an internal node"); if (index < 0 || index >= numberOfKeys) throw new BTreeError("Data index out of range - value = " + index); return data[index]; }
/** * This method is used to determine if this node is a leaf node. * * @return True if this node is a leaf node. */ public boolean isLeaf() { return isLeaf; }
/** * Inserts the (key, data) pair into this BTreeNode object. * <p/>You must supply the code for this method. * <p/>Implementation notes:<br> * <ol> * <li>Throw an exception if this node is not a leaf node. * <li>Scan the keys array for index of the key greater than or equal to the insertion key. * <li>If the key at the index is equal to the insertion key, update the data field and return - you are done. * <li>Otherwise shuffle the keys values from the insertion index along to make a hole for the insertion key, * and insert the insertion key into the keys array. Do the same for the data array values to insert the * new data value into the data array at the insertion index. * <li>increment the number of keys, and increment the container BTree object's count field. * <li>If the number of keys in the node is now no more than 2*order, you are done, so simply return. * <li>Otherwise the node has (2*order+1) key values, and need to split. The split operation leaves the first * <i>order</i> keys and data values in this node (and so the node's numberOfKeys value will become * <i>order</i>, and moves the remaining (order + 1) keys and data values to a new BTreeNode leaf node * that you need to create.<br> * You need to fix up the previous and next fields of this leaf node and the new leaf node you have created.<br> * Two sub-cases: * <ol> * <li>If this node is the root node (i.e., it does not have a parent node), the split of this node will create * a new root node, with a single key (the key at index (order+1)) and this node and the new BTreeNode as * the child nodes. In my solution I used a call to the method newRootNode to do this. The newRootNode() * method will also be used when a split of an interior node creates a new root node. See the JavaDoc for * details of what the newRootNode() method should do. Once the new root node has been created, and all * the fields updated due to the split, you are done. * <li>Otherwise we need to insert in this node's parent node the middle key (at index (order+1) and the * new node that we created. This is done by the method insertInterior(). The method is passed the * key to insert (at location this.parentIndex in the keys array of the parent node), the index to * to insert the key (this.parentIndex), and the new leaf node (that will be inserted at index * (this.parentIndex+1) in the parent node's child links array). * </ol> * </ol> * * @param key The key to insert into the leaf node. * @param data The key's corresponding data value. */ public void insertLeaf(Comparable key, Object data) { // // You need to provide the code for this method. //
// BTreeNode temp = new int size = this.data.length; int counter = 0;
this.keys[size] = key; this.data[size] = data;
sort(size);
}
/**
public int compareTo(Comparable o2) { // Integer o1 = (Integer) o2; return (((Integer)o2).compareTo(this)); } **/
/** *split() *Splits a node into to nodes. This can only be done, if the node is full *The midlest key go up into the parent, the left ones of them rest in *this node, and the right ones go into a new node. **/ private BTreeNode split(int order) {
if (numberOfKeys == order*2-1) { BTreeNode right = null; if (parent == null) { // algo for the root-node BTreeNode left = new BTreeNode(order, this); right = new BTreeNode(order, this); for (int i=0; i<order-1; i++) { left.keys = keys; left.data = data; right.keys = keys[order+i]; right.data = data[order+i]; } if (!isLeaf()) { for (int i=0; i<order; i++) { left.childNodes = childNodes; left.childNodes.parent = left; right.childNodes = childNodes[order+i]; right.childNodes.parent = right; } left.isLeaf = false; right.isLeaf = false; } else isLeaf = false; keys[0] = keys[order-1]; numberOfKeys = 1; left.numberOfKeys = order-1; right.numberOfKeys = order-1; for (int i=1; i<order*2-1; i++) { keys = null; data = null; childNodes[i+1] = null; } childNodes[0] = left; childNodes[1] = right; } else { // algo for non-root-nodes if (parent.numberOfKeys == order*2-1) parent.split(order); int pos=0; while(keys[order-1].compareTo(parent.keys[pos]) > 0) { pos++; if (pos==parent.numberOfKeys) break; } parent.shift(pos); parent.keys[pos] = keys[order-1]; parent.data[pos] = data[order-1]; right = new BTreeNode(order, parent); for (int i=0; i<order-1; i++) { right.keys = keys[order+i]; right.data = data[order+i]; } if (!isLeaf) { for (int i=0; i<order; i++) { right.childNodes = childNodes[order+i]; right.childNodes.parent = right; } right.isLeaf = false; } right.numberOfKeys = order-1; numberOfKeys = order-1; for (int u=0; u<order-1; u++) { keys[order-1+u] = null; data[order-1+u] = null; childNodes[order+u] = null; } parent.childNodes[pos] = this; parent.childNodes[pos+1] = right; } return right; } else return null; }
/** private BTreeNode split(int order) {
// System.out.println(childNodes[0].childString()); if (numberOfKeys == order*2-1) { BTreeNode right = null;
if (parent == null) { // algo for the root-node
BTreeNode left = new BTreeNode(order, this); System.out.println("hmmm 1"); right = new BTreeNode( order, this); for (int i=0; i<order-1; i++) { left.keys = keys; left.data = data; System.out.println("hmmm 1.1"); right.keys = keys[order+i]; right.data = data[order+i]; } if (!isLeaf) { for (int i=0; i<order; i++) { left.childNodes = childNodes; left.childNodes.parent = left; right.childNodes = childNodes[order+i]; right.childNodes.parent = right; } left.isLeaf = false; right.isLeaf = false; System.out.println("hmmm 2");
/** *shift(int startPos) *Moves the key's at, and behind the startpos one position right **/ void shift(int startPos) { for (int i=numberOfKeys; i>startPos; i--) { keys = keys[i-1]; data = data[i-1]; if (!isLeaf) childNodes[i+1] = childNodes; } System.out.println(childNodes [1].childString()); numberOfKeys++; }
/** * method for sorting student records into ascending order according to * student name using inserting sort algorithmn * * codes template is from http://math.hws.edu/TMCM/java/xSortLab/ * copyright */
public void sort(int lineCount) { int in, out; lineCount--; for (out = 1; out < lineCount; out++) { // out is dividing line Comparable tempKey = keys[out]; // remove marked person Object tempData = this.data[out]; in = out; // start shifting at out
while (in > 0 && // until smaller one found, this.keys[in - 1].compareTo(tempKey) > 0) { this.keys[in] = this.keys[in - 1]; // shift item to the right this.data[in] = this.data[in - 1]; --in; // move left one position } this.keys[in] = tempKey; // insert marked item this.data[in] = tempData; } }
/** * A private method to create a new root node for the tree of BTreeNode objects. * <p/>The node that calles this method must currently be the root of the BTree. * <p/>This method needs to create a new empty root node, add the key passed up (by the split * of the current root) as the only key to this new root node (and set the numberOfKeys field to 1), * and add the previous root node and then right node created by the split as the two child node * links in the node.<br> * The child nodes of the new root node need to have their parent and parentIndex fields fixed. * <p/>You need to provide the code for this method. * * @param key The single key to initially store in the root node * @param right The link to the right child tree node created by the split of the old root node. */ private void newRootNode(Comparable key, BTreeNode right) { // // You need to provide the code for this method. // }
/** *insert(KeyNode keyNode); *Insert a key in a Node in the right position. (Small to Big) **/ public void insert(Comparable key,Object value) { if ( numberOfKeys == 0) { numberOfKeys++; keys[0] = key; data[0] = value; } else { int pos = 0; while (key.compareTo(keys[pos]) > 0) { pos++; if (pos == numberOfKeys) { break;
} } if (numberOfKeys == order*2-1) { BTreeNode right = split(order); if (pos > order-1) right.insert(key,value); else { if (pos != numberOfKeys)
/** * A method to insert a new key (and link to the child node containing the key) into an interior * node of the B-Tree. This method is only called when a node of the B-tree splits following an insertion. * The splitting of node passes a key and node link to insert in the parent node, which may itself split, and * so on. * <p/> You nened to provide the code for this method. * <p/>Implementation Notes: * <p>This method is only called when a child node of this node has split, passing up the middle key from the * split, along with the link to the new right BTreeNode created by the split.<br> * As nodes keep both a back link to their parent node <b>and</b> the index of the link to the node * in the parent's array of child node links, this method is passed the index into the array of child nodes * where the new child node's link needs to be inserted. * This means tht unlike the insertLeaf() method, you don't need to search for the correct locations in the * array of child nodes and array of keys to do the insertion.<br> * There is though the overhead that when links to * child nodes are moved in the array of child nodes, the child node's parentIndex has to be updated. * <p>The <i>insertIndex</i> that is passed in will be the index in the array of child node links for * the subtree that contains the <i>key</i> being inserted. This means that the <i>key</i> should be * inserted at index <i>(insertIndex-1)</i>. * <p>Note the value of <i>insertIndex</i> can never be zero, as when a node splits, the new node * inserted is always to the right of an existing node. The maximum valid value for <i>insertIndex</i> is * <i>(numberOfKeys+1)</i>, when the new <i>key</i> will be inserted at index <i>numberOfKeys</i> * (at the end of the current list of keys). * <p/>Some details: * <ol> * <li> Check preconditions - this node must be an interior node, and the insertIndex must be valid. * <li> You are adding a key and child node pointer to this node - it may cause the node to split, but * there is room to add the key and child node link the correct location first, and then (if needed) * do the split. This is same strategy as used for insertion into a leaf node.<br> * When inserting, need to move key array values and childNode array values to make room for the * new key and child node pointer. The indices of the values to be moved for these two arrays differ * by 1. Don't forget to fix up the parentIndex of child nodes that are moved. * <li> After insertion of the key and child node link, if the node is not full, you are done. * <li> Otherwise, you need to split this node into two, and insert the new middle key upwards along with * a link to the new BTreeNode object that you create. Some difference to the code to what you did * when splitting a leaf node: * <ol> * <li> The new BTreeNode will be an interior node. * <li> The middle key is not added to the new right node, but only pushed up to the parent node. Both * <i>this</i> node and the new right node will have <i>order</i> keys after the split. * <li> The child node pointers that you move across to the new right node need to have their nodes * <i>parent</i> and <i>parentIndex</i> fields fixed. * <li> You don't need to fix up <i>previous</i> and <i>next</i> fields, as these are only used to * link leaf nodes together. * </ol> * <li> The passing up of the middle key and right node link is identical to what is done for splitting * a leaf node. This includes what you do if this node that you are splitting is the root node. * </ol> * * @param key The key that is being pushed up from a split of a child node. This is first key value in the new child node. * @param insertIndex The index into the childNode list for the link to the new child node. * @param newChild The new child node. */ private void insertInterior(Comparable key, int insertIndex, BTreeNode newChild) { // // You need to provide the code for this method. // }
/** * A method to delete a key and associated data value from a leaf node. * <p/>The implementation of this method is optional - it is worth bonus marks, but you can * obtain full marks for the assignment without implementing the delete() related methods. * <p/>If you do decide to implement delete(), be aware that it is more difficult than * the insertion code, and you will need to work out carefully (with diagrams to help you) * what you need to do before you code these methods up. * <p/>Implementation Notes:<br> * <ol> * <li> Check the preconditions are satified - the node must be leaf node and the key must be in the correct * range. * <li> Start by deleting the key and data values. Do this by shuffling the keys and data values after the * insert index to the left by 1. Decrement the number of keys, increment the change count and the BTree * object's count. * <li> If this node is the root node, or if the number of keys remaining is at least order, you are done. * <li> Otherwise the nubmer of keys in the node should be (order-1). The node is underfull, and you need * to either: * <ol> * <li> Take a key from a node with the same parent node that is adjacent to this node, if the adjacent * node has at least (order+1) key values, or * <li> Merge this leaf node with a leaf node that is adjacent and has the same parent. The adjacent * leaf node will have exactly order keys, and the merged node will have (2*order-1) keys. * </ol> * <li> The first thing you need to do is find the adjacent leaf nodes with the same parent. There may only * be one, but there will be at least one. * <li> If at least one of these nodes has more than <i>order</i> keys, can take a key from the node, leaving * both this node and the other node with at least <i>order</i> keys. You are then done. There are two * sub-cases: where you take from the left adjacent node and from the right adjacent node. * <ol> * <li>If you are taking from the left node, the work is done by a call to getKeyFromLeftNode().<br> * The last key of the left node is moved. As it becomes the smallest key in the underfull node, * it also has to be moved up to the parent node (to the index equal to the parentIndex of the * left node). * <li>If you are taking from the right node, call getKeyFromRightNode(), which makes the first key * of the right node the last key of this node. This method also moves the smallest key of the * right node up to this node's parentIndex position in the parent node. (see * getKeyFromRightNode() for more details). * </ol> * <li> Otherwise we need to merge this node with either a left or right adjacent node with the same parent. * I used a method mergeWithLeafNode() to do the merge. Any adjacent leaf nodes with the same parent * node as this node must have exactly <i>order</i> keys (otherwise would have taken a key from the * adjacent node to avoid a merge). In my implementation of the mergeWithLeafNode method, the method * checks to see if a left node with the same parent exits, and if so merges with it, otherwise * merges with the right adjacent node (which, if there is not a left node, must have the same parent). * The merge method can use the next and previous links to find the adjacent nodes. * </ol> * @param keyIndex The index in the array of keys and array of data values of the key and * associated data value that are to be deleted. */ public void deleteLeafNodeKey(int keyIndex){ // // You need to provide the code for this method. // } /** * A method to get a key from an adjacent left leaf node with the same parent that has more * than <i>order</i> keys, to give this node exactly <i>order</i> nodes. * <p/>You only need to implement this method if you are implementing the delete() operation. * <p/>Implementation notes: * <ol> * <li> Check preconditions (this node is a leaf node, the previous node exists and has the same parent, * and this node has (order-1) nodes while the previous node has at least (order+1) nodes. * <li> Make a space at the start of the key and data arrays of this node for the new key and data values. * <li> Copy the last key from the left node to the spaces you created. * <li> Fix up the key at (parentIndex-1) location in the parent node (should be set to the key that was * moved to the start of this node's key array) * <li> Fix up sizes of the left node and this node. */ private void getKeyFromLeftNode(){//(BTreeNode right){ // // You need to provide the code for this method. // }
/** * A method to get a key from the right adjacent leaf node to this node. * <p/>You only need to implement this method if you are implementing the delete() operation. * <p/>Implementation Nodes:<br> * Similar to getKeyFromLeftNode, except you get the key from the first location of the right node, * have to shuffle the remaining key and data values to the left in the arrays in the right node, * and the key and data value that you move to this node are added to the end of the current values in * the key and data arrays of this node. */ private void getKeyFromRightNode(){ // // You need to provide the code for this method. // }
/** * A method to merge this node with an adajcent node that has the same parent. * <p/>This is a method you need to implement to get the delete() operation working for bonus marks. * <p/>Implementation notes: * <p/>This method should only be called once it is known that adjacent nodes with the same parent * don't have any spare keys (they will have exactly <i>order</i> keys).<br> * This method should check to see if there is an adjacent left leaf node with the same parent. If so * <ol> * <li> Set a left leaf node pointer to this left leaf node, and a right leaf node pointer to * this node (use the previous link), else * <li> Set the left leaf node pointer to this node, and the right leaf node pointer to this node * (use the next link). * </ol> * Now using the left and right pointers: * <ol> * <li> copy all the keys and data values from the right node to the end of the arrays in the left node. * <li> fix the left node's numberOfKeys field * <li> Fix the left node's <i>next</i> pointer, and the next node's previous pointer. * <li> Call the method deleteInternalNodeKey() with the left node's parentIndex to remove a key from the * merged node's parent node (which has to be an internal node). * <ol> */ private void mergeWithLeafNode(){ // // You need to provide the code for this method. // }
/** * This is a method to remove the key at a given indexs into the keys array of an interior BTreeNode object. * <p/>You only need to implement this method if you are trying to implement the delete operation. * <p/>Implementation notes: * <ol> * <li>When you delete a key from an interior node, you also need to delete the associated link to a * child node. If you delete the key with index k, you need to delete the child link with index (k+1). * <li>When you shuffle the childNode array elements (to delete the child node at index (keyIndex+1), you * need to ensure the child node's parentIndex is updated correctly. * <li>Done if after the deletion, this node is not empty and either the root node or has at least (order+1) keys. * <li>If this node was the root node and is empty after deletion, the root node becomes the child node at * index 0 (and this node is discarded). * <li>Otherwise have a node with (order-1) keys, and can fix (as with leaf node), by taking a key from an * adjacent node with the same parent that has at least (order+1) keys, or by merging with an adjacent * node with the same parent (which will have exactly <i>order</i> keys). Merging will propagate upwards * the removal of a node from an interior node. The movement of a key from an adjacent node and the * merging of adjacent nodes is performed by the private methods rotateKeyFromLeftInteriorNode(), * rotateKeyFromRightInteriorNode(), and mergeWithInteriorNode(). See the JavaDoc for these methods for * more details. * </ol> * @param keyIndex The index in the keys array of the key to delete. */ private void deleteInteriorNodeKey(int keyIndex){ // // You need to provide the code for this method. // }
/** * Add a key to this interior node by rotation from left node. * * <p/>The key at (this.parentIndex-1) in this node's parent node is moved to the first location in * this node (existing keys and child node pointers moved along 1 to right in their arrays), and the last * key in the left node is moved to the vacant location in the parent node. * <p/>The last child node link in the left node is moved to the first child node link position in this node. * * @param left The left interior node for the rotation. */ private void rotateKeyFromLeftInteriorNode(BTreeNode left){ // // You need to provide the code for this method. // }
/** * Add a key to this interior node by a rotation of a key from the adjacent right interior node. * * <p>The key in the parent node of this at index this.parentIndex is moved to the last position in this * node, the first child node link in the right node is moved to be the last child node link in this node, * and the first key in the right node is moved to the this.parentIndex location in this node's parent node. * * @param right the right interior node for the key rotation */ private void rotateKeyFromRightInteriorNode(BTreeNode right){ // // You need to provide the code for this method. // }
/** * Merge two interior nodes. * * When this method is called, this node has (order-1) keys, the left and right nodes (at least one * of them exist), don't have any spare keys, but one or both have exactly order keys. * <p/>This method merges by preference with the left node - it only merges with the right node if * the the left node is null. * * @param leftNode The left candidate node for the merge. * @param rightNode The right candidate node for the merge. */ private void mergeWithInteriorNode(BTreeNode leftNode, BTreeNode rightNode){ // // You need to provide the code for this method. // } }
/** * A class to store the result of a search of the BTree class. * * <p>This class is also used to initialise a SequentialIterator object. * <p>Essentially stores a reference to a leaf node and index into the array of keys in the * leaf node. * <p>This class is an inner class of the BTree object, and so objects of this class have an * implicit reference to the 'containing' BTree object. This is used to allow a SearchPosition * object to be invalidated if the BTree object is modified. * * <p>Provided for Objects and Algorithms, Assignment 5<br> * <b>You do not need to modify this class.</b> * * @author a.sobey * @version 1.o */ public class SearchPosition { private boolean found; private int modCount; private BTreeNode leafNode; private int leafNodeIndex;
/** * Construct a SearchPosition object. * @param found Should be true if the key being searched for is in the B-Tree. * @param node The leaf node of the B-Tree that contains the key being searched for. * @param keyIndex The index of the search key within the B-Tree */ private SearchPosition(boolean found, BTreeNode node, int keyIndex) { this.found = found; this.modCount = BTree.this.changeCount; if (found) { if (!node.isLeaf()) throw new BTreeError("SearcResult.constructor: passed an interior BTreeNode rather than a leaf node"); leafNode = node; leafNodeIndex = keyIndex; } }
/** * Used to determine if the search did find the key in the B-Tree. If keyFound() is false, calls to * the mehtods searchKey(), data(), leafNode() and leafKeyIndex() will throw a BTreeError exception. * @return True if key was found in the B-tree */ public boolean keyFound() { if (modCount != BTree.this.changeCount) throw new BTreeError("SearchPosition.keyFound(): SearchPosition invalidated by tree modifications"); return found; }
/** * * @return The search key used for a successful search. */ public Comparable searchKey() { if (modCount != BTree.this.changeCount) throw new BTreeError("SearchPosition.searchKey(): SearchPosition invalidated by tree modifications"); return leafNode.key(leafNodeIndex); }
/** * * @return The data associated with the search key for a successful search. */ public Object data() { if (modCount != BTree.this.changeCount) throw new BTreeError("SearchPosition.data(): SearchPosition invalidated by tree modifications"); return leafNode.data(leafNodeIndex); }
/** * * @return The leaf node in which the key was found when the search was successful. */ public BTreeNode leafNode() { if (modCount != BTree.this.changeCount) throw new BTreeError("SearchPosition.leafNode(): SearchPosition invalidated by tree modifications"); return leafNode; }
/** * * @return The index into the keys array in the leaf node in which the key was found during a successfull search. */ public int leafKeyIndex() { if (modCount != BTree.this.changeCount) throw new BTreeError("SearchPosition.leafKeyIndex(): SearchPosition invalidated by tree modifications"); return leafNodeIndex; } }
/** * An interface for a sequential bi-directional iterator for the BTree class. * <p/> * <p>This interface specifies the methods that must be supplied by an iterator class for * bi-directional sequential access to the keys and data values stored in a BTree class. * <p>Provided for Objects and Algorithms, Assignment 5<br> * You do not need to modify this interface. * * @author a.sobey * @version 1.0 */ public interface SequentialIterator { /** * Used to determine if iterator is still valid. The iterator can be invalidated if data values are * added to or removed from the BTree class. * <p>Calls to the most other methods (except setFirst and setLast) will throw a BTreeIteratorError * exception if called for an iterator object that is not valid. * * @return true if the iterator is valid. */ public boolean isValid();
/** * Resets the iterator to be positioned just before the first key in the BTree. * <p> The iterator will be valid, but calls to key() and data() will throw a BTreeIteratorError * exceptions until the method next() has been called. */ public void setStart();
/** * Reset the iterator to be positioned just after the last key in the BTree. * <p>The Iterator will be valid, but calls to key() and data() will throw a BTreeIteratorError * exception until a call to the method previous() has been made. */ public void setEnd();
/** * A method to determine if there are futher keys to visit via calls to next() * * @return true if there are more keys to visit by calls to next(). */ public boolean hasNext();
/** * A method to determine if there are futher keys to visit via calls to previous(). * * @return true if there are more keys to visit by a call to previous() */ public boolean hasPrevious();
/** * A method to 'advance' the position of the iterator to the next key in the BTree. * <p> Note<b>If the iterator is positioned at the last key, a call to next() can still be made, and will * result in the iteraetor being positioned as if a call to setEnd() had been made. Howoever, calls to * key() and data() will then thow a BTreeIterator exception until a call to previous() is made.<br> * A call to next() while the iterator is positioned at the setEnd() position will throw a BTreeIteratorError * exception. */ public void next();
/** * A method to 'advance' the position of the iterator to the previous key in the BTree. * <p> Note<b>If the iterator is positioned at the first key, a call to previous() can still be made, and will * result in the iteraetor being positioned as if a call to setStart() had been made. Howoever, calls to * key() and data() will then thow a BTreeIterator exception until a call to next() is made.<br> * A call to previous() while the iterator is positioned at the setStart() position will throw a BTreeIteratorError * exception. */ public void previous();
/** * A method to return the key value associated with the current position of the iterator. * * @return The key at the current iterator position. */ public Comparable key();
/** * A method to return the data value assocaited with the key value at the current position of the iterator. * * @return The data value at the current iterator position. */ public Object data(); }
/** * A simple exception class to for classes that implement the SequentialIterator interface to thow when * an interator is used wrongly or becomes invalid due to changes to the BTree object. * * <p>LProvided for Objects and Algorithms Assignment 5<br> * You do not need to modify this class. * * @author a.sobey * @version 1.0 */ public class BTreeIteratorError extends RuntimeException { public BTreeIteratorError(String reason) { super(reason); } }
/** * An implementation of the SequentialIterator interface to allow bi-directional sequential access to the keys * and associated data in a BTree object. * * <p>Provided for Objects and Algorithms assignment 5<br> * You do not need to modify this class. * * @author a.sobey * @version 1.0 */ private class BTreeIterator implements SequentialIterator {
private SearchPosition position;
public BTreeIterator() { position = new SearchPosition(size() > 0, first, -1); }
public BTreeIterator(SearchPosition position) { this.position = position; }
public boolean isValid() { return position.keyFound(); }
public void setStart() { position = new SearchPosition(size() > 0, first, -1); }
public void setEnd() { position = new SearchPosition(size() > 0, last, last.numberOfKeys); }
public void next() { if (position.leafNode.next == null && position.leafNodeIndex == position.leafNode.numberOfKeys) throw new BTreeIteratorError("next() called when past end of the keys of the BTree"); if (position.leafNode.next == null && position.leafNodeIndex == position.leafNode.numberOfKeys - 1) { position.leafNodeIndex = position.leafNode.numberOfKeys; return; } if (position.leafNodeIndex < position.leafNode.numberOfKeys - 1) position.leafNodeIndex++; else { position.leafNode = position.leafNode.next; position.leafNodeIndex = 0; } }
public void previous() { if (position.leafNode.previous == null && position.leafNodeIndex == -1) throw new BTreeIteratorError("previous() called when before start of the keys of the BTree"); if (position.leafNode.previous == null && position.leafNodeIndex == 0) { position.leafNodeIndex = -1; return; } if (position.leafNodeIndex > 0) position.leafNodeIndex--; else { position.leafNode = position.leafNode.previous; position.leafNodeIndex = position.leafNode.numberOfKeys - 1; } }
public Comparable key() { if (!position.keyFound()) throw new BTreeIteratorError("key() called for invalid iterator"); if (position.leafNode.previous == null && position.leafNodeIndex == -1) throw new BTreeIteratorError("key() called when before start of the keys of the BTree"); if (position.leafNode.next == null && position.leafNodeIndex == position.leafNode.numberOfKeys) throw new BTreeIteratorError("key() called when past end of the keys of the BTree"); return position.leafNode.key(position.leafNodeIndex); }
public Object data() { if (!position.keyFound()) throw new BTreeIteratorError("data() called for invalid iterator"); if (position.leafNode.previous == null && position.leafNodeIndex == -1) throw new BTreeIteratorError("data() called when before start of the keys of the BTree"); if (position.leafNode.next == null && position.leafNodeIndex == position.leafNode.numberOfKeys) throw new BTreeIteratorError("data() called when past end of the keys of the BTree"); return position.leafNode.data(position.leafNodeIndex); }
} }
The test program........
/** * A simple program to exercise the BTree class. * * <p/>Provided for Objects and Algorithms, assignment 5. * <p/>You can modify this code as much as you like - a different test program will be used for marking * * @author a.sobey * @version 1.0 */ public class BTreeTest {
public static void main(String args[]) { BTree bTree; // // Try testing your code with order 1, 2, 3, 4, 5, 6 // int order = 1; System.out.println("Creating BTree of order "+order); bTree = new BTree(order); System.out.println("New tree:\n"+bTree.toString());
// // Add some key + data pairs to the tree // // There is alternate add code - adds in reverse order // You should try adding keys in increasing and reverse order // System.out.println("\nAdding 10 key+data pairs to the B-Tree\n"); for (int i=1; i<=10; i++) { System.out.println("About to add key "+i); bTree.add(new Integer(i), "Data #"+i); System.out.println(bTree); } // alternate add code // for (int i=10; i>=1; i--) { // System.out.println("About to add key "+i); // bTree.add(new Integer(i), "Data #"+i); // System.out.println(bTree); // }
// // Check that iterators work - in both forward and backward directions // System.out.println("\nChecking iterators work in forward and backward directions\n"); BTree.SequentialIterator itr = bTree.iterator(); System.out.print("Forward: "); while (itr.hasNext()){ itr.next(); System.out.print("("+itr.key()+", "+itr.data()+")"+(itr.hasNext()?" | " : ".\n")); } itr.setEnd(); System.out.print("Reverse: "); while (itr.hasPrevious()){ itr.previous(); System.out.print("("+itr.key()+", "+itr.data()+")"+(itr.hasPrevious()?" | " : ".\n")); }
// // Try adding at start, end and in middle where key already exists in tree // System.out.println("\nAdding three key+data pairs where keys are already in tree\n"); System.out.println("Changing data for key 1"); bTree.add(new Integer(1), "NewData #1"); System.out.println(bTree);
System.out.println("Changing data for key 5"); bTree.add(new Integer(5), "NewData #5"); System.out.println(bTree);
System.out.println("Changing data for key 10"); bTree.add(new Integer(10), "NewData #10"); System.out.println(bTree);
// // Check again that iterators still work in forward and backward directions System.out.println("\nChecking iterators work in forward and backward directions\n"); itr = bTree.iterator(); System.out.print("Forward: "); while (itr.hasNext()){ itr.next(); System.out.print("("+itr.key()+", "+itr.data()+")"+(itr.hasNext()?" | " : ".\n")); } itr.setEnd(); System.out.print("Reverse: "); while (itr.hasPrevious()){ itr.previous(); System.out.print("("+itr.key()+", "+itr.data()+")"+(itr.hasPrevious()?" | " : ".\n")); }
// // Checking searchFor() for all data in tree // System.out.println("\nChecking searchFor() method\n"); for (int k = -1; k < 12; k++){ BTree.SearchPosition position = bTree.searchFor(new Integer(k)); System.out.println("searchFor(new Integer("+k+") returned "+ position.keyFound() +(position.keyFound()?", data = "+position.data():"")); }
// // Try deleting keys from tree (should try deleting 1..10 and deleting 10..1 // System.out.println("\nDeleting keys from tree\n"); System.out.println(bTree); for(int k=1; k<=10; k++){ System.out.println("Deleting key "+k); System.out.println("data removed = "+bTree.delete(new Integer(k))); System.out.println(bTree); } // alternate code for deleting in order 10 to 1. // for(int k=10; k>=1; k--){ // System.out.println("data removed = "+bTree.delete(new Integer(k))); // System.out.println(bTree); // }
// // Checking iterator works after deleting some values // System.out.println("\nChecking iterator after delete\n"); System.out.println("After adding 10 values (1 .. 10) B-Tree is:"); for (int i=1; i<=10; i++) { bTree.add(new Integer(i), "Data #"+i); } System.out.println(bTree); bTree.delete(new Integer(1)); bTree.delete(new Integer(10)); bTree.delete(new Integer(5)); System.out.println("After deleting keys 1, 10 and 5, BTree is:"); System.out.println(bTree); itr = bTree.iterator(); System.out.print("Forward: "); while (itr.hasNext()){ itr.next(); System.out.print("("+itr.key()+", "+itr.data()+")"+(itr.hasNext()?" | " : ".\n")); } itr.setEnd(); System.out.print("Reverse: "); while (itr.hasPrevious()){ itr.previous(); System.out.print("("+itr.key()+", "+itr.data()+")"+(itr.hasPrevious()?" | " : ".\n")); } }
Previous Topic
