Mega Code Archive
Search Tree
<![CDATA[
//package termproject;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* (2,4) Search Tree
*
* Description: An ADT for a (2,4) Search Tree as described on page 451 of
* the Data Structures and Algorithms in Java textbook.
*
* Date Created: December, 2008
* @author Alex Laird, Wes Perrien
* @version 1.0
*/
public class TwoFourTree implements Dictionary
{
private Comparator treeComp;
private int size = 0;
private TFNode treeRoot = null;
/**
* Default constructor which assigns the comparator for the tree.
*
* @param comp Comparator the comparator to be assigned
*/
public TwoFourTree(Comparator comp)
{
treeComp = comp;
}
/**
* Returns the current size of the tree.
*
* @return int the current size of the tree.
*/
public int size()
{
return size;
}
/**
* Returns true if the tree is empty, otherwise false.
*
* @return boolean whether the tree is empty or not
*/
public boolean isEmpty()
{
return (size == 0);
}
/**
* Returns a pointer to the root node of the tree.
*
* @return TFNode the root node
*/
public TFNode root()
{
return treeRoot;
}
/**
* Finds an the first element in the tree with the specified key.
*
* @param key Object the key that is to be found in the tree
* @return Object the Item that contains the specified key
* @throws ElementNotFoundException if the key is not found in the tree
*/
public Object findElement (Object key) throws ElementNotFoundException
{
TFNode node = firstGreaterOrEqualNode(key, root());
int itemIndex = firstGreaterOrEqualItem(key, node);
if(itemIndex == -1)
throw new ElementNotFoundException();
if(treeComp.isEqual(key, ((Item) node.getItem(itemIndex)).key()))
return node.getItem(itemIndex);
else
throw new ElementNotFoundException();
}
/**
* Inserts an Item with the specified key and element into the tree at it's
* proper location. This function determines the in order successor based on
* the specified key to find the proper location.
*
* @param key Object the key to be used for the inserted Item
* @param element Object the element to be used for the inserted Item
*/
public void insertElement (Object key, Object element)
{
Item newItem = new Item(key, element);
// if this is the first element, make a root node
if(size() == 0)
{
treeRoot = new TFNode();
treeRoot.addItem(0, newItem);
size++;
return;
}
// find the node that contains the first greater or equal item
TFNode greatest = findInsertionPointer(newItem.key(), root());
if(greatest != null)
{
// find greatest or equal item within node
int index = firstGreaterOrEqualItem(newItem.key(), greatest);
// if a greater or equal item was not found in node, add at end
if(index == -1)
index = greatest.numItems();
// insert item at proper location
greatest.insertItem(index, newItem);
}
// if a greater or equal node was not found, insert at root
else
{
greatest = treeRoot;
// walks to the far right child
while(greatest.getChild(greatest.numItems()) != null)
greatest = greatest.getChild(greatest.numItems());
greatest.addItem(greatest.numItems(), newItem);
}
// incremet tree size
size++;
// if the insert caused a node to be greater than the max allowed size
// a node split is required
if(greatest.numItems() == greatest.maxItems() + 1)
{
nodePop(greatest);
}
}
/**
* Removes the first element from the tree that matches the specified key.
*
* @param key Object the key to be removed by the first found element
* @return Object the Item that contains the specified key
* @throws ElementNotFoundException if the key is not found in the tree
*/
public Object removeElement (Object key) throws ElementNotFoundException
{
// ensure that the element is in the tree and find it
findElement(key);
TFNode node = firstGreaterOrEqualNode(key, root());
TFNode inOrderSuccessor = null;
Object element;
// find the index of the element within the node
int location = firstGreaterOrEqualItem(key, node);
// if the node is internal
if(node.getChild(location + 1) != null)
{
inOrderSuccessor = node.getChild(location + 1);
// find the in order successor
while(inOrderSuccessor.getChild(0) != null)
inOrderSuccessor = inOrderSuccessor.getChild(0);
node.insertItem(location, inOrderSuccessor.removeItem(0));
location++;
}
// remove the item from the tree
element = node.removeItem(location);
// rebalance the tree if the node has become empty
if(node.numItems() == 0
&& node != root())
rebalance(node);
// rebalance tree if in order successor has become empty
if(inOrderSuccessor != null
&& inOrderSuccessor.numItems() == 0)
rebalance(inOrderSuccessor);
return element;
}
/**
* Determines whether the specified node has a left sibling or not. If it does
* have a left sibling, this method returns the index to the left sibling.
*
* @param node TFNode the node to be checked for a left sibling
* @return int -1 if there is no left sibling, otherwise the index of the left sibling
*/
protected int hasLeftSibling(TFNode node)
{
int childIndex;
// find the index in the parent of the current node
for(childIndex = 0; childIndex < 4; childIndex++)
{
if (node.getParent().getChild(childIndex) == node)
break;
}
if(childIndex != 0
&& node.getParent().getChild(childIndex - 1) != null)
// return the index of the left sibling
return childIndex - 1;
else
// no left sibling exists
return -1;
}
/**
* Determines whether the specified node has a right sibling or not. If it does
* have a right sibling, this method returns the index to the right sibling.
*
* @param node TFNode the node to be checked for a right sibling
* @return int -1 if there is no right sibling, otherwise the index of the right sibling
*/
protected int hasRightSibling(TFNode node)
{
int childIndex;
// find the index in the parent of the current node
for(childIndex = 0; childIndex < 4; childIndex++)
{
if (node.getParent().getChild(childIndex) == node)
break;
}
if(childIndex != 3
&& node.getParent().getChild(childIndex + 1) != null)
// return the index of the right sibling
return childIndex + 1;
else
// no right sibling exists
return -1;
}
/**
* This method will rebalance if needed, usually directly following a remove.
*
* @param node TFNode the node to be the starting point for rebalance
*/
protected void rebalance(TFNode node)
{
// check siblings
int leftSibIndex = hasLeftSibling(node);
int rightSibIndex = hasRightSibling(node);
TFNode leftSib = null;
TFNode rightSib = null;
TFNode parent = node.getParent();
TFNode newNode = null;
if(leftSibIndex != -1)
{
// get the left sibling
leftSib = parent.getChild(leftSibIndex);
}
if(rightSibIndex != -1)
{
// get the right sibling
rightSib = parent.getChild(rightSibIndex);
}
// transfer from left sibling
if(leftSibIndex != -1
&& leftSib.numItems() > 1)
{
// insert parent into index 0
node.insertItem(0, parent.getItem(leftSibIndex));
// make left sibling's most right child the first child here
node.setChild(0, leftSib.getChild(leftSib.numItems()));
if(node.getChild(0) != null)
node.getChild(0).setParent(node);
// store the last pointer reference
TFNode pointer = leftSib.getChild(leftSib.numItems() - 1);
// make left sibling's greatest item the new parent
parent.replaceItem(leftSibIndex, leftSib.removeItem(leftSib.numItems() - 1));
// reset the last pointer
leftSib.setChild(leftSib.numItems(), pointer);
}
// transfer from right sibling
else if(rightSibIndex != -1
&& rightSib.numItems() > 1)
{
// insert parent into index 0
node.insertItem(0, parent.getItem(rightSibIndex - 1));
// make right sibling's first child the last child here
node.setChild(0, rightSib.getChild(0));
if(node.getChild(0) != null)
node.getChild(0).setParent(node);
// store the third last pointer reference
TFNode pointer = rightSib.getChild(0);
// make right sibling's first item the new parent
parent.replaceItem(rightSibIndex - 1, rightSib.removeItem(0));
// reset the last pointer
rightSib.setChild(rightSib.numItems(), pointer);
}
// neither sibling has enough elements
else
{
// left fusion
if(leftSib != null
&& leftSib.numItems() == 1)
{
// store nodes pointer
TFNode pointer = node.getChild(0);
if(treeComp.isLessThan(((Item) leftSib.getItem(0)).key(), ((Item) parent.getItem(leftSibIndex)).key()))
leftSib.addItem(1, parent.removeItem(leftSibIndex));
else
leftSib.insertItem(0, parent.removeItem(leftSibIndex));
// reset the last pointer
leftSib.setChild(leftSib.numItems(), pointer);
if(pointer != null)
pointer.setParent(leftSib);
parent.setChild(leftSibIndex, leftSib);
newNode = leftSib;
}
// right fusion
else
{
// store the nodes pointer
TFNode pointer = node.getChild(rightSib.numItems());
if(treeComp.isLessThan(((Item) rightSib.getItem(0)).key(), ((Item) parent.getItem(rightSibIndex - 1)).key()))
rightSib.addItem(1, node.getParent().removeItem(rightSibIndex - 1));
else
rightSib.insertItem(0, node.getParent().removeItem(rightSibIndex - 1));
// reset the first pointer
rightSib.setChild(0, pointer);
if(pointer != null)
pointer.setParent(rightSib);
parent.setChild(rightSibIndex - 1, rightSib);
newNode = rightSib;
}
}
// rebalance parent recursively if it has zero items and is not he parent
if(parent.numItems() == 0)
{
if(parent != root())
rebalance(parent);
else
{
treeRoot = newNode;
newNode.setParent(null);
size--;
}
}
node = null;
}
/**
* Searches the tree until it finds a node with an item that is greater than
* or equal to the specified key.
*
* @param key Object the key to be compared against
* @param node TFNode the node to be the starting point, usually the root
* @return TFNode the node that holds the first greater or equal item
*/
protected TFNode firstGreaterOrEqualNode(Object key, TFNode start)
{
// recursive exit condition
if(start == null)
return null;
int index = firstGreaterOrEqualItem(key, start);
if(index == -1)
{
index = start.numItems();
return firstGreaterOrEqualNode(key, start.getChild(index));
}
if(treeComp.isLessThan(key, ((Item) start.getItem(index)).key()))
return firstGreaterOrEqualNode(key, start.getChild(index));
else if(treeComp.isGreaterThan(key, ((Item) start.getItem(index)).key()))
return firstGreaterOrEqualNode(key, start.getChild(index + 1));
else
return start;
}
/**
* Searches the node until it finds a node that is greater than or equal to
* the specified key.
*
* @param key Object the key to be compared against
* @param node TFNode the node to be searched
* @return int the index of the first greater than or equal item
*/
protected int firstGreaterOrEqualItem(Object key, TFNode node) throws ElementNotFoundException
{
if(node == null)
throw new ElementNotFoundException();
// find first greater or equal item within the node
for(int i = 0; i < node.numItems(); i++)
{
if (treeComp.isGreaterThanOrEqualTo(((Item) node.getItem(i)).key(), key))
return i;
}
// no greater or equal item was found
return -1;
}
/**
* Searches the tree until it finds a node with an item that is greater than
* or equal to the specified key. This is the point at which it will insert
* the a new node.
*
* @param key Object the key to be compared against
* @param start TFNode the node to be the starting point, usually the root
* @return TFNode the node that holds the first greater or equal item
*/
protected TFNode findInsertionPointer(Object key, TFNode start)
{
// exit condition for recursion
if(start == null)
return null;
int index = firstGreaterOrEqualItem(key, start);
// if a greater or equal item was not found in node, add at end
if(index == -1)
index = start.numItems();
// continue searching down tree
TFNode node = findInsertionPointer(key, start.getChild(index));
if(node == null)
return start;
return node;
}
/**
* Pops the third item out of a node and sends it to the parent, thus creating
* the children nodes off of that parent then. Essentially a node split. Usually
* called directly after an insert if the insert causes a node to become too full.
*
* @param left TFNode the node to be split
*/
protected void nodePop(TFNode left)
{
TFNode parent;
TFNode right = new TFNode();
int index;
// if no parent exists, we are the root
if(left.getParent() == null)
{
parent = new TFNode();
treeRoot = parent;
index = 0;
}
else
{
parent = left.getParent();
index = firstGreaterOrEqualItem(((Item) left.getItem(2)).key(), parent);
// if a greater or equal item was not found in node, add at end
if(index == -1)
index = parent.numItems();
}
// insert items in new locations
parent.insertItem(index, left.getItem(2));
right.addItem(0, left.getItem(3));
// set new child pointers
parent.setChild(index, left);
parent.setChild(index + 1, right);
// set parent pointers
left.setParent(parent);
right.setParent(parent);
// conditions if the node has more than three children
if(left.getChild(3) != null)
{
right.setChild(0, left.getChild(3));
right.getChild(0).setParent(right);
}
if(left.getChild(4) != null)
{
right.setChild(1, left.getChild(4));
right.getChild(1).setParent(right);
}
// store the third pointer reference
TFNode pointer = left.getChild(2);
// remove the two items
left.removeItem(2);
left.removeItem(2);
// reassign the child which was lost in the remove
left.setChild(2, pointer);
// check to see if the parent is too full now; call recursion
if(parent.numItems() == parent.maxItems() + 1)
nodePop(parent);
}
/**
* The main method which the program executes from and which handles all
* testing and input/output.
*
* @param args String[]
*/
public static void main(String[] args) throws IOException
{
Comparator myComp = new IntegerComparator();
TwoFourTree myTree = new TwoFourTree(myComp);
TwoFourTree firstTree = new TwoFourTree(myComp);
TwoFourTree secondTree = new TwoFourTree(myComp);
BufferedReader myReader = new BufferedReader(new InputStreamReader(System.in));
String input;
boolean go = true;
while(go == true)
{
System.out.print("Format like this: -a 37 to add a 37 to the tree. -r 37 to remove a 37 from the tree: ");
input = myReader.readLine();
if(input.substring(0, 2).equals("-a"))
{
Integer myInt = new Integer(input.substring(3, input.length()));
myTree.insertElement(myInt, myInt);
myTree.printAllElements();
}
else if(input.substring(0, 2).equals("-r"))
{
Integer myInt = new Integer(input.substring(3, input.length()));
myTree.removeElement(myInt);
myTree.printAllElements();
}
else
System.out.print("\nYou're bad!");
System.out.print("\n");
}
/*System.out.println("Loading firstTree with values ...");
Integer firstInt1 = new Integer(20);
firstTree.insertElement(firstInt1, firstInt1);
Integer firstInt2 = new Integer(50);
firstTree.insertElement(firstInt2, firstInt2);
Integer firstInt3 = new Integer(30);
firstTree.insertElement(firstInt3, firstInt3);
Integer firstInt4 = new Integer(40);
firstTree.insertElement(firstInt4, firstInt4);
Integer firstInt5 = new Integer(15);
firstTree.insertElement(firstInt5, firstInt5);
Integer firstInt6 = new Integer(35);
firstTree.insertElement(firstInt6, firstInt6);
Integer firstInt7 = new Integer(55);
firstTree.insertElement(firstInt7, firstInt7);
Integer firstInt8 = new Integer(38);
firstTree.insertElement(firstInt8, firstInt8);
Integer firstInt9 = new Integer(17);
firstTree.insertElement(firstInt9, firstInt9);
Integer firstInt10 = new Integer(37);
firstTree.insertElement(firstInt10, firstInt10);
Integer firstInt11 = new Integer(16);
firstTree.insertElement(firstInt11, firstInt11);
Integer firstInt12 = new Integer(36);
firstTree.insertElement(firstInt12, firstInt12);
Integer firstInt13 = new Integer(15);
firstTree.insertElement(firstInt13, firstInt13);
Integer firstInt14 = new Integer(36);
firstTree.insertElement(firstInt14, firstInt14);
Integer firstInt15 = new Integer(30);
firstTree.insertElement(firstInt15, firstInt15);
Integer firstInt16 = new Integer(34);
firstTree.insertElement(firstInt16, firstInt16);
Integer firstInt17 = new Integer(34);
firstTree.insertElement(firstInt17, firstInt17);
Integer firstInt18 = new Integer(30);
firstTree.insertElement(firstInt18, firstInt18);
Integer firstInt19 = new Integer(30);
firstTree.insertElement(firstInt18, firstInt18);
System.out.println("firstTree is fully loaded as follows:");
firstTree.printAllElements();
System.out.println("Checking parent/child connections ...");
firstTree.checkTree(firstTree.root());
System.out.println("All parent/child connections valid.");
System.out.println("\nRemove 30");
firstTree.removeElement(30);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 30");
firstTree.removeElement(30);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 30");
firstTree.removeElement(30);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 30");
firstTree.removeElement(30);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 15");
firstTree.removeElement(15);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 55");
firstTree.removeElement(55);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 35");
firstTree.removeElement(35);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 38");
firstTree.removeElement(38);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 40");
firstTree.removeElement(40);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 36");
firstTree.removeElement(36);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 17");
firstTree.removeElement(17);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 34");
firstTree.removeElement(34);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 34");
firstTree.removeElement(34);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 36");
firstTree.removeElement(36);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 20");
firstTree.removeElement(20);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 37");
firstTree.removeElement(37);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 16");
firstTree.removeElement(16);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 50");
firstTree.removeElement(50);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("");
System.out.println("Remove 15");
firstTree.removeElement(15);
System.out.println("Removed successfully. Print new tree:");
firstTree.printAllElements();
System.out.println("done");
System.out.println("\n\nLoading secondTree with values ...");
Integer secondInt1 = new Integer(47);
secondTree.insertElement(secondInt1, secondInt1);
Integer secondInt2 = new Integer(83);
secondTree.insertElement(secondInt2, secondInt2);
Integer secondInt3 = new Integer(22);
secondTree.insertElement(secondInt3, secondInt3);
Integer secondInt4 = new Integer(16);
secondTree.insertElement(secondInt4, secondInt4);
Integer secondInt5 = new Integer(49);
secondTree.insertElement(secondInt5, secondInt5);
Integer secondInt6 = new Integer(100);
secondTree.insertElement(secondInt6, secondInt6);
Integer secondInt7 = new Integer(38);
secondTree.insertElement(secondInt7, secondInt7);
Integer secondInt8 = new Integer(3);
secondTree.insertElement(secondInt8, secondInt8);
Integer secondInt9 = new Integer(53);
secondTree.insertElement(secondInt9, secondInt9);
Integer secondInt10 = new Integer(66);
secondTree.insertElement(secondInt10, secondInt10);
Integer secondInt11 = new Integer(19);
secondTree.insertElement(secondInt11, secondInt11);
Integer secondInt12 = new Integer(23);
secondTree.insertElement(secondInt12, secondInt12);
Integer secondInt13 = new Integer(24);
secondTree.insertElement(secondInt13, secondInt13);
Integer secondInt14 = new Integer(88);
secondTree.insertElement(secondInt14, secondInt14);
Integer secondInt15 = new Integer(1);
secondTree.insertElement(secondInt15, secondInt15);
Integer secondInt16 = new Integer(97);
secondTree.insertElement(secondInt16, secondInt16);
Integer secondInt17 = new Integer(94);
secondTree.insertElement(secondInt17, secondInt17);
Integer secondInt18 = new Integer(35);
secondTree.insertElement(secondInt18, secondInt18);
Integer secondInt19 = new Integer(51);
secondTree.insertElement(secondInt19, secondInt19);
System.out.println("firstTree is fully loaded as follows:");
secondTree.printAllElements();
System.out.println("Checking parent/child connections ...");
secondTree.checkTree(secondTree.root());
System.out.println("All parent/child connections valid.");
System.out.println("\nRemove 19");
secondTree.removeElement(19);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 3");
secondTree.removeElement(3);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 66");
secondTree.removeElement(66);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 88");
secondTree.removeElement(88);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 94");
secondTree.removeElement(94);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 100");
secondTree.removeElement(100);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 97");
secondTree.removeElement(97);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 47");
secondTree.removeElement(47);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 53");
secondTree.removeElement(53);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 38");
secondTree.removeElement(38);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 24");
secondTree.removeElement(24);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 83");
secondTree.removeElement(83);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 49");
secondTree.removeElement(49);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 23");
secondTree.removeElement(23);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 51");
secondTree.removeElement(51);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 1");
secondTree.removeElement(1);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 22");
secondTree.removeElement(22);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 16");
secondTree.removeElement(16);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("");
System.out.println("Remove 35");
secondTree.removeElement(35);
System.out.println("Removed successfully. Print new tree:");
secondTree.printAllElements();
System.out.println("done");*/
}
public void printAllElements() {
int indent = 0;
if (root() == null) {
System.out.println("The tree is empty");
}
else {
printTree(root(), indent);
}
}
public void printTree(TFNode start, int indent) {
if (start == null) {
return;
}
for (int i = 0; i < indent; i++) {
System.out.print(" ");
}
printTFNode(start);
indent += 4;
int numChildren = start.numItems() + 1;
for (int i = 0; i < numChildren; i++) {
printTree(start.getChild(i), indent);
}
}
public void printTFNode(TFNode node) {
int numItems = node.numItems();
for (int i = 0; i < numItems; i++) {
System.out.print( ( (Item) node.getItem(i)).element() + " ");
}
System.out.println();
}
// checks if tree is properly hooked up, i.e., children point to parents
public void checkTree(TFNode start) {
if (start == null) {
return;
}
if (start.getParent() != null) {
TFNode parent = start.getParent();
int childIndex = 0;
for (childIndex = 0; childIndex <= parent.numItems(); childIndex++) {
if (parent.getChild(childIndex) == start) {
break;
}
}
// if child wasn't found, print problem
if (childIndex > parent.numItems()) {
System.out.println("Child to parent confusion");
printTFNode(start);
}
}
if (start.getChild(0) != null) {
for (int childIndex = 0; childIndex <= start.numItems(); childIndex++) {
if (start.getChild(childIndex).getParent() != start) {
System.out.println("Parent to child confusion");
printTFNode(start);
}
}
}
int numChildren = start.numItems() + 1;
for (int childIndex = 0; childIndex < numChildren; childIndex++) {
checkTree (start.getChild(childIndex));
}
}
}
/**
* Basic storage element for the 2-4 Tree
*
* @author Dr. Gallagher
* @version 1.0
* Created 2 Mar 2001
* Description: The basic node for a 2-4 tree. Contains an array of Items,
* an array of references to children TFNodes, a pointer to a parent TFNode,
* and a count of how many Items are stored in the node.
*/
class TFNode {
private static final int MAX_ITEMS = 3;
private int numItems = 0;
private TFNode nodeParent;
private TFNode[] nodeChildren;
private Object[] nodeItems;
public TFNode() {
// make them one bigger than needed, so can handle oversize nodes
// during inserts
nodeChildren = new TFNode[MAX_ITEMS+2];
nodeItems = new Object[MAX_ITEMS+1];
}
public int numItems () {
return numItems;
}
public int maxItems() {
return MAX_ITEMS;
}
public TFNode getParent() {
return nodeParent;
}
public void setParent (TFNode parent) {
nodeParent = parent;
}
public Object getItem(int index) {
if ( (index < 0) || (index > (numItems-1) ) )
throw new TFNodeException();
return nodeItems[index];
}
// adds, but does not extend array; so it overwrites anything there
public void addItem (int index, Object data) {
// always add at end+1; check that you are within array
if ( (index < 0) || (index > numItems) || (index > MAX_ITEMS) )
throw new TFNodeException();
nodeItems[index] = data;
numItems++;
}
// this function inserts an item into the node, and adjusts into child
// pointers to add the proper corresponding pointer
public void insertItem (int index, Object data) {
if ( (index < 0) || (index > numItems) || (index > MAX_ITEMS) )
throw new TFNodeException();
// adjust Items
for (int ind=numItems; ind > index; ind--) {
nodeItems[ind] = nodeItems[ind-1];
}
// insert new data into hole made
nodeItems[index] = data;
// adjust children pointers; if inserting into index=1, we make
// pointers 1 and 2 to point to 1; this is because whoever called
// this function will fix one of them later; index 0 doesn't change;
// pointer 3 becomes pointer 2; pointer 4 becomes 3, etc.
for (int ind=numItems+1; ind > index; ind--) {
nodeChildren[ind] = nodeChildren[ind-1];
}
numItems++;
}
// this method removes item, and shrinks array
public Object removeItem (int index) {
if ( (index < 0) || (index > (numItems-1) ) )
throw new TFNodeException();
Object removedItem = nodeItems[index];
for (int ind=index; ind < numItems-1; ind++) {
nodeItems[ind] = nodeItems[ind+1];
}
nodeItems[numItems-1] = null;
// fix children pointers also
// typically, you wouldn't expect to do a removeItem unless
// children are null, because removal of an item will mess up the
// pointers; however, here we will simply delete the child to the
// left of the removed item; i.e., the child with same index
for (int ind=index; ind < numItems; ind++) {
nodeChildren[ind] = nodeChildren[ind+1];
}
nodeChildren[numItems] = null;
numItems--;
return removedItem;
}
// this method removes item, but does not shrink array
public Object deleteItem (int index) {
if ( (index < 0) || (index > (numItems-1) ) )
throw new TFNodeException();
Object removedItem = nodeItems[index];
nodeItems[index] = null;
numItems--;
return removedItem;
}
// replaces Item at index with newItem, returning the old Item
public Object replaceItem (int index, Object newItem) {
if ( (index < 0) || (index > (numItems-1) ) )
throw new TFNodeException();
Object returnItem = nodeItems[index];
nodeItems[index] = newItem;
return returnItem;
}
public TFNode getChild (int index) {
if ( (index < 0) || (index > (MAX_ITEMS+1)) )
throw new TFNodeException();
return nodeChildren[index];
}
public void setChild (int index, TFNode child) {
if ( (index < 0) || (index > (MAX_ITEMS+1)) )
throw new TFNodeException();
nodeChildren[index] = child;
}
}
class TFNodeException extends RuntimeException {
public TFNodeException() {
super ("Problem with TFNode");
}
public TFNodeException(String errorMsg) {
super (errorMsg);
}
}
interface Dictionary {
public int size();
public boolean isEmpty();
public Object findElement (Object key) throws ElementNotFoundException;
public void insertElement (Object key, Object element);
public Object removeElement (Object key) throws ElementNotFoundException;
}
class ElementNotFoundException extends RuntimeException
{
public ElementNotFoundException()
{
}
}
class Item {
private Object itemKey;
private Object itemElement;
public Item() {
this (null, null);
}
public Item(Object key, Object element) {
itemKey = key;
itemElement = element;
}
public Object key() {
return itemKey;
}
public void setKey(Object key) {
itemKey = key;
}
public Object element() {
return itemElement;
}
public void setElement (Object element) {
itemElement = element;
}
}interface Comparator {
public boolean isLessThan (Object obj1, Object obj2);
public boolean isLessThanOrEqualTo (Object obj1, Object obj2);
public boolean isGreaterThan (Object obj1, Object obj2);
public boolean isGreaterThanOrEqualTo (Object obj1, Object obj2);
public boolean isEqual (Object obj1, Object obj2);
public boolean isComparable (Object obj);
}class IntegerComparator implements Comparator {
public IntegerComparator() {
}
public boolean isLessThan (Object obj1, Object obj2) {
Integer myInt1;
Integer myInt2;
try {
myInt1 = (Integer) obj1;
myInt2 = (Integer) obj2;
}
catch (ClassCastException exc) {
throw new InvalidIntegerException ("Object not an integer");
}
return ( myInt1.intValue() < myInt2.intValue() );
}
public boolean isLessThanOrEqualTo (Object obj1, Object obj2) {
return ( ! isLessThan (obj2, obj1) );
}
public boolean isGreaterThan (Object obj1, Object obj2) {
return ( isLessThan (obj2, obj1) );
}
public boolean isGreaterThanOrEqualTo (Object obj1, Object obj2) {
return ( ! isLessThan (obj1, obj2) );
}
public boolean isEqual (Object obj1, Object obj2) {
return ( (! isLessThan (obj1, obj2)) && (! isLessThan (obj2, obj1)) );
}
public boolean isComparable (Object obj) {
try {
Integer myInt = (Integer) obj;
return true;
}
catch (ClassCastException exc) {
return false;
}
}
}
class InvalidIntegerException extends RuntimeException {
public InvalidIntegerException(String errorMsg) {
super (errorMsg);
}
}
]]>