/*
* Author: Cameron McKinnon
*/
package BinaryTree;
/**
* An AVL Tree that holds any number of data Objects of type E.
*
* Balance (keeping the tree's height minimal) and order (ensuring the tree is
* sorted) are both automatically maintained.
*
*
* @param The type of data to be sorted by this Tree.
* @author Cameron McKinnon
*/
public class Tree>
implements java.io.Serializable {
/**
* overseer is used internally to keep track of the tree's root after
* rotations.
*/
protected SubTree overseer;
/**
* Insert a node into the Tree. This node will contain toInsert. If another
* node is found that contains data which exactly matches toInsert
* (a collision), no insertion will take place and the Tree will not be
* changed.
* @param toInsert The node to insert.
* @return true on a successful insert, or false on a collision.
*/
public boolean insert(E toInsert) {
return overseer.right.insert(toInsert);
}
/**
* Search for a node which holds data equal to toFind.
* @param toFind The data to search for.
* @return the data held by the node if a matching one was found, or
* null if no match was found.
*/
public E find(E toFind) {
return overseer.right.find(toFind);
}
/**
* Delete the node with data toDelete from the tree.
* @param toDelete The node to be deleted will contain this data.
* @return true if a node was found and deleted, or false if no match was found.
*/
public boolean delete(E toDelete) {
if (size()==1){
//special case where there's only one node left
//(set to null instead of deleting)
if (overseer.right.data.compareTo(toDelete)==0){
overseer.right.data=null;
return true;
}
return false;
}
else
return overseer.right.delete(toDelete);
}
/**
* For debugging purposes only (not recommended for production use!): Display a
* visual representation of the tree's nodes using System.out(). Each node is
* represented by the data it contains.
*/
public void debug() {
overseer.right.debug();
}
/**
* In an in-order list of all the nodes in this tree, get the data from the
* child node at a specific position (ID). (Allows array-like data retrieval).
* This function performs a binary search.
* @param i the ID ('position') of the item to return.
* @return the data of the ndoe found, or null if no node was found
*/
public E getChildAt(int i) {
return overseer.right.getDataAt(i);
}
/**
* Get the number of nodes in this tree.
* @return the number of nodes in this tree.
*/
public int size() {
if (overseer.right.data == null) {
return 0;
} else {
return overseer.right.size();
}
}
/**
* @return true if the tree is empty - false otherwise.
*/
public boolean isEmpty(){
return (overseer.right.data == null);
}
/**
* Initialize the tree with no data.
*/
public Tree() {
overseer = new SubTree();
overseer.redirectChildPointer(new SubTree());
}
/**
* Initialize the tree with one node of data.
* @param initData The data with which to initialize the tree. Immediately
* after this constructor is called, the only node in the tree will be initData.
*/
public Tree(E initData) {
overseer = new SubTree();
overseer.redirectChildPointer(new SubTree());
insert(initData);
}
}