686 lines
19 KiB
Java
686 lines
19 KiB
Java
package termproject;
|
|
|
|
import java.util.LinkedList;
|
|
import java.util.Queue;
|
|
import java.util.Random;
|
|
|
|
/**
|
|
* Title: Term Project 2-4 Trees
|
|
* Description: An abstract data type for a 2-4 tree
|
|
* Copyright: Copyright (c) 2017
|
|
* @author Joel Beckmeyer & Daniel Parker
|
|
* @version 1.0
|
|
*/
|
|
public class TwoFourTree
|
|
implements Dictionary {
|
|
|
|
private static final int MAX_ITEMS = 3;
|
|
|
|
private Comparator treeComp;
|
|
private int size = 0;
|
|
private TFNode treeRoot = null;
|
|
|
|
public TwoFourTree(Comparator comp) {
|
|
treeComp = comp;
|
|
}
|
|
|
|
private TFNode root() {
|
|
return treeRoot;
|
|
}
|
|
|
|
private void setRoot(TFNode root) {
|
|
treeRoot = root;
|
|
}
|
|
|
|
/**
|
|
* Searches the tree for a node containing the given key.
|
|
*
|
|
* @param key Object to search for
|
|
* @return node which contains key, or insertion point for this key
|
|
* @throws TwoFourTreeException if root is null
|
|
*/
|
|
private TFNode search(Object key) throws TwoFourTreeException {
|
|
TFNode current = treeRoot;
|
|
TFNode parent = null;
|
|
if(treeRoot == null) {
|
|
throw new TwoFourTreeException("root was null");
|
|
}
|
|
|
|
// loop until we have reached the child of an external node, or until
|
|
// we find the key
|
|
while(current != null) {
|
|
int index = FFGTE(current, key);
|
|
|
|
// ensure that the index given is not out of bounds
|
|
if(index != current.getNumItems()) {
|
|
if(treeComp.isEqual(current.getItem(index).key(), key)) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
parent = current;
|
|
current = current.getChild(index);
|
|
}
|
|
|
|
// if key was not found, we know we are at an external node, so we must
|
|
// return that node rather than its null "child"
|
|
if(current == null) {
|
|
return parent;
|
|
}else {
|
|
return current;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Finds the index of the first item that is greater than or equal to the
|
|
* given key.
|
|
*
|
|
* @param node TFnode to be searched
|
|
* @param key key to find
|
|
* @return index of first item greater than or equal to given key
|
|
*/
|
|
private int FFGTE(TFNode node, Object key) {
|
|
int i;
|
|
// loop through item array, comparing each item until we find first item
|
|
// greater than or equal to key
|
|
for(i = 0; i < node.getNumItems(); i++) {
|
|
if(treeComp.isGreaterThanOrEqualTo(node.getItem(i).key(), key)) {
|
|
break;
|
|
}
|
|
}
|
|
return i;
|
|
}
|
|
|
|
/**
|
|
* Finds the index of the given node in its parent.
|
|
*
|
|
* @param node the node to be found in the parent
|
|
* @return index of node in its parent
|
|
*/
|
|
private int WCIT(TFNode node) {
|
|
TFNode parent = node.getParent();
|
|
int i;
|
|
// loop through child array until we find the given node
|
|
for(i = 0; i < parent.getNumItems() + 1; ++i) {
|
|
if(parent.getChild(i) == node) {
|
|
break;
|
|
}
|
|
}
|
|
return i;
|
|
}
|
|
|
|
/**
|
|
* Finds the in-order successor of the given node-key combination.
|
|
*
|
|
* @param node the node to start at
|
|
* @param key the key to follow
|
|
* @return the in-order successor node
|
|
*/
|
|
private TFNode getInOrderSuccessor(TFNode node, int index) {
|
|
TFNode parent = null;
|
|
// go down the right child of our key
|
|
TFNode current = node.getChild(index + 1);
|
|
|
|
// go left until we hit a leaf
|
|
while(current != null) {
|
|
parent = current;
|
|
current = current.getChild(0);
|
|
}
|
|
|
|
return parent;
|
|
}
|
|
|
|
/**
|
|
* Checks for and fixes node overflow.
|
|
*
|
|
* @param node the node to check for overflow
|
|
*/
|
|
private void fixOverflow(TFNode node) {
|
|
if(node.getNumItems() <= MAX_ITEMS) {
|
|
return;
|
|
}
|
|
|
|
TFNode parent = node.getParent();
|
|
|
|
// special case when root overflows (we must increase height of tree)
|
|
if(parent == null) {
|
|
parent = new TFNode();
|
|
parent.setChild(0, node);
|
|
node.setParent(parent);
|
|
treeRoot = parent;
|
|
}
|
|
|
|
// removes offending data from current node
|
|
int index = WCIT(node);
|
|
|
|
// preserves data that we want to move around
|
|
TFNode left = node.getChild(3);
|
|
node.setChild(3, null);
|
|
TFNode right = node.getChild(4);
|
|
node.setChild(4, null);
|
|
Item toSibling = node.deleteItem(3);
|
|
Item toParent = node.deleteItem(2);
|
|
|
|
// creates and hooks up new sibling
|
|
TFNode sibling = new TFNode();
|
|
sibling.setParent(parent);
|
|
sibling.addItem(0, toSibling);
|
|
sibling.setChild(0, left);
|
|
sibling.setChild(1, right);
|
|
if(left != null) {
|
|
left.setParent(sibling);
|
|
right.setParent(sibling);
|
|
}
|
|
|
|
// connects children to parents
|
|
parent.insertItem(index, toParent);
|
|
parent.setChild(index, node);
|
|
parent.setChild(index + 1, sibling);
|
|
//}
|
|
|
|
// recursively call on parent
|
|
fixOverflow(parent);
|
|
}
|
|
|
|
/**
|
|
* Checks for and fixes node underflow.
|
|
*
|
|
* @param node the node to check for underflow
|
|
*/
|
|
private void fixUnderflow(TFNode node) {
|
|
// checks for underflow
|
|
if(node.getNumItems() < 1) {
|
|
|
|
// special case where root is underflowed
|
|
if(node == treeRoot) {
|
|
treeRoot = node.getChild(0);
|
|
node.setParent(null);
|
|
}
|
|
|
|
// different cases to check and run
|
|
else if(isPossibleLTrans(node)) {
|
|
leftTransfer(node);
|
|
}
|
|
else if(isPossibleRTrans(node)) {
|
|
rightTransfer(node);
|
|
}
|
|
else if(isPossibleLFusion(node)) {
|
|
leftFusion(node);
|
|
}
|
|
else {
|
|
rightFusion(node);
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Checks if left transfer is possible.
|
|
*
|
|
* @param node node to check for possible transfer
|
|
* @return true if possible
|
|
*/
|
|
private boolean isPossibleLTrans(TFNode node) {
|
|
// checks if the given node has a left sibling
|
|
int index = WCIT(node);
|
|
TFNode parent = node.getParent();
|
|
|
|
if(index > 0) {
|
|
TFNode sibling = parent.getChild(index - 1);
|
|
|
|
// checks if existing left sibling has 2+ items
|
|
return sibling.getNumItems() >= 2;
|
|
}else {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Checks if right transfer is possible.
|
|
*
|
|
* @param node node to check for possible transfer
|
|
* @return true if possible
|
|
*/
|
|
private boolean isPossibleRTrans(TFNode node) {
|
|
// checks if the given node has a right sibling
|
|
int index = WCIT(node);
|
|
TFNode parent = node.getParent();
|
|
|
|
if(index < parent.getNumItems()) {
|
|
TFNode sibling = parent.getChild(index + 1);
|
|
|
|
// checks if existing right sibling has 2+ items
|
|
return sibling.getNumItems() >= 2;
|
|
}else {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Performs a left transfer operation.
|
|
*
|
|
* @param node underflowed node to perform on
|
|
*/
|
|
private void leftTransfer(TFNode node) {
|
|
int index = WCIT(node);
|
|
TFNode parent = node.getParent();
|
|
TFNode sibling = parent.getChild(index - 1);
|
|
|
|
// preserving data that would otherwise be lost
|
|
TFNode lastChild = sibling.getChild(sibling.getNumItems());
|
|
sibling.setChild(sibling.getNumItems(), null);
|
|
Item lastItem = sibling.deleteItem(sibling.getNumItems() - 1);
|
|
|
|
// swap old sibling item with parent and add parent item to underflowed
|
|
// node
|
|
Item parentItem = parent.replaceItem(index - 1, lastItem);
|
|
node.addItem(0, parentItem);
|
|
|
|
|
|
// move old child 0 to child position 1, then add child from sibling as
|
|
// child 0
|
|
TFNode oldChild = node.getChild(0);
|
|
node.setChild(1, oldChild);
|
|
node.setChild(0, lastChild);
|
|
if(lastChild != null) {
|
|
lastChild.setParent(node);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Performs a right transfer operation.
|
|
*
|
|
* @param node underflowed node to perform on
|
|
*/
|
|
private void rightTransfer(TFNode node) {
|
|
int index = WCIT(node);
|
|
TFNode parent = node.getParent();
|
|
TFNode sibling = parent.getChild(index + 1);
|
|
|
|
// preserving data that would otherwise be lost
|
|
TFNode firstChild = sibling.getChild(0);
|
|
Item firstItem = sibling.removeItem(0);
|
|
|
|
// swap old sibling item with parent and add parent item to underflowed
|
|
// node
|
|
Item parentItem = parent.replaceItem(index, firstItem);
|
|
node.addItem(0, parentItem);
|
|
|
|
|
|
// insert child from sibling as 2nd(index 1) child
|
|
node.setChild(1, firstChild);
|
|
if(firstChild != null) {
|
|
firstChild.setParent(node);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Checks if left fusion operation is possible
|
|
*
|
|
* @param node node to check for possible fusion
|
|
* @return true if possible
|
|
*/
|
|
private boolean isPossibleLFusion(TFNode node) {
|
|
// checks if a left sibling exists
|
|
return WCIT(node) > 0;
|
|
}
|
|
|
|
/**
|
|
* Performs a left fusion operation
|
|
*
|
|
* @param node underflowed node to perform fusion on
|
|
*/
|
|
private void leftFusion(TFNode node) {
|
|
int index = WCIT(node);
|
|
TFNode parent = node.getParent();
|
|
|
|
// delete underflowed node
|
|
parent.setChild(index, null);
|
|
|
|
// preserving data
|
|
TFNode sibling = parent.getChild(index - 1);
|
|
Item parentItem = parent.removeItem(index - 1);
|
|
TFNode child = node.getChild(0);
|
|
|
|
// insert data in sibling
|
|
sibling.insertItem(sibling.getNumItems(), parentItem);
|
|
sibling.setChild(sibling.getNumItems(), child);
|
|
if(child != null) {
|
|
child.setParent(sibling);
|
|
}
|
|
|
|
// fix parent pointer
|
|
parent.setChild(index - 1, sibling);
|
|
if(node == null) {
|
|
System.out.println("node was null: ");
|
|
}
|
|
|
|
// recursively check underflow on parent
|
|
fixUnderflow(parent);
|
|
}
|
|
|
|
/**
|
|
* Performs a right fusion operation
|
|
*
|
|
* @param node underflowed node to perform fusion on
|
|
*/
|
|
private void rightFusion(TFNode node) {
|
|
int index = WCIT(node);
|
|
TFNode parent = node.getParent();
|
|
|
|
// preserving data
|
|
Item parentItem = parent.removeItem(index);
|
|
TFNode child = node.getChild(0);
|
|
TFNode sibling = parent.getChild(index);
|
|
|
|
// insert data in sibling
|
|
sibling.insertItem(0, parentItem);
|
|
sibling.setChild(0, child);
|
|
if(child != null) {
|
|
child.setParent(sibling);
|
|
}
|
|
|
|
// recursively check underflow on parent
|
|
fixUnderflow(parent);
|
|
}
|
|
public int size() {
|
|
return size;
|
|
}
|
|
|
|
public boolean isEmpty() {
|
|
return (size == 0);
|
|
}
|
|
|
|
/**
|
|
* Searches dictionary to determine if key is present
|
|
* @param key to be searched for
|
|
* @return object corresponding to key; null if not found
|
|
*/
|
|
public Object findElement(Object key) {
|
|
// first get the node which might contain the given key
|
|
TFNode target = search(key);
|
|
|
|
// find the key in this node
|
|
for(int i = 0; i < target.getNumItems(); ++i) {
|
|
if(treeComp.isEqual(target.getItem(i).key(), key)) {
|
|
return target.getItem(i).element();
|
|
}
|
|
}
|
|
|
|
// if key was not in node, return null
|
|
return null;
|
|
}
|
|
|
|
/**
|
|
* Inserts provided element into the Dictionary
|
|
* @param key of object to be inserted
|
|
* @param element to be inserted
|
|
*/
|
|
public void insertElement(Object key, Object element) {
|
|
if(treeRoot == null) {
|
|
treeRoot = new TFNode();
|
|
}
|
|
|
|
Item data = new Item(key, element);
|
|
TFNode node = search(key);
|
|
int index = FFGTE(node, key);
|
|
if(index != node.getNumItems()) {
|
|
// external node that contains a duplicate
|
|
if(node.getChild(0) == null) {
|
|
node.insertItem(index, data);
|
|
// internal node that contains a duplicate
|
|
}else {
|
|
node = getInOrderSuccessor(node, index);
|
|
node.insertItem(0, data);
|
|
}
|
|
// if we are at last index
|
|
}else {
|
|
node.insertItem(index, data);
|
|
}
|
|
|
|
fixOverflow(node);
|
|
}
|
|
|
|
/**
|
|
* Searches dictionary to determine if key is present, then
|
|
* removes and returns corresponding object
|
|
* @param key of data to be removed
|
|
* @return object corresponding to key
|
|
* @exception ElementNotFoundException if the key is not in dictionary
|
|
*/
|
|
public Object removeElement(Object key) throws ElementNotFoundException {
|
|
TFNode node = search(key);
|
|
int index = FFGTE(node, key);
|
|
|
|
// if we are at an external node and we got the last index of node,
|
|
// we know that the key was not in tree
|
|
if(index == node.getNumItems() && node.getChild(0) == null) {
|
|
this.printAllElements();
|
|
throw new ElementNotFoundException("key is not in tree: " + key);
|
|
}
|
|
|
|
Object returnData;
|
|
// if we are at an external node, simply remove data from node
|
|
if(node.getChild(0) == null) {
|
|
returnData = node.removeItem(index).element();
|
|
// else, we are at an internal node, we must replace data with in-order
|
|
// successor
|
|
}else {
|
|
TFNode successor = getInOrderSuccessor(node, index);
|
|
returnData = node.replaceItem(index, successor.removeItem(0)).element();
|
|
node = successor;
|
|
}
|
|
|
|
fixUnderflow(node);
|
|
return returnData;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
Comparator myComp = new IntegerComparator();
|
|
TwoFourTree myTree = new TwoFourTree(myComp);
|
|
|
|
myTree.insertElement(47, 47);
|
|
myTree.insertElement(83, 83);
|
|
myTree.insertElement(22, 22);
|
|
myTree.insertElement(16, 16);
|
|
myTree.insertElement(49, 49);
|
|
myTree.insertElement(100, 100);
|
|
myTree.insertElement(38, 38);
|
|
myTree.insertElement(3, 3);
|
|
myTree.insertElement(53, 53);
|
|
myTree.insertElement(66, 66);
|
|
myTree.insertElement(19, 19);
|
|
myTree.insertElement(23, 23);
|
|
myTree.insertElement(24, 24);
|
|
myTree.insertElement(88, 88);
|
|
myTree.insertElement(1, 1);
|
|
myTree.insertElement(97, 97);
|
|
myTree.insertElement(94, 94);
|
|
myTree.insertElement(35, 35);
|
|
myTree.insertElement(51, 51);
|
|
|
|
//myTree.printAllElements();
|
|
//System.out.println("removing\n");
|
|
|
|
myTree.removeElement(19);
|
|
myTree.removeElement(66);
|
|
myTree.removeElement(100);
|
|
myTree.removeElement(83);
|
|
myTree.removeElement(51);
|
|
myTree.removeElement(94);
|
|
myTree.removeElement(49);
|
|
myTree.removeElement(88);
|
|
|
|
//myTree.printAllElements();
|
|
System.out.println("test 1: simple test done");
|
|
|
|
System.out.println();
|
|
myTree = new TwoFourTree(myComp);
|
|
int testSize = 10000;
|
|
|
|
Random rng = new Random();
|
|
Queue<Integer> nums = new LinkedList<Integer>();
|
|
for (int i = 0; i < testSize; i++) {
|
|
int j = rng.nextInt(testSize / 10);
|
|
nums.add(j);
|
|
myTree.insertElement(j, j);
|
|
// if(i > testSize - 30) {
|
|
// System.out.println("inserting " + j);
|
|
// myTree.printAllElements();
|
|
// myTree.checkTree();
|
|
// }
|
|
}
|
|
System.out.println("removing");
|
|
for (int i = testSize - 1; i >= 0; i--) {
|
|
int j = nums.remove();
|
|
if (i < 30){
|
|
System.out.println("removing "+j);
|
|
}
|
|
//myTree.printAllElements();
|
|
int out = (int)myTree.removeElement(j);
|
|
if (out != j) {
|
|
throw new TwoFourTreeException("main: wrong element removed: " + out +" ; " + j);
|
|
}
|
|
if (i < 30){
|
|
myTree.printAllElements();
|
|
}
|
|
|
|
}
|
|
System.out.println("test 2: random done");
|
|
myTree.printAllElements();
|
|
|
|
System.out.println();
|
|
myTree = new TwoFourTree(myComp);
|
|
testSize = 1000;
|
|
for (int i = 0; i < testSize; i++) {
|
|
myTree.insertElement(0, 0);
|
|
}
|
|
System.out.println("removing");
|
|
int out;
|
|
for (int i = testSize - 1; i >= 0; i--) {
|
|
out = (int)myTree.removeElement(0);
|
|
if (out != 0) {
|
|
throw new TwoFourTreeException("main: wrong element removed: " + out);
|
|
}
|
|
}
|
|
System.out.println("test 3: extreme duplicate test done");
|
|
myTree.printAllElements();
|
|
|
|
System.out.println();
|
|
for (int i = 0; i < testSize; i++) {
|
|
myTree.insertElement(i, i);
|
|
}
|
|
System.out.println("removing");
|
|
for (int i = testSize - 1; i >= 0; i--) {
|
|
out = (int)myTree.removeElement(i);
|
|
if (out != i) {
|
|
throw new TwoFourTreeException("main: wrong element removed: " + out +" ; " + i);
|
|
}
|
|
}
|
|
System.out.println("test 4: reverse sorted order remove done");
|
|
myTree.printAllElements();
|
|
|
|
System.out.println();
|
|
for (int i = 0; i < testSize; i++) {
|
|
myTree.insertElement(i, i);
|
|
}
|
|
System.out.println("removing");
|
|
for (int i = 0; i < testSize; i++) {
|
|
out = (int)myTree.removeElement(i);
|
|
if (out != i) {
|
|
throw new TwoFourTreeException("main: wrong element removed: " + out +" ; " + i);
|
|
}
|
|
}
|
|
System.out.println("test 5: sorted order remove done");
|
|
myTree.printAllElements();
|
|
|
|
}
|
|
|
|
public void printAllElements() {
|
|
int indent = 0;
|
|
if (root() == null) {
|
|
System.out.println("The tree is empty");
|
|
}
|
|
else {
|
|
printTree(root(), indent);
|
|
}
|
|
System.out.println("");
|
|
}
|
|
|
|
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.getNumItems() + 1;
|
|
for (int i = 0; i < numChildren; i++) {
|
|
printTree(start.getChild(i), indent);
|
|
}
|
|
}
|
|
|
|
public void printTFNode(TFNode node) {
|
|
int numItems = node.getNumItems();
|
|
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() {
|
|
checkTreeFromNode(treeRoot);
|
|
}
|
|
|
|
private void checkTreeFromNode(TFNode start) {
|
|
if (start == null) {
|
|
return;
|
|
}
|
|
|
|
if (start.getParent() != null) {
|
|
TFNode parent = start.getParent();
|
|
int childIndex = 0;
|
|
for (childIndex = 0; childIndex <= parent.getNumItems(); childIndex++) {
|
|
if (parent.getChild(childIndex) == start) {
|
|
break;
|
|
}
|
|
}
|
|
// if child wasn't found, print problem
|
|
if (childIndex > parent.getNumItems()) {
|
|
System.out.println("Child to parent confusion");
|
|
printTFNode(start);
|
|
}
|
|
}
|
|
|
|
if (start.getChild(0) != null) {
|
|
for (int childIndex = 0; childIndex <= start.getNumItems(); childIndex++) {
|
|
if (start.getChild(childIndex) == null) {
|
|
System.out.println("Mixed null and non-null children");
|
|
printTFNode(start);
|
|
}
|
|
else {
|
|
if (start.getChild(childIndex).getParent() != start) {
|
|
System.out.println("Parent to child confusion");
|
|
printTFNode(start);
|
|
}
|
|
for (int i = childIndex - 1; i >= 0; i--) {
|
|
if (start.getChild(i) == start.getChild(childIndex)) {
|
|
System.out.println("Duplicate children of node");
|
|
printTFNode(start);
|
|
}
|
|
}
|
|
}
|
|
|
|
}
|
|
}
|
|
|
|
int numChildren = start.getNumItems() + 1;
|
|
for (int childIndex = 0; childIndex < numChildren; childIndex++) {
|
|
checkTreeFromNode(start.getChild(childIndex));
|
|
}
|
|
|
|
}
|
|
}
|