/*
* Author: Cameron McKinnon
*/
package BinaryTree;
/**
* A node in an AVL Tree. Meant to be used as a private member within the Tree
* class.
* @author Cameron McKinnon
*/
public class SubTree> implements java.io.Serializable {
/**
* This node's parent. This pointer is always maintained automatically by
* functions such as setLeft and setRight, and redirectChildPointer,
* as well as in all rotations.
*/
protected SubTree parent;
/**
* This node's right child.
*/
public SubTree right;
/**
* This node's left child.
*/
public SubTree left;
/**
* The data held by this node - used to compare nodes to one another
*/
public E data;
/**
* The height of this node's two children.
*/
private int rightHeight = 0;
private int leftHeight = 0;
/**
* The balance factor of this tree (used for AVL calculations)
*/
private int balanceFactor = 0;
/**
* The size of this node's two children.
*/
private int leftSize = 0;
private int rightSize = 0;
/**
* Initializes the tree with no parent or children and no data.
*/
protected SubTree() {
parent = null;
right = null;
left = null;
}
/**
* Initializes the tree with no parent or children, and assigns it data.
* @param e The data with which to initialize this node.
*/
protected SubTree(E e) {
parent = null;
right = null;
left = null;
data = e;
}
/**
* Search for and delete a node within this tree whose data is equal to e. Rebalancing
* occurs as appropriate.
* @param e The data to which the to-be-deleted node's data must be equal.
* @return true if a successful deletion occured, or false if no match was found.
*/
protected boolean delete(E e) {
SubTree foundNode = findNode(e);
if (foundNode == null) {
return false;
}
foundNode.deleteMe();
return true;
}
/**
* Insert a node into this tree (the node will be initialized with data e). If another
* node is found which already contains data equal to e (a collision), no insertion
* will occur.
* @param e The data with which to initialize the node to insert.
* @return true if the node was successfully inserted, or false if there was a
* collision.
*/
protected boolean insert(E e) {
if (data == null) {
data = e;
return true;
} else {
return (Integer.MAX_VALUE != recursiveInsert(new SubTree(e)));
}
}
/**
* Debug this tree recursively using System.out() to display this node's data
* and the data of its children.
*/
protected void debug() {
System.out.print("\nTREE DEBUG:\nH: ");
debug(0);
}
/**
* Compare the data from this node to that of another node.
* @param e The node against which this node is being compared.
* @return -1 if this node is lesser, 0 if they are equal, or 1 if e is greater.
*/
protected int compareTo(SubTree e) {
int r = this.data.compareTo(e.data);
if (r > 0) {
return 1;
}
if (r < 0) {
return -1;
}
return 0;
}
/**
* Calculate the size of this tree according to its two childrens' sizes.
* @return This SubTree's size.
*/
protected int size() {
return leftSize + rightSize + 1;
}
/**
* Return the node at a specific point (ID) in the list generated by an
* in-order traversal. NOTE: Although the behaviour of this function is
* described that way, this search is actually performed as a binary search,
* so it is very fast.
* @param i The ID of the node to return (that is, its position in the list
* generated by an in-rder traversal).
* @return The found node (or null there is no node with that ID).
*/
protected E getDataAt(int i) {
SubTree returnFrom = getNodeByIdRecursive(i, 0);
if (returnFrom == null) {
return null;
}
//else
return returnFrom.data;
}
/**
* Performs a recursive binary search for an element with i nodes with
* values smaller than it. This function is called by getDataAt.
* @param i the ID of the node to return
* @param add used internally by the function to keep track of how many
* nodes precede the current node - should always be passed a 0
* when called externally!
* @return the node at the passed ID, or null if no node was found.
*/
private SubTree getNodeByIdRecursive(int i, int add) {
//base case:
if (leftSize + add == i) {
return this;
}
//recursive cases:
if (leftSize + add > i && left != null) {
return left.getNodeByIdRecursive(i, add);
} else if (leftSize + add < i && right != null) {
return right.getNodeByIdRecursive(i, leftSize + 1 + add);
} else {
return null;
}
}
/**
* Recursively debug this node by displaying its data and the data of its
* children
* using System.out().
* @param i The distance of this node from the root of the tree. Should be
* passed a 0.
*/
private void debug(int i) {
fixCounts();
//print this node's data:
System.out.println(data.toString());
//System.out.print(" S="+this.size()+" BF="+(rightHeight - leftHeight));
//base case (this is a leaf node):
if (left == null && right == null) {
return;
}
i += data.toString().length() + 3;
//recursively debug this tree's left child
if (left != null) {
for (int c = 0; c < i / 2; c++) {
System.out.print(" ");
}
System.out.print("--L: ");
left.debug(i);
}
//recursively debug this tree's right child
if (right != null) {
for (int c = 0; c < i / 2; c++) {
System.out.print(" ");
}
System.out.print("--R: ");
right.debug(i);
}
}
/**
* Get the height of this tree by considering its left and right children's
* heights.
* @return the height of this tree.
*/
private int height() {
if (leftHeight > rightHeight) {
return leftHeight;
} else {
return rightHeight;
}
}
/**
* Set the right child.
* @param newChild The node which will become this node's right child.
*/
private void setRight(SubTree newChild) {
right = newChild;
if (newChild != null) {
rightHeight = newChild.height() + 1;
rightSize = newChild.size();
newChild.parent = this;
} else {
rightHeight = 0;
rightSize = 0;
}
}
/**
* Set the left child.
* @param newChild The node which will become this node's left child.
*/
private void setLeft(SubTree newChild) {
left = newChild;
if (newChild != null) {
leftHeight = newChild.height() + 1;
leftSize = newChild.size();
newChild.parent = this;
} else {
leftHeight = 0;
leftSize = 0;
}
}
/**
* Replaces the child oldChild with newChild. That is, whichever of this tree's
* children was oldChild will now be newChild.
* @param oldChild The current child (to replace).
* @param newChild The child with which oldChild is to be replaced.
*/
private void redirectChildPointer(SubTree oldChild, SubTree newChild) {
if (right == oldChild) {
right = newChild;
if (newChild != null) {
rightHeight = newChild.height();
rightSize = newChild.size();
}
} else if (left == oldChild) {
left = newChild;
if (newChild != null) {
leftHeight = newChild.height();
leftSize = newChild.size();
}
} else {
right = newChild;
}
if (newChild != null) {
newChild.parent = this;
}
oldChild.parent=null;
}
/**
* Perform the same actions as setRight, but without maintaining rightHeight.
* @param newChild The new right child.
*/
protected void redirectChildPointer(SubTree newChild) {
right = newChild;
newChild.parent = this;
}
/**
* Perform an AVL right rotation (with root as the root, and pivot as the pivot).
* @param root The current root of the tree to be rotated.
* @param pivot The node which will become the root after the rotation is done.
*/
private void rightRotate(SubTree root, SubTree pivot) {
//redirect the root.parent->root reference to point at pivot instead
root.parent.redirectChildPointer(root, pivot);
root.setLeft(pivot.right);
pivot.setRight(root);
}
/**
* Perform an AVL left rotation (with root as the root, and pivot as the pivot).
* @param root The current root of the tree to be rotated.
* @param pivot The node which will become the root after the rotation is done.
*/
private void leftRotate(SubTree root, SubTree pivot) {
//redirect the root.parent->root reference to point at pivot instead
root.parent.redirectChildPointer(root, pivot);
root.setRight(pivot.left);
pivot.setLeft(root);
}
/**
* Balance _this tree only_ as necessary to make sure its balance factor has a
* magnitude of at most 1. Does not go on to balance this tree's children or
* ancestors.
*/
private void balance() {
balanceFactor = rightHeight - leftHeight;
if (balanceFactor == 2) {
right.balanceFactor = right.rightHeight - right.leftHeight;
if (right.balanceFactor == -1) {
rightRotate(right, right.left);
}
leftRotate(this, right);
} else if (balanceFactor == -2) {
left.balanceFactor = left.rightHeight - left.leftHeight;
if (left.balanceFactor == 1) {
leftRotate(left, left.right);
}
rightRotate(this, left);
}
}
/**
* Starting with this tree, recursively travel up the tree, balancing it as
* we go.
*/
private void balanceUp() {
balance();
fixCounts();
if (parent != null && parent.parent != null) {
parent.balanceUp();
}
}
/**
* Recursively find the place for the new node, and insert it there. Then
* recursively travel up the tree rebalancing it.
* @param e The node to insert.
* @return Integer.MAX_VALUE if a collision has occured. Otherwise returns
* the height of this tree.
*/
private int recursiveInsert(SubTree e) {
int check = 0;
if (e.compareTo(this) == 0) {
return Integer.MAX_VALUE;
}
//if e is greater than this
if (e.compareTo(this) > 0) {
if (right == null) {
//base case (attach the data as a child of this)
setRight(e);
rightHeight = 1;
rightSize = 1;
} else {
//recursive case
check = right.recursiveInsert(e);
}
//a collision has occured, return the flag
if (check == Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
rightHeight = right.height() + 1;
rightSize = right.size();
}
//if e is lesser than this
else {
if (left == null) {
//base case (attach the data as a child of this)
setLeft(e);
leftHeight = 1;
leftSize = 1;
} else {
//recursive case
check = left.recursiveInsert(e);
}
//a collision has occured, return the flag
if (check == Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
leftHeight = left.height() + 1;
leftSize = left.size();
}
//balance the tree if necessary after the insertion
balance();
//return the new height of this tree (after the balance).
return height();
}
/**
* Perform a binary search for a node with data e.
* @param e The data to search for.
* @return The found node if a match was found, or null if no match was found.
*/
private SubTree findNode(E e) {
//normal base case (node found, return this)
if (e.compareTo(this.data) == 0) {
return this;
}
//data will be in left subtree
else if (e.compareTo(this.data) < 0) {
if (left == null) {
//there is no left tree - return null (a base case)
return null;
} else {
//recursive case - continue recursing
return left.findNode(e);
}
}
//data will be in right subtree
else {
if (right == null) {
//there is no right tree - return null (a base case)
return null;
} else {
//recursive case - continue recursing
return right.findNode(e);
}
}
}
/**
* Find the node with the lowest value in this tree.
* @return The node with the lowest value in this tree.
*/
private SubTree findLowestNode() {
//travel down the left-most branch of this tree until a leaf node is
//found
if (left == null) {
return this;
} else {
return left.findLowestNode();
}
}
/**
* Find the node with the highest value in this tree.
* @return The node with the highest value in this tree.
*/
private SubTree findHighestNode() {
//travel down the right-most branch of this tree until a leaf node is
//found
if (right == null) {
return this;
} else {
return right.findHighestNode();
}
}
/**
* Find the node whose data is equal to e, and then return its data. Like
* findNode, but returns the found node's data instead of the node itself.
* @param e The data to search for.
* @return The found data if a match was found, or null if no match was found.
*/
protected E find(E e) {
SubTree holder = findNode(e);
if (holder == null) {
return null;
}
return holder.data;
}
/**
* Remove this node from its parent tree, and rebalance appropriately. This
* function removes the parent's reference to this tree so this tree can be
* garbage collected.
*/
private void deleteMe() {
if (right == null && left == null) {
SubTree oldParent=parent;
parent.redirectChildPointer(this, null);
oldParent.balanceUp();
return;
}
SubTree replacement;
SubTree replacementOldParent;
if (right==null){//replace with highest in left subtree
//find replacement
replacement=left.findHighestNode();
//set its old parent
replacementOldParent=replacement.parent;
//if necessary give replacement's left child to its parent
if (this.left!=replacement)
replacement.parent.setRight(replacement.left);
//replace this with replacement
replacement.setRight(this.right);
if (this.left!=replacement)
replacement.setLeft(this.left);
//else let replacement keep any children it may have
parent.redirectChildPointer(this,replacement);
}
else{//replace with lowest in right subtree
//find replacement
replacement=right.findLowestNode();
//set its old parent
replacementOldParent=replacement.parent;
//if necessary give replacement's right child to its parent
if (this.right!=replacement)
replacement.parent.setLeft(replacement.right);
//replace this with replacement
replacement.setLeft(this.left);
if (this.right!=replacement)
replacement.setRight(this.right);
//else let replacement keep any children it may have
parent.redirectChildPointer(this,replacement);
}
//if this is the replacement's old parent, balance up from replacement
if (this==replacementOldParent)
replacement.balanceUp();
//otherwise balance up from the replacement's old parent
else
replacementOldParent.balanceUp();
}
/**
* Set leftHeight and rightHeight based on the height of this node's children,
* and Set leftSize and rightSize based on the size of this node's children.
*/
private void fixCounts() {
if (right == null) {
rightHeight = 0;
rightSize=0;
} else {
rightHeight = right.height() + 1;
rightSize=right.size();
}
if (left == null) {
leftHeight = 0;
leftSize=0;
} else {
leftHeight = left.height() + 1;
leftSize=left.size();
}
}
}