BalancedBSTTree. Therefore,
* it overides all important methods necessary for maintaining a
* Balanced BST.
*
* BalanceBSTTree defines methods necessary for a BSTTreeHead, a DrawingBSTTreeHead, and an AnimatingBSTTreeHead.
* The type is set when the node is constructed but can be changed in the middle using methods found in BSTTree. If a method is
* called for a type that is higher is level than the type of the tree, the method will be ignored.
* @author Corey Sanders
* @version 3.4 9/15/01
*/
public class BalancedBSTTreeHead extends BSTTreeHead {
/**************************************************************************************/
/* RootInsertionBSTTreeHead constructor, methods, and variables, regardless of type. */
/**************************************************************************************/
/**
* String representing information regarding the type of tree.
*/
public static final String TREE_INFORMATION =
"A Binary Search Tree(BST) is a binary tree that has a key associated with each of its\n"+
"internal nodes, with the additional property that the key in any node is larger than\n"+
"(or equal to) the keys in all nodes in that node's left subtree and smaller than\n"+
"(or equal to) the keys in all nodes in that node's right subtree (Sedgewick, 502).\n\n"+
"We can balance most BSTs completely in linear time.\n"+
"Such rebalancing is likely to improve pperformance for random keys, but does not\n"+
"provide guarantess against quadratic worst-case. (Sedgewick, 530).\n\n"+
"This tree is automatically rebalanced at a given node once one child has a size\n"+
"that is 5 greater then the other child. Five is an arbitrary value selected.\n\n"+
"Search Hits, Search Misses, and Insertions require about 2 ln N (1.39 lg N) comparisons,\n"+
"on the average, in a BST built from N random keys.\n\n"+
"Search Hits, Search Misses, and Insertions can require N comparisons in the worst case.\n";
/**
* Constructs a new, null BalancedBSTTreeHead, sorted according to the keys' natural
* order and insertion occurs automatically to the root.
*
* Default type is BST_TREE_TYPE. */ public BalancedBSTTreeHead() { this(0); } /** * Constructs a new, empty BalancedBSTTreeHead according to the type passed. * * *@param treeType type of tree that should be implemented. */ public BalancedBSTTreeHead(int treeType) { super(treeType); setBalanceDifference(DEFAULT_BALANCE_DIFFERENCE); } /** * Gets the tree type String for the BSTTree. * * @return tree type String for the tree. */ public String getTreeTypeString() { return "Balanced BST Tree"; } /** * Acts according to the String action passed.Overides BSTTree, to stop rapid-fire * insertion. For each insertion a rotateToTop must follow, which means insertion must enter the waitingList also! * * * @param action String action representing the next action for the BSTTreeHead. * @param element Object to which the action could be occuring, depending on the type of action. */ public void waitingAction(String action, Object element) { // search if (action.equals(TreeHead.INSERT_NODE)) { insertAnimatingType((BSTTree)element); } else { super.waitingAction(action, element); } } /*-----------------------------------------------------------------------*/ /*-------------------------------BST_TREE_TYPE---------------------------*/ /*-----------------------------------START-------------------------------*/ /*-----------------------------------------------------------------------*/ /** * Double the difference between the left and right sizes for the tree to balance * after each insertion or deletion. */ private int balanceDifference; /** * Default balance probability. (1) */ public static final int DEFAULT_BALANCE_DIFFERENCE = 1; /*************************************************************************/ /* BST_TREE_TYPE : Methods and Variables specific to the BST_TREE_TYPE. */ /* These methods are universally used, regardless of the type of BST. */ /*************************************************************************/ /** * Makes and places the node into the tree. The node is returned for further manipulation. *
Makes the node a BalancedBSTTree.
*
* @param keyInsert comparable object which is added to the tree.
* @param valueInsert Object that accompanies keyInsert in the node.
*
* @return BSTTree that was recently inserted into the tree.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected BSTTree makeNode(Comparable keyInsert, Object valueInsert) throws ClassCastException {
// Get node from node factory.
BalancedBSTTree newTree = new BalancedBSTTree(getTreeType());
newTree.setHead(this);
// Set the null leaves.
newTree.setLeaf();
// Set the values of the node.
newTree.setNode(keyInsert, valueInsert);
return newTree;
}
/**
* Gets the Balance Frequency for the Balanced BSTTree. The frequency is a double between
* 0.0 and 1.0 and is the probability that the tree will balance after every
* insert/delete.
*
* @return double probability of balancing the tree.
*/
public int getBalanceDifference() {
return balanceDifference;
}
/**
* Gets the Balance Frequency for the Balanced BSTTree. The frequency is a double between
* 0.0 and 1.0 and is the probability that the tree will balance after every
* insert/delete.
*
* @return double probability of balancing the tree.
*/
public void setBalanceDifference(int balanceDifference) {
this.balanceDifference = balanceDifference;
}
/**
*************************************
* BST_TREE_TYPE Implements TreeHead *
*************************************
*/
/**
* Adds the node to the tree using its natural ordering .
*
Randomly balances the tree after each insertion. * * @param node BSTTree which is added to the tree. * * @throws ClassCastException key cannot be compared with the keys * currently in the map. */ public void insert(Tree node) throws ClassCastException { super.insert(node); } /** * Removes the given node from the tree. The accompanying value is also * removed from the tree and the node is deleted. *
Randomly balances the tree after each deletion.
*
* @param node the Tree node to be removed from the tree.
*/
public void remove(Tree node) {
super.remove(node);
}
/*-----------------------------------------------------------------------*/
/*-------------------------------BST_TREE_TYPE---------------------------*/
/*------------------------------------END--------------------------------*/
/*-----------------------------------------------------------------------*/
/*/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
/*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////////*/
/*-----------------------------------------------------------------------*/
/*---------------------------ANIMATING_BST_TREE_TYPE---------------------*/
/*-----------------------------------START-------------------------------*/
/*-----------------------------------------------------------------------*/
/**
*********************************************
* ANIMATING_BST_TREE_TYPE Overiding methods *
*********************************************
*/
/**
* Insert the comaparable node to the tree using its natural ordering .
*
*
Makes insert a waitingAction if the tree is animating.
*
* @param node BSTTree node to be inserted into the tree
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected void insertAnimatingType(BSTTree node) throws ClassCastException {
// If Animation is occuring, add INSERT_NODE to the waitingList.
if (isTreeAnimating()) {
getWaitingList().add(AnimatingTreeHead.INSERT_NODE, node);
}
else {
super.insertAnimatingType(node);
}
}
}