BSTTree that is root inserted. It implements the
* interface for TreeHead and implements all important methods necessary for maintaining a
* Root Inserted Binary Search Tree.
*
* @author Corey Sanders
* @version 3.4 9/15/01
*/
public class RootInsertionBSTTreeHead extends BSTTreeHead {
/**
* 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"+
"Root Insertion brings newly inserted nodes to the root using repeated rotations.\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";
/**************************************************************************************/
/* RootInsertionBSTTreeHead constructor, methods, and variables, regardless of type. */
/**************************************************************************************/
/**
* Constructs a new, null RootInsertionBSTTreeHead, sorted according to the keys' natural
* order and insertion occurs automatically to the root.
*
* Default type is BST_TREE_TYPE. */ public RootInsertionBSTTreeHead() { this(0); } /** * Constructs a new, empty RootInsertionBSTTreeHead according to the type passed. * *@param treeType type of tree that should be implemented. */ public RootInsertionBSTTreeHead(int treeType) { super(treeType); } /** * Gets the tree type String for the BSTTree. * * @return tree type String for the tree. */ public String getTreeTypeString() { return "Root Insertion 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 elements elemetns 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-------------------------------*/ /*-----------------------------------------------------------------------*/ /*************************************************************************/ /* BST_TREE_TYPE : Methods and Variables specific to the BST_TREE_TYPE. */ /* These methods are universally used, regardless of the type of BST. */ /*************************************************************************/ /** ************************************* * BST_TREE_TYPE Implements TreeHead * ************************************* */ /** * Adds the node to the tree using its natural ordering . *
The new node is inserted and then rotateToToped to the root. This defines the tree as a rotateToTop BSTTree.
*
* @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);
rotateToTop((BSTTree)node);
}
/**
* Searches for the comaparable object in the Tree using its natural ordering .
* If the method is successful in finding the element, the item is returned. Otherwise, the closest item is
* returned.
*
*
The found node rotated to the top, to the root. If the node is not found, the nearest node is rotated to the top. * * @param keySearch comparable object which is search for within the tree. * * @return Tree element which matches the keySearch or the nearest node or null if the search is impossible to perform. * * @throws ClassCastException key cannot be compared with the keys * currently in the map. * @throws NullPointerException key is null. */ public Tree search(Comparable keySearch) throws ClassCastException, NullPointerException { BSTTree node = (BSTTree)super.search(keySearch); if (node == null) { return null; } if (isAnimatingBSTTree()) { getWaitingList().addFirst(AnimatingTreeHead.ROTATE_TO_TOP_NODE, node); } else { rotateToTop(node); } return 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);
}
}
}