SplayBSTTree. It extends the
* object RootInsertionBSTTreeHead because it is root inserted, just a splay
* instead of a rotate to top. Therefore, it overides all important methods necessary for maintaining a
* Splay Tree.
*
* @author Corey Sanders
* @version 3.5 9/15/01
*/
public class SplayTreeHead 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"+
"Splay Insertion brings newly inserted nodes to the root using standard root insertion\n"+
"when the links from the root to the grandchild on the search path have different \n"+
"orientation and splay rotation (two rotations at the root) when the links from the root\n"+
"to the grandchil on the search path have the same orientation (Sedgewick, 540).\n\n"+
"Insertions require about N lg N comparisons, on the average, in a BST built from N random keys.\n\n"+
"The number of comparisons required for any sequence of M insert or search operations in an N-node\n"+
"splay BST is ((N+M)lg(N+M)).\n\n"+
"Search Hits and Search Misses 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 and Search Misses 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 SplayTreeHead() { this(0); } /** * Constructs a new, empty RootInsertionBSTTreeHead according to the type passed. * * *@param treeType type of tree that should be implemented. */ public SplayTreeHead(int treeType) { super(treeType); } /** * Gets the tree type String for the BSTTree. * * @return tree type String for the tree. */ public String getTreeTypeString() { return "Splay Tree"; } /** ****************************************************************************** * BST_TREE_TYPE Methods for determining best/average/worst case times * ****************************************************************************** */ /** * Returns the average Insertion time, according to n, the amount of elements in the tree. * * @param n the size of the tree for which the average search hit is needed. * * @return double the is the average search hit. */ public double averageInsertion(int n) { return (n*(Math.log((double)n))); } /** * 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);
splay((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.SPLAY_NODE, node); } else { splay(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);
}
}
}