Class SplayTreeHead

java.lang.Object
  |
  +--BSTTree
        |
        +--BSTTreeHead
              |
              +--SplayTreeHead

All Implemented Interfaces:

AnimatingTree, AnimatingTreeHead, AnimationListener, DrawingTree, DrawingTreeHead, java.util.EventListener, Tree, TreeHead

public class SplayTreeHead

extends BSTTreeHead

This class provides the head structure for a 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.

Nested Class Summary

Nested classes inherited from class BSTTreeHead

BSTTreeHead.NodeAndKey

Field Summary

static java.lang.String

TREE_INFORMATION String representing information regarding the type of tree.

Fields inherited from class BSTTreeHead

BINARY_DISPLAY, SECTIONAL_DISPLAY

Fields inherited from class BSTTree

ANIMATING_BST_TREE_TYPE, BST_TREE_TYPE, DRAWING_BST_TREE_TYPE

Fields inherited from interface TreeHead

BALANCE_NODE, CHANGE_DISPLAY, INORDER_TRAVERSAL, INSERT_NODE, LEVELORDER_TRAVERSAL, PARTITION_NODE, POSTORDER_TRAVERSAL, PREORDER_TRAVERSAL, REMOVE_NODE, ROTATE_TO_TOP_NODE, ROTATE_UP, ROTATE_UP_DOUBLE, SEARCH, SELECT, SPLAY_NODE, TRAVERSE

Constructor Summary

SplayTreeHead()
Constructs a new, null RootInsertionBSTTreeHead, sorted according to the keys' natural order and insertion occurs automatically to the root.

SplayTreeHead(int treeType)
Constructs a new, empty RootInsertionBSTTreeHead according to the type passed.

Method Summary

double	averageInsertion(int n) Returns the average Insertion time, according to n, the amount of elements in the tree.
java.lang.String	getTreeTypeString() Gets the tree type String for the BSTTree.
void	insert(Tree node) Adds the node to the tree using its natural ordering .
protected void	insertAnimatingType(BSTTree node) Insert the comaparable node to the tree using its natural ordering .
Tree	search(java.lang.Comparable keySearch) Searches for the comaparable object in the Tree using its natural ordering .
void	waitingAction(java.lang.String action, java.lang.Object element) Acts according to the String action passed.Overides BSTTree, to stop rapid-fire insertion.

Methods inherited from class BSTTreeHead

addTreeAnimator, addTreeMessageListener, AnimateTree, animationEventPerformed, averageSearchHit, averageSearchMiss, balance, balanceAnimatingType, balanceTree, balanceTreeType, changeDisplay, changeDisplayAnimatingType, changeDisplayTreeType, clear, clearAnimators, constructAnimatingBSTTreeHead, constructBSTTreeHead, constructDrawingBSTTreeHead, DrawTree, findNode, fixLevel, fixSize, getBackgroundColor, getChild, getDeleteLeftLinePaintSettings, getDeleteRightLinePaintSettings, getDisplay, getDrawingKeySettings, getDrawingNodeSettings, getInorderTree, getInsertAnimatorKeySettings, getInsertAnimatorNodeSettings, getInsertNodeLeftSettings, getInsertNodeRightSettings, getLevelorderTree, getNodeHeight, getNodeWidth, getPostorderTree, getPreorderTree, getPreviousDisplay, getRotateAnimatorKeySettings, getRotateChildNodeSettings, getRotateDescendantNodeSettings, getRotateOriginalKeySettings, getRotateOriginalNodeSettings, getRotateRootNodeSettings, getScreenBounds, getSearchAnimatorKeySettings, getSearchAnimatorNodeSettings, getSearchNodeLeftSettings, getSearchNodeRightSettings, getSelectAnimatorKeySettings, getSelectAnimatorNodeSettings, getSelectNodeLeftSettings, getSelectNodeRightSettings, getTraverseAnimatorKeySettings, getTraverseAnimatorNodeSettings, getTreeAnimationStepSize, getTreeAnimator, getTreeLevel, getTreeSectionHeight, getTreeStatus, getTreeStatusMessage, getWaitingList, insert, insertDrawingType, insertTreeType, isJumpStep, isStepPause, isTreeAnimating, isTreeEmpty, isTreeRemove, makeBalanceAnimation, makeChangeDisplayAnimation, makeDeletionAnimation, makeInsertAnimation, makeNode, makeNodeDrawingType, makeNodeTreeType, makePartitionAnimation, makeRotationAnimation, makeRotationDoubleAnimation, makeSearchAnimation, makeSelectionAnimation, makeTraverseAnimation, MakeTree, messageAction, messageAction, partition, partitionAnimatingType, partitionTreeType, pause, play, remove, remove, removeAnimatingType, removeTreeAnimation, removeTreeMessageListener, removeTreeType, resetTreeLevel, rewind, rotateToTop, rotateToTopAnimatingType, rotateToTopTreeType, rotateUp, rotateUp, rotateUpAnimatingType, rotateUpDouble, rotateUpDouble, rotateUpDoubleAnimatingType, rotateUpDoubleTreeType, rotateUpTreeType, searchAnimatingType, searchTreeType, select, selectAnimatingType, selectTreeType, setBackgroundColor, setChild, setDeleteLeftLinePaintSettings, setDeleteRightLinePaintSettings, setDisplay, setDrawingKeySettings, setDrawingNodeSettings, setInsertAnimatorKeySettings, setInsertAnimatorNodeSettings, setInsertNodeLeftSettings, setInsertNodeRightSettings, setJumpStep, setNodeHeight, setNodeWidth, setPreviousDisplay, setRemove, setRotateAnimatorKeySettings, setRotateChildNodeSettings, setRotateDescendantNodeSettings, setRotateOriginalKeySettings, setRotateOriginalNodeSettings, setRotateRootNodeSettings, setScreenBounds, setSearchAnimatorKeySettings, setSearchAnimatorNodeSettings, setSearchNodeLeftSettings, setSearchNodeRightSettings, setSectionHeight, setSelectAnimatorKeySettings, setSelectAnimatorNodeSettings, setSelectNodeLeftSettings, setSelectNodeRightSettings, setStepPause, setTraverseAnimatorKeySettings, setTraverseAnimatorNodeSettings, setTreeAnimationsStepSize, setTreeLevel, setTreeSettings, setTreeStatus, setTreeType, size, splay, splayAnimatingType, splayTreeType, stop, traverse, traverseAnimatingType, traverseTreeType, worstCaseInsertion, worstCaseSearchHit, worstCaseSearchMiss

Methods inherited from class BSTTree

addAnimator, constructAnimatingBSTTree, constructBSTTree, constructDrawingBSTTree, copyBSTTree, drawLeftLink, drawNode, drawNode, drawNode, drawNodeAndLeftLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndRightLink, drawRightLink, drawTree, eraseNodeAndLink, fixLevel, fixTreeType, getAnimator, getChildren, getCurrentGraphics, getCurrentPower2, getCurrentShape, getCurrentTransform, getDrawingLevel, getHead, getInorderCount, getKey, getKeyOriginRectangle, getLeftTree, getLevel, getNodeOriginShape, getParentTree, getPreviousTransform, getRightTree, getSectionHeight, getSettings, getTreeType, getValue, insert, inTree, isAnimateDrawing, isAnimatingBSTTree, isDrawingBSTTree, isEmpty, isNodeAnimating, isSettingsSaved, join, makeInorderTree, makeInsertAnimation, makePostorderTree, makePreorderTree, makeSearchAnimation, makeSelectionAnimation, makeTree, partition, remove, restoreLeftSettings, restoreRightSettings, restoreSettings, restoreTransform, rotateLeft, rotateRight, saveLeftSettings, saveRightSettings, saveSettings, select, setAnimateDrawing, setCurrentGraphics, setCurrentPower2, setCurrentTransform, setDrawingLevel, setHead, setInorderCount, setLeaf, setLeftTree, setLevel, setNode, setNodeSettings, setParentTree, setRightTree, setSettings, setSize

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface Tree

getChildren, getKey, getLevel, getParentTree, getValue, isEmpty

Field Detail

TREE_INFORMATION

public static final java.lang.String TREE_INFORMATION

String representing information regarding the type of tree.

See Also:

Constant Field Values

Constructor Detail

SplayTreeHead

public SplayTreeHead()

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.

SplayTreeHead

public SplayTreeHead(int treeType)

Constructs a new, empty RootInsertionBSTTreeHead according to the type passed.

Parameters:

treeType - type of tree that should be implemented.

Method Detail

getTreeTypeString

public java.lang.String getTreeTypeString()

Gets the tree type String for the BSTTree.

Overrides:

getTreeTypeString in class BSTTree

Returns:

tree type String for the tree.

averageInsertion

public double averageInsertion(int n)

Returns the average Insertion time, according to n, the amount of elements in the tree.

Overrides:

averageInsertion in class BSTTreeHead

Parameters:

n - the size of the tree for which the average search hit is needed.

Returns:

double the is the average search hit.

waitingAction

public void waitingAction(java.lang.String action,
                          java.lang.Object element)

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!

Specified by:

waitingAction in interface TreeHead

Overrides:

waitingAction in class BSTTreeHead

Parameters:

action - String action representing the next action for the BSTTreeHead.

element - element to which the action could be occuring, depending on the type of action.

insert

public void insert(Tree node)
            throws java.lang.ClassCastException

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.

Overrides:

insert in class BSTTreeHead

Parameters:

node - BSTTree which is added to the tree.

Throws:

java.lang.ClassCastException - key cannot be compared with the keys currently in the map.

search

public Tree search(java.lang.Comparable keySearch)
            throws java.lang.ClassCastException,
                   java.lang.NullPointerException

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.

Specified by:

search in interface TreeHead

Overrides:

search in class BSTTreeHead

Parameters:

keySearch - comparable object which is search for within the tree.

Returns:

Tree element which matches the keySearch or the nearest node or null if the search is impossible to perform.

Throws:

java.lang.ClassCastException - key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - key is null.

insertAnimatingType

protected void insertAnimatingType(BSTTree node)
                            throws java.lang.ClassCastException

Insert the comaparable node to the tree using its natural ordering .

Makes insert a waitingAction if the tree is animating.

Overrides:

insertAnimatingType in class BSTTreeHead

Parameters:

node - BSTTree node to be inserted into the tree

Throws:

java.lang.ClassCastException - key cannot be compared with the keys currently in the map.