Class BSTTreeHead

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

All Implemented Interfaces:

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

Direct Known Subclasses:

BalancedBSTTreeHead, RedBlackTreeHead, RootInsertionBSTTreeHead, SplayTreeHead

public class BSTTreeHead

extends BSTTree

implements TreeHead, AnimationListener, AnimatingTreeHead

This class provides the head structure for a BSTTree. It implements the interface for TreeHead and implements all important methods necessary for maintaining a Binary Search Tree. The BSTTreeHead additionally extends BSTTree, using the information and methods of a BSTTree in addition to the specialized methods of a BSTTreeHead.

Nested Class Summary

class

BSTTreeHead.NodeAndKey An object which keeps both a BSTTree node and an integer key.

Field Summary

static int	BINARY_DISPLAY Binary Display
static int	SECTIONAL_DISPLAY sectional display
static java.lang.String	TREE_INFORMATION String representing information regarding the type of tree.

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

BSTTreeHead()
Constructs a new, null BSTTreeHead, sorted according to the keys' natural order.

BSTTreeHead(int treeType)
Constructs a new, empty BSTTree according to the type passed.

Method Summary

void	addTreeAnimator(Animation a) Adds the Animation to the list of Animations for the Head.
void	addTreeMessageListener(TreeMessageListener l) Adds an TreeMessageListener from the TREE, according to the TreeMessageListener interface and the TreeMessageEvent.
void	AnimateTree(java.awt.Graphics2D g2) Animates the entire BSTTree.
void	animationEventPerformed(AnimationEvent e) Implements AnimationListener which requires the following method.
double	averageInsertion(int n) Returns the average Insertion time, according to n, the amount of elements in the tree.
double	averageSearchHit(int n) Returns the average Search hit time, according to n, the amount of elements in the tree.
double	averageSearchMiss(int n) Returns the average Search miss time, according to n, the amount of elements in the tree.
void	balance(Tree node) Balances the tree, from the node downward, recursively rotating the median to the top.
void	balanceAnimatingType(BSTTree node) Balances the tree from the given node, recursively rotating the median to the top.
void	balanceTree() Balances the entire tree, recursively rotating the median to the top.
void	balanceTreeType(BSTTree node) Balances the tree from the given node, recursively rotating the median to the top.
void	changeDisplay() Changes the display of the current tree.
void	changeDisplayAnimatingType() Change Display of the BSTTree.
void	changeDisplayTreeType() Change Display of the BSTTree.
void	clear() Clears the BSTTree completely, removing all references to all nodes and all values return to the default.
void	clearAnimators() Clears the Animations from the list of Animations for the Head.
void	constructAnimatingBSTTreeHead() Constructor for the ANIMATING_BST_TREE_TYPE.
void	constructBSTTreeHead() Constructor for the BST_TREE_TYPE.
void	constructDrawingBSTTreeHead() Constructor for the DRAWING_BST_TREE_TYPE.
void	DrawTree(java.awt.Graphics2D g2) Draws the entire tree from the null head down.
DrawingTree	findNode(double x, double y) Finds the node represented by the x-y coordinates given.
void	fixLevel() Fixes the lowest level of the Tree, using recursive calls into the BSTTree.
int	fixSize() Fixes the size of each subtree, using recursive calls into the BSTTree.
protected java.awt.Color	getBackgroundColor() Sets the background paint for the tree.
Tree	getChild() Gets the child of the TreeHead.
PaintSettings	getDeleteLeftLinePaintSettings() Gets the Paint for the left line of Paint.
PaintSettings	getDeleteRightLinePaintSettings() Gets the Paint for the right line of Paint.
int	getDisplay() Gets the display choice for the tree.
KeySettings	getDrawingKeySettings() Gets the KeySettings for the entire tree.
NodeSettings	getDrawingNodeSettings() Gets the NodeSettings for the entire tree.
java.util.LinkedList	getInorderTree() Makes a inorder representation of the tree in an array of BSTTrees.
KeySettings	getInsertAnimatorKeySettings() Gets the KeySettings for the animator key settings for insertion.
NodeSettings	getInsertAnimatorNodeSettings() Gets the NodeSettings for the animator node settings for insertion.
NodeSettings	getInsertNodeLeftSettings() Gets the NodeSettings for the left node settings for insertion.
NodeSettings	getInsertNodeRightSettings() Gets the NodeSettings for the right node settings for insertion.
java.util.LinkedList	getLevelorderTree() Makes a levelorder representation of the tree in an array of BSTTrees.
double	getNodeHeight() Gets the height of the standard node within the tree.
double	getNodeWidth() Gets the width of the standard node within the tree.
java.util.LinkedList	getPostorderTree() Makes a postorder representation of the tree in an array of BSTTrees.
java.util.LinkedList	getPreorderTree() Makes a preorder representation of the tree in an array of BSTTrees.
int	getPreviousDisplay() Gets the previous display choice for the tree.
KeySettings	getRotateAnimatorKeySettings() Gets the KeySettings for the animator key settings for rotation.
NodeSettings	getRotateChildNodeSettings() Gets the NodeSettings for the child node settings for rotation.
NodeSettings	getRotateDescendantNodeSettings() Gets the NodeSettings for the descendant node settings for rotation.
KeySettings	getRotateOriginalKeySettings() Gets the KeySettings for the original key settings for rotation.
NodeSettings	getRotateOriginalNodeSettings() Gets the NodeSettings for the original node settings for rotation.
NodeSettings	getRotateRootNodeSettings() Gets the NodeSettings for the root node settings for rotation.
java.awt.geom.Rectangle2D	getScreenBounds() Gets the bounds of the screen to which the tree is drawing.
KeySettings	getSearchAnimatorKeySettings() Gets the KeySettings for the animator key settings for searching.
NodeSettings	getSearchAnimatorNodeSettings() Gets the NodeSettings for the animator node settings for searching.
NodeSettings	getSearchNodeLeftSettings() Gets the NodeSettings for the left node settings for searching.
NodeSettings	getSearchNodeRightSettings() Gets the NodeSettings for the right node settings for searching.
KeySettings	getSelectAnimatorKeySettings() Gets the KeySettings for the animator key settings for selection.
NodeSettings	getSelectAnimatorNodeSettings() Gets the NodeSettings for the animator node settings for selection.
NodeSettings	getSelectNodeLeftSettings() Gets the NodeSettings for the left node settings for selection.
NodeSettings	getSelectNodeRightSettings() Gets the NodeSettings for the right node settings for selection.
KeySettings	getTraverseAnimatorKeySettings() Gets the KeySettings for the animator key settings for traversal.
NodeSettings	getTraverseAnimatorNodeSettings() Gets the NodeSettings for the animator node settings for traversal.
int	getTreeAnimationStepSize() Gets the step size of the Animations of the tree.
Animation	getTreeAnimator() Gets the first Animation in the list of Animations for the Head and null if no Animations are present.
int	getTreeLevel() Gets the lowest level of the Tree.
protected double	getTreeSectionHeight() Returns the height of the section, used for rendering the tree.
java.lang.String	getTreeStatus() Gets the Tree's status, using the String status of Animation.
java.lang.String	getTreeStatusMessage() Makes a new tree message.
protected WaitingActionList	getWaitingList() Gets the WaitingActionList representing the waitingList for the tree.
boolean	insert(java.lang.Comparable keyInsert, java.lang.Object valueInsert) Inserts the comaparable object keyInsert to the tree using its natural ordering .
void	insert(Tree node) Inserts the node to the tree using its natural ordering .
protected void	insertAnimatingType(BSTTree node) Inserts the comaparable node to the tree using its natural ordering .
protected void	insertDrawingType(BSTTree node) Insert the comaparable node to the tree using its natural ordering .
protected void	insertTreeType(BSTTree node) Insert the comaparable node to the tree using its natural ordering .
boolean	isJumpStep() Gets the JumpStep of the current tree.
boolean	isStepPause() Gets the StepPause of the current tree.
boolean	isTreeAnimating() Returns true if the current AnimatingBSTTreeHead is animating (whether the animating list is empty.
boolean	isTreeEmpty() Returns true if the is empty, indicating no Child node, and a level of 0.
boolean	isTreeRemove() Gets whether the AnimatingBSTTreeHead is removing an Animation.
Animation	makeBalanceAnimation(BSTTree node) Makes a balance Animation using the given node.
Animation	makeChangeDisplayAnimation() Makes a changeDisplay Animation.
Animation	makeDeletionAnimation(BSTTree node) Makes a deletion Animation using the given node.
Animation	makeInsertAnimation(BSTTree insertNode) Makes an insert Animation using the given node.
protected BSTTree	makeNode(java.lang.Comparable keyInsert, java.lang.Object valueInsert) Makes and places the node into the tree.
protected BSTTree	makeNodeDrawingType(java.lang.Comparable keyInsert, java.lang.Object valueInsert) Makes and places the node into the tree.
protected BSTTree	makeNodeTreeType(java.lang.Comparable keyInsert, java.lang.Object valueInsert) Makes and places the node into the tree.
Animation	makePartitionAnimation(BSTTree node, int keySelect) Makes a partition Animation using the given node and given keySelect.
Animation	makeRotationAnimation(BSTTree node) Makes a rotation Animation using the given node.
Animation	makeRotationDoubleAnimation(BSTTree node) Makes a rotationDouble Animation using the given node.
Animation	makeSearchAnimation(java.lang.Comparable keySearch) Makes a search Animation using the given keySearch.
Animation	makeSelectionAnimation(BSTTree node, int keySelect) Makes a select Animation using the given keySelect.
Animation	makeTraverseAnimation(java.util.LinkedList nodeList) Makes a traverse Animation using the given LinkedList.
void	MakeTree(java.awt.Graphics2D g2) Makes the entire tree from the null head down.
protected void	messageAction(java.lang.String msg) Calls all of the listeners of the Tree and passes the tree message information information regarding the status of the Tree.
protected void	messageAction(java.lang.String msg, java.lang.Object msgObj) Calls all of the listeners of the Tree and passes the tree message information information regarding the status of the Tree.
Tree	partition(Tree node, int keySelect) Partitions from the given node the keySelect value.
protected Tree	partitionAnimatingType(BSTTree node, int keySelect) Partitions from the given node the keySelect value.
protected BSTTree	partitionTreeType(BSTTree node, int keySelect) Partitions from the given node the keySelect value.
void	pause() Sets the status of the AnimatingBSTTree to pause.
void	play() Sets the status of the AnimatingBSTTree to play.
boolean	remove(java.lang.Comparable keyRemove) Removes the comaparable object keyRemove from the BSTTree using its natural ordering .
void	remove(Tree node) Removes the given node from the tree.
protected void	removeAnimatingType(BSTTree node) Removes the node in the BSTTree.
void	removeTreeAnimation() Quickly removes all Animations within the Tree.
void	removeTreeMessageListener(TreeMessageListener l) Removes an TreeMessageListener from the TREE, according to the TreeMessageListener interface and the TreeMessageEvent.
void	removeTreeType(BSTTree node) Removes the given node from the tree.
void	resetTreeLevel() Resets the lowest level of the Tree.
void	rewind() Sets the status of the AnimatingBSTTree to rewind.
void	rotateToTop(BSTTree node) Rotates the BSTTTree to the top.
protected void	rotateToTopAnimatingType(BSTTree node) Rotates to top the node in the BSTTree.
protected void	rotateToTopTreeType(BSTTree node) Rotates to top the node up in the BSTTree.
void	rotateUp(BSTTree node) Rotates the BSTTree up.
void	rotateUp(BSTTree node, int levelCount) Rotates the BSTTree up.
protected void	rotateUpAnimatingType(BSTTree node) Rotates the node up in the BSTTree.
void	rotateUpDouble(BSTTree node) Double Rotatation of the BSTTTree.
void	rotateUpDouble(BSTTree node, int levelCount) Doubly Rotates the BSTTree up to the top.
protected void	rotateUpDoubleAnimatingType(BSTTree node) Double Rotates the node up in the BSTTree.
void	rotateUpDoubleTreeType(BSTTree node) Double Rotates the BSTTree up.
void	rotateUpTreeType(BSTTree node) Rotates the BSTTree up.
Tree	search(java.lang.Comparable keySearch) Searches for the comaparable object in the Tree using its natural ordering .
protected Tree	searchAnimatingType(java.lang.Comparable keySearch) Searches for the Tree in the entire tree.
Tree	searchTreeType(java.lang.Comparable keySearch) Searches for the Tree in the entire tree.
Tree	select(Tree node, int keySelect) Selects the kth smallest item in the Tree using its natural ordering from the given node.
protected Tree	selectAnimatingType(BSTTree node, int keySelect) Selects for the Tree in the entire tree.
Tree	selectTreeType(BSTTree node, int keySelect) Selects for the Tree in the entire tree.
protected void	setBackgroundColor(java.awt.Color background) Sets the background paint for the tree.
void	setChild(Tree child) Sets the child of the TreeHead.
void	setDeleteLeftLinePaintSettings(PaintSettings p) Sets the PaintSettings for the left line of Paint.
void	setDeleteRightLinePaintSettings(PaintSettings p) Sets the PaintSettings for the right line of Paint.
void	setDisplay(int display) Sets the display choice for the tree.
void	setDrawingKeySettings(KeySettings k) Sets the KeySettings for the key of the head, used in creation of new nodes.
void	setDrawingNodeSettings(NodeSettings s) Sets the NodeSettings for the node of the head, used in creation of new nodes.
void	setInsertAnimatorKeySettings(KeySettings k) Sets the KeySettings for the animator key settings for insertion.
void	setInsertAnimatorNodeSettings(NodeSettings n) Sets the NodeSettings for the animator node settings for insertion.
void	setInsertNodeLeftSettings(NodeSettings n) Sets the NodeSettings for the left node settings for insertion.
void	setInsertNodeRightSettings(NodeSettings n) Sets the NodeSettings for the right node settings for insertion.
void	setJumpStep(boolean b) Sets the JumpStep of the current tree to the boolean value.
protected void	setNodeHeight(double height) Sets the node height for the standard node.
protected void	setNodeWidth(double width) Sets the node width for the standard node.
void	setPreviousDisplay(int previousDisplay) Sets the previous display choice for the tree.
protected void	setRemove(boolean b) Sets whether the AnimatingBSTTreeHead is removing an Animation, because multiple Animations may occur simultaneously.
void	setRotateAnimatorKeySettings(KeySettings k) Sets the KeySettings for the animator key settings for rotation.
void	setRotateChildNodeSettings(NodeSettings n) Sets the NodeSettings for the child node settings for rotation.
void	setRotateDescendantNodeSettings(NodeSettings n) Sets the NodeSettings for the descendant node settings for rotation.
void	setRotateOriginalKeySettings(KeySettings k) Sets the KeySettings for the original key settings for rotation.
void	setRotateOriginalNodeSettings(NodeSettings n) Sets the NodeSettings for the original node settings for rotation.
void	setRotateRootNodeSettings(NodeSettings n) Sets the NodeSettings for the root node settings for rotation.
void	setScreenBounds(java.awt.geom.Rectangle2D screen) Sets the bounds of the screen to which the tree is drawing.
void	setSearchAnimatorKeySettings(KeySettings k) Sets the KeySettings for the animator key settings for searching.
void	setSearchAnimatorNodeSettings(NodeSettings n) Sets the NodeSettings for the animator node settings for searching.
void	setSearchNodeLeftSettings(NodeSettings n) Sets the NodeSettings for the left node settings for searching.
void	setSearchNodeRightSettings(NodeSettings n) Sets the NodeSettings for the right node settings for searching.
protected void	setSectionHeight(double height) Sets the height of the section, used for rendering the tree.
void	setSelectAnimatorKeySettings(KeySettings k) Sets the KeySettings for the animator key settings for selection.
void	setSelectAnimatorNodeSettings(NodeSettings n) Sets the NodeSettings for the animator node settings for selection.
void	setSelectNodeLeftSettings(NodeSettings n) Sets the NodeSettings for the left node settings for selection.
void	setSelectNodeRightSettings(NodeSettings n) Sets the NodeSettings for the right node settings for selection.
void	setStepPause(boolean b) Sets the StepPause of the current tree to the boolean value.
void	setTraverseAnimatorKeySettings(KeySettings k) Sets the KeySettings for the animator key settings for traversal.
void	setTraverseAnimatorNodeSettings(NodeSettings n) Sets the NodeSettings for the animator node settings for traversal.
void	setTreeAnimationsStepSize(int t) Sets the step size of the Animations of the tree.
protected void	setTreeLevel(int level) Sets the lowest level of the Tree, used in numerous methods.
void	setTreeSettings(NodeSettings s, KeySettings k) Sets the NodeSettings for the entire tree from the head down.
void	setTreeStatus(java.lang.String s) Sets the Status of the entire tree, using the status of Animation class.
void	setTreeType(int treeType) Sets the tree type for the BSTTree.
int	size() Returns the number of objects in the entire tree.
void	splay(BSTTree node) Splays the BSTTTree to the top (Double rotates).
protected void	splayAnimatingType(BSTTree node) Splays the node up in the BSTTree.
protected void	splayTreeType(BSTTree node) Splays the node up in the BSTTree.
void	stop() Sets the status of the AnimatingBSTTree to stop.
java.util.LinkedList	traverse(int traverseType) Traverses the tree in the given traversal type.
java.util.LinkedList	traverseAnimatingType(int traverseType) Traverses the tree in the given traversal type.
java.util.LinkedList	traverseTreeType(int traverseType) Traverses the tree in the given traversal type.
void	waitingAction(java.lang.String action, java.lang.Object element) Acts according to the String action passed.
double	worstCaseInsertion(int n) Returns the worst case Insertion time, according to n, the amount of elements in the tree.
double	worstCaseSearchHit(int n) Returns the worst case Search hit time, according to n, the amount of elements in the tree.
double	worstCaseSearchMiss(int n) Returns the worst case Search miss time, according to n, the amount of elements in the tree.

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, getTreeTypeString, 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

BINARY_DISPLAY

public static final int BINARY_DISPLAY

Binary Display

See Also:

Constant Field Values

SECTIONAL_DISPLAY

public static final int SECTIONAL_DISPLAY

sectional display

See Also:

Constant Field Values

Constructor Detail

BSTTreeHead

public BSTTreeHead()

Constructs a new, null BSTTreeHead, sorted according to the keys' natural order.

Default type is BST_TREE_TYPE.

BSTTreeHead

public BSTTreeHead(int treeType)

Constructs a new, empty BSTTree according to the type passed. The options for the types are BST_TREE_TYPE, DRAWING_BST_TREE_TYPE, and ANIMATING_BST_TREE_TYPE. The types are defined as follows:

• BST_TREE_TYPE: Only implements the basic methods of a Binary Search Tree. A lot of the expensive (huge overhead) information necessary for drawing and animating are left not instantiated to save time. This basic type is simply for BST usage.
• DRAWING_BST_TREE_TYPE: Implements the methods necessary to draw the BST onto the screen. This includes a lot of overhead data that is necessary for rendering the tree.
• ANIMATING_BST_TREE_TYPE: This implements the rest of the methods necessary to animate the tree. The overhead is small for the animating methods, but for every method possible, the animation occurs. Therefore, to stop animation, the node must be set to just DRAWING_BST_TREE_TYPE and then the method will ignore the animation.

Parameters:

treeType - type of tree that should be implemented.

Method Detail

setTreeType

public void setTreeType(int treeType)

Sets the tree type for the BSTTree. It additionally checks constructors for the head.

Overrides:

setTreeType in class BSTTree

Parameters:

treeType - setting for the tree.

messageAction

protected void messageAction(java.lang.String msg)

Calls all of the listeners of the Tree and passes the tree message information information regarding the status of the Tree.

Parameters:

msg - String message being passed to all TreeMessage listeners.

messageAction

protected void messageAction(java.lang.String msg,
                             java.lang.Object msgObj)

Calls all of the listeners of the Tree and passes the tree message information information regarding the status of the Tree.

Parameters:

msg - String message being passed to all TreeMessage listeners.

msgObj - Object related to the message and usable by all listeners.

addTreeMessageListener

public void addTreeMessageListener(TreeMessageListener l)

Adds an TreeMessageListener from the TREE, according to the TreeMessageListener interface and the TreeMessageEvent.

Specified by:

addTreeMessageListener in interface TreeHead

Parameters:

l - the listener added recieves the TreeMessageEvents occuring.

removeTreeMessageListener

public void removeTreeMessageListener(TreeMessageListener l)

Removes an TreeMessageListener from the TREE, according to the TreeMessageListener interface and the TreeMessageEvent.

Specified by:

removeTreeMessageListener in interface TreeHead

Parameters:

l - the listener removed from recieving the TreeMessageEvents occuring.

getTreeStatusMessage

public java.lang.String getTreeStatusMessage()

Makes a new tree message. The method calls messageAction with the information necessary for the tree status. The information presented include :

• Tree Type
• Tree Size
• Tree Level

Specified by:

getTreeStatusMessage in interface AnimatingTreeHead

averageSearchHit

public double averageSearchHit(int n)

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

Parameters:

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

Returns:

double the is the average search hit.

averageSearchMiss

public double averageSearchMiss(int n)

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

Parameters:

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

Returns:

double the is the average search hit.

worstCaseSearchHit

public double worstCaseSearchHit(int n)

Returns the worst case Search hit time, according to n, the amount of elements in the tree.

Parameters:

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

Returns:

double the is the worst case search hit.

worstCaseSearchMiss

public double worstCaseSearchMiss(int n)

Returns the worst case Search miss time, according to n, the amount of elements in the tree.

Parameters:

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

Returns:

double the is the worst case search hit.

averageInsertion

public double averageInsertion(int n)

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

Parameters:

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

Returns:

double the is the average search hit.

worstCaseInsertion

public double worstCaseInsertion(int n)

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

Parameters:

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

Returns:

double the is the worst case search hit.

waitingAction

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

Acts according to the String action passed. The method generally accompanies a WaitingActionList which keeps the list of actions, and calls the method when instructed to call the next action.

Specified by:

waitingAction in interface TreeHead

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.

getWaitingList

protected WaitingActionList getWaitingList()

Gets the WaitingActionList representing the waitingList for the tree. This allows extension of the class have tthe ability to modify the attributes of the list.

Returns:

WaitingActionList waiting list for the tree.

constructBSTTreeHead

public void constructBSTTreeHead()

Constructor for the BST_TREE_TYPE. This constructs and sets all values to defaults for the BST_TREE_TYPE.

isTreeEmpty

public boolean isTreeEmpty()

Returns true if the is empty, indicating no Child node, and a level of 0.

Specified by:

isTreeEmpty in interface TreeHead

Returns:

true if the TreeHead is empty.

getChild

public Tree getChild()

Gets the child of the TreeHead. The child is the beginning of the Tree nodes.

Specified by:

getChild in interface TreeHead

getTreeLevel

public int getTreeLevel()

Gets the lowest level of the Tree. A level of 0 indicates an empty tree.

Specified by:

getTreeLevel in interface TreeHead

Returns:

integer level set for the Tree.

size

public int size()

Returns the number of objects in the entire tree.

Specified by:

size in interface TreeHead

Overrides:

size in class BSTTree

Returns:

the number of objects in the entire tree.

setChild

public void setChild(Tree child)

Sets the child of the TreeHead. The child is the beginning of the Tree nodes.

Specified by:

setChild in interface TreeHead

Parameters:

child - Tree, beginning the Tree nodes.

setTreeLevel

protected void setTreeLevel(int level)

Sets the lowest level of the Tree, used in numerous methods. The level must remain very accurate. A level of 0 indicates an empty Tree.

Parameters:

level - integer level set for the BSTTree.

resetTreeLevel

public void resetTreeLevel()

Resets the lowest level of the Tree. The level is set to 0, so that is can be recalculated, using fixLevel.

Specified by:

resetTreeLevel in interface TreeHead

fixLevel

public void fixLevel()

Fixes the lowest level of the Tree, using recursive calls into the BSTTree. Generally, resetTreeLevel is called before the method.

Specified by:

fixLevel in interface TreeHead

fixSize

public int fixSize()

Fixes the size of each subtree, using recursive calls into the BSTTree.

Overrides:

fixSize in class BSTTree

Returns:

integer of the size fixed, which is passed up through the BSTTree, recursively.

makeNode

protected BSTTree makeNode(java.lang.Comparable keyInsert,
                           java.lang.Object valueInsert)
                    throws java.lang.ClassCastException

Makes and places the node into the tree. The node is returned for further manipulation.

Parameters:

keyInsert - comparable object which is added to the tree.

valueInsert - Object that accompanies keyInsert in the node.

Returns:

BSTTree that was recently inserted into the tree.

Throws:

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

clear

public void clear()

Clears the BSTTree completely, removing all references to all nodes and all values return to the default.

Specified by:

clear in interface TreeHead

insert

public boolean insert(java.lang.Comparable keyInsert,
                      java.lang.Object valueInsert)
               throws java.lang.NullPointerException,
                      java.lang.ClassCastException

Inserts the comaparable object keyInsert to the tree using its natural ordering . The value, valueInsert is added with the key to the node.

Specified by:

insert in interface TreeHead

Parameters:

keyInsert - comparable object which is added to the tree.

valueInsert - Object that accompanies keyInsert in the node.

Returns:

boolean true if this collection changed as a result of the call.

Throws:

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

java.lang.NullPointerException - key is null.

insert

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

Inserts the node to the tree using its natural ordering .

Parameters:

node - BSTTree which is added to the tree.

Throws:

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

remove

public void remove(Tree node)

Removes the given node from the tree. The accompanying value is also removed from the tree and the node is deleted.

Specified by:

remove in interface TreeHead

Parameters:

node - the Tree node to be removed from the tree.

remove

public boolean remove(java.lang.Comparable keyRemove)
               throws java.lang.ClassCastException,
                      java.lang.NullPointerException

Removes the comaparable object keyRemove from the BSTTree using its natural ordering . If the method is successful in removing the element, true is returned.

Specified by:

remove in interface TreeHead

Parameters:

keyRemove - comparable object which is removed from the tree.

Returns:

boolean true if this collection changed as a result of the call.

Throws:

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

java.lang.NullPointerException - key is null.

balanceTree

public void balanceTree()

Balances the entire tree, recursively rotating the median to the top.

Specified by:

balanceTree in interface TreeHead

balance

public void balance(Tree node)

Balances the tree, from the node downward, recursively rotating the median to the top.

Specified by:

balance in interface TreeHead

Parameters:

node - the node from which the balance occurs

partition

public Tree partition(Tree node,
                      int keySelect)

Partitions from the given node the keySelect value. Replacing the reference in the Tree to the given node, to the keySelectth item.

Specified by:

partition in interface TreeHead

Parameters:

keySelect - integer key selecting the count item.

node - Tree which the partition occurs at.

Returns:

Tree that is the reference to the newly partitioned tree.

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.

Specified by:

search in interface TreeHead

Overrides:

search in class BSTTree

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.

select

public Tree select(Tree node,
                   int keySelect)

Selects the kth smallest item in the Tree using its natural ordering from the given node. If the method is successful in finding the element, the item is returned. Otherwise, null is returned if the integer is greater than the size.

Specified by:

select in interface TreeHead

Parameters:

keySelect - integer key selecting the count item.

node - Tree which the partition occurs at.

Returns:

Tree element which matches the kth element or null if k > size.

rotateUp

public void rotateUp(BSTTree node)

Rotates the BSTTree up. It simply changes around references, including the parent reference and the ancestor reference. The rotation upwards replaces the parent with the node and brings the parent down a level.

Parameters:

node - BSTTree that rotated upwards.

rotateUp

public void rotateUp(BSTTree node,
                     int levelCount)

Rotates the BSTTree up. It simply changes around references, including the parent reference and the ancestor reference. The rotation upwards replaces the parent with the node and brings the parent down a level.

Parameters:

node - BSTTree that rotated upwards.

levelCount - the amount of levels up the node should rotate

rotateUpDouble

public void rotateUpDouble(BSTTree node)

Double Rotatation of the BSTTTree.

Parameters:

node - BSTTree that is double rotated (bottom rotation first).

rotateUpDouble

public void rotateUpDouble(BSTTree node,
                           int levelCount)

Doubly Rotates the BSTTree up to the top. This is also referred to as a Splay and is the basis for a splay tree if the double rotation occurs to the top.

Parameters:

node - BSTTree that rotated upwards.

levelCount - the amount of levels up the node should rotate

rotateToTop

public void rotateToTop(BSTTree node)

Rotates the BSTTTree to the top.

Parameters:

node - BSTTree that is rotated to the top.

splay

public void splay(BSTTree node)

Splays the BSTTTree to the top (Double rotates).

Parameters:

node - BSTTree that is rotated to the top.

changeDisplay

public void changeDisplay()

Changes the display of the current tree.

traverse

public java.util.LinkedList traverse(int traverseType)

Traverses the tree in the given traversal type.

Parameters:

traverseType - int defining the given traversal type.

makeNodeTreeType

protected BSTTree makeNodeTreeType(java.lang.Comparable keyInsert,
                                   java.lang.Object valueInsert)

Makes and places the node into the tree. The node is returned for further manipulation.

Parameters:

keyInsert - comparable object which is added to the tree.

valueInsert - Object that accompanies keyInsert in the node.

Returns:

BSTTree that was recently inserted into the tree.

Throws:

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

insertTreeType

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

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

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.

removeTreeType

public void removeTreeType(BSTTree node)

Removes the given node from the tree. The accompanying value is also removed from the tree and the node is deleted.

Parameters:

node - the Tree node to be removed from the tree.

partitionTreeType

protected BSTTree partitionTreeType(BSTTree node,
                                    int keySelect)

Partitions from the given node the keySelect value. Replacing the reference in the Tree to the given node, to the keySelectth item.

Parameters:

keySelect - integer key selecting the count item.

Returns:

Tree that is the reference to the newly partitioned tree.

balanceTreeType

public void balanceTreeType(BSTTree node)

Balances the tree from the given node, recursively rotating the median to the top.

Parameters:

node - BSTTree that is balanced from.

searchTreeType

public Tree searchTreeType(java.lang.Comparable keySearch)
                    throws java.lang.ClassCastException

Searches for the Tree in the entire tree.

Parameters:

keySearch - the comparable key which is searched for within the tree.

Returns:

Tree the Tree found or null if keySearch was not present within the tree.

Throws:

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

selectTreeType

public Tree selectTreeType(BSTTree node,
                           int keySelect)
                    throws java.lang.ClassCastException

Selects for the Tree in the entire tree.

Parameters:

node - the node from which the selection takes place.

keySelect - integer key selecting the count item.

Returns:

Tree the Tree found or null.

Throws:

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

rotateUpTreeType

public void rotateUpTreeType(BSTTree node)

Rotates the BSTTree up. It simply changes around references, including the parent reference and the ancestor reference. The rotation upwards replaces the parent with the node and brings the parent down a level.

Parameters:

node - BSTTree that rotated upwards.

rotateUpDoubleTreeType

public void rotateUpDoubleTreeType(BSTTree node)

Double Rotates the BSTTree up.

Parameters:

node - BSTTree that rotated upwards.

splayTreeType

protected void splayTreeType(BSTTree node)

Splays the node up in the BSTTree.

Parameters:

node - BSTTree node that is splayed.

rotateToTopTreeType

protected void rotateToTopTreeType(BSTTree node)

Rotates to top the node up in the BSTTree.

Parameters:

node - BSTTree node that is rotated up.

traverseTreeType

public java.util.LinkedList traverseTreeType(int traverseType)

Traverses the tree in the given traversal type.

Parameters:

traverseType - int defining the given traversal type.

changeDisplayTreeType

public void changeDisplayTreeType()

Change Display of the BSTTree.

getPreorderTree

public java.util.LinkedList getPreorderTree()

Makes a preorder representation of the tree in an array of BSTTrees. Changes in the references in the array have no effect upon the tree.

Returns:

LinkedList of BSTTree objects that are the preorder representation of the tree.

getInorderTree

public java.util.LinkedList getInorderTree()

Makes a inorder representation of the tree in an array of BSTTrees. Changes in the references in the array have no effect upon the tree.

Returns:

LinkedList of BSTTree objects that are the preorder representation of the tree.

getPostorderTree

public java.util.LinkedList getPostorderTree()

Makes a postorder representation of the tree in an array of BSTTrees. Changes in the references in the array have no effect upon the tree.

Returns:

LinkedList of BSTTree objects that are the preorder representation of the tree.

getLevelorderTree

public java.util.LinkedList getLevelorderTree()

Makes a levelorder representation of the tree in an array of BSTTrees. Changes in the references in the array have no effect upon the tree.

Returns:

Array of BSTTree objects that are the preorder representation of the tree.

constructDrawingBSTTreeHead

public void constructDrawingBSTTreeHead()

Constructor for the DRAWING_BST_TREE_TYPE. This constructs and sets all values to defaults for the DRAWING_BST_TREE_TYPE.

getDisplay

public int getDisplay()

Gets the display choice for the tree.

Returns:

the integer that defines the display choice of the tree.

getPreviousDisplay

public int getPreviousDisplay()

Gets the previous display choice for the tree.

Returns:

the integer that defines the display choice of the tree.

getDrawingNodeSettings

public NodeSettings getDrawingNodeSettings()

Gets the NodeSettings for the entire tree.

Specified by:

getDrawingNodeSettings in interface DrawingTreeHead

Returns:

NodeSettings for defined for the entire tree.

getDrawingKeySettings

public KeySettings getDrawingKeySettings()

Gets the KeySettings for the entire tree.

Specified by:

getDrawingKeySettings in interface DrawingTreeHead

Returns:

KeySettings for defined for the entire tree.

getNodeWidth

public double getNodeWidth()

Gets the width of the standard node within the tree. Every node is not necessarily the same width, but the standard is set within the Head.

Specified by:

getNodeWidth in interface DrawingTreeHead

Returns:

width of the standard node.

getNodeHeight

public double getNodeHeight()

Gets the height of the standard node within the tree. Every node is not necessarily the same height, but the standard is set within the Head.

Specified by:

getNodeHeight in interface DrawingTreeHead

Returns:

height of the standard node.

getScreenBounds

public java.awt.geom.Rectangle2D getScreenBounds()

Gets the bounds of the screen to which the tree is drawing. The bounds generally is simply the rectangle enclosing the Graphics2D passed.

Specified by:

getScreenBounds in interface DrawingTreeHead

Overrides:

getScreenBounds in class BSTTree

Returns:

the rectangle representing the bounds of the screen.

getTreeSectionHeight

protected double getTreeSectionHeight()

Returns the height of the section, used for rendering the tree.

Returns:

double height of the section.

getBackgroundColor

protected java.awt.Color getBackgroundColor()

Sets the background paint for the tree.

getInsertNodeLeftSettings

public NodeSettings getInsertNodeLeftSettings()

Gets the NodeSettings for the left node settings for insertion.

Returns:

NodeSettings for the left node.

getInsertNodeRightSettings

public NodeSettings getInsertNodeRightSettings()

Gets the NodeSettings for the right node settings for insertion.

Returns:

NodeSettings for the right node.

getInsertAnimatorNodeSettings

public NodeSettings getInsertAnimatorNodeSettings()

Gets the NodeSettings for the animator node settings for insertion.

Returns:

NodeSettings for the animator node.

getInsertAnimatorKeySettings

public KeySettings getInsertAnimatorKeySettings()

Gets the KeySettings for the animator key settings for insertion.

Returns:

KeySettings for the animator key.

getSearchNodeLeftSettings

public NodeSettings getSearchNodeLeftSettings()

Gets the NodeSettings for the left node settings for searching.

Returns:

NodeSettings for the left node.

getSearchNodeRightSettings

public NodeSettings getSearchNodeRightSettings()

Gets the NodeSettings for the right node settings for searching.

Returns:

NodeSettings for the right node.

getSearchAnimatorNodeSettings

public NodeSettings getSearchAnimatorNodeSettings()

Gets the NodeSettings for the animator node settings for searching.

Returns:

NodeSettings for the animator node.

getSearchAnimatorKeySettings

public KeySettings getSearchAnimatorKeySettings()

Gets the KeySettings for the animator key settings for searching.

Returns:

KeySettings for the animator key.

getSelectNodeLeftSettings

public NodeSettings getSelectNodeLeftSettings()

Gets the NodeSettings for the left node settings for selection.

Returns:

NodeSettings for the left node.

getSelectNodeRightSettings

public NodeSettings getSelectNodeRightSettings()

Gets the NodeSettings for the right node settings for selection.

Returns:

NodeSettings for the right node.

getSelectAnimatorNodeSettings

public NodeSettings getSelectAnimatorNodeSettings()

Gets the NodeSettings for the animator node settings for selection.

Returns:

NodeSettings for the animator node.

getSelectAnimatorKeySettings

public KeySettings getSelectAnimatorKeySettings()

Gets the KeySettings for the animator key settings for selection.

Returns:

KeySettings for the animator key.

getRotateRootNodeSettings

public NodeSettings getRotateRootNodeSettings()

Gets the NodeSettings for the root node settings for rotation.

Returns:

NodeSettings for the root node.

getRotateChildNodeSettings

public NodeSettings getRotateChildNodeSettings()

Gets the NodeSettings for the child node settings for rotation.

Returns:

NodeSettings for the child node.

getRotateDescendantNodeSettings

public NodeSettings getRotateDescendantNodeSettings()

Gets the NodeSettings for the descendant node settings for rotation.

Returns:

NodeSettings for the descendant node.

getRotateOriginalNodeSettings

public NodeSettings getRotateOriginalNodeSettings()

Gets the NodeSettings for the original node settings for rotation.

Returns:

NodeSettings for the original node.

getRotateAnimatorKeySettings

public KeySettings getRotateAnimatorKeySettings()

Gets the KeySettings for the animator key settings for rotation.

Returns:

KeySettings for the animator key.

getRotateOriginalKeySettings

public KeySettings getRotateOriginalKeySettings()

Gets the KeySettings for the original key settings for rotation.

Returns:

KeySettings for the original key.

getDeleteLeftLinePaintSettings

public PaintSettings getDeleteLeftLinePaintSettings()

Gets the Paint for the left line of Paint.

Returns:

Paint for the left line.

getDeleteRightLinePaintSettings

public PaintSettings getDeleteRightLinePaintSettings()

Gets the Paint for the right line of Paint. `

Returns:

Paint for the right line.

getTraverseAnimatorNodeSettings

public NodeSettings getTraverseAnimatorNodeSettings()

Gets the NodeSettings for the animator node settings for traversal.

Returns:

NodeSettings for the animator node.

getTraverseAnimatorKeySettings

public KeySettings getTraverseAnimatorKeySettings()

Gets the KeySettings for the animator key settings for traversal.

Returns:

KeySettings for the animator key.

setDisplay

public void setDisplay(int display)

Sets the display choice for the tree.

Parameters:

display - sets the integer that defines the display choice of the tree.

setPreviousDisplay

public void setPreviousDisplay(int previousDisplay)

Sets the previous display choice for the tree.

setTreeSettings

public void setTreeSettings(NodeSettings s,
                            KeySettings k)

Sets the NodeSettings for the entire tree from the head down. These settings are used for drawing the node and the links of each given tree.

Specified by:

setTreeSettings in interface DrawingTreeHead

Overrides:

setTreeSettings in class BSTTree

Parameters:

s - NodeSettings for use in drawing the entire tree.

k - KeySettings for use in drawing the keys of the entire tree.

setDrawingNodeSettings

public void setDrawingNodeSettings(NodeSettings s)

Sets the NodeSettings for the node of the head, used in creation of new nodes.

Parameters:

s - NodeSettings for use in drawing the nodes.

setDrawingKeySettings

public void setDrawingKeySettings(KeySettings k)

Sets the KeySettings for the key of the head, used in creation of new nodes.

Parameters:

k - KeySettings for use in drawing the keys.

setNodeWidth

protected void setNodeWidth(double width)

Sets the node width for the standard node. Generally defined in MakeTree.

Parameters:

width - the width of the node.

setNodeHeight

protected void setNodeHeight(double height)

Sets the node height for the standard node. Generally defined in MakeTree.

Parameters:

height - the height of the node.

setScreenBounds

public void setScreenBounds(java.awt.geom.Rectangle2D screen)

Sets the bounds of the screen to which the tree is drawing. Generally, these bounds are set using getClipBounds on the Graphics2D passed, however, the bounds can be set in any way.

Specified by:

setScreenBounds in interface DrawingTreeHead

Overrides:

setScreenBounds in class BSTTree

setSectionHeight

protected void setSectionHeight(double height)

Sets the height of the section, used for rendering the tree.

Parameters:

height - of the section, used for drawing the tree.

setBackgroundColor

protected void setBackgroundColor(java.awt.Color background)

Sets the background paint for the tree.

Parameters:

background - paint of the background.

setInsertNodeLeftSettings

public void setInsertNodeLeftSettings(NodeSettings n)

Sets the NodeSettings for the left node settings for insertion.

Returns:

NodeSettings for the left node.

setInsertNodeRightSettings

public void setInsertNodeRightSettings(NodeSettings n)

Sets the NodeSettings for the right node settings for insertion.

Returns:

NodeSettings for the right node.

setInsertAnimatorNodeSettings

public void setInsertAnimatorNodeSettings(NodeSettings n)

Sets the NodeSettings for the animator node settings for insertion.

Returns:

NodeSettings for the animator node.

setInsertAnimatorKeySettings

public void setInsertAnimatorKeySettings(KeySettings k)

Sets the KeySettings for the animator key settings for insertion.

Returns:

KeySettings for the animator key.

setSearchNodeLeftSettings

public void setSearchNodeLeftSettings(NodeSettings n)

Sets the NodeSettings for the left node settings for searching.

Returns:

NodeSettings for the left node.

setSearchNodeRightSettings

public void setSearchNodeRightSettings(NodeSettings n)

Sets the NodeSettings for the right node settings for searching.

Returns:

NodeSettings for the right node.

setSearchAnimatorNodeSettings

public void setSearchAnimatorNodeSettings(NodeSettings n)

Sets the NodeSettings for the animator node settings for searching.

Returns:

NodeSettings for the animator node.

setSearchAnimatorKeySettings

public void setSearchAnimatorKeySettings(KeySettings k)

Sets the KeySettings for the animator key settings for searching.

Returns:

KeySettings for the animator key.

setSelectNodeLeftSettings

public void setSelectNodeLeftSettings(NodeSettings n)

Sets the NodeSettings for the left node settings for selection.

Returns:

NodeSettings for the left node.

setSelectNodeRightSettings

public void setSelectNodeRightSettings(NodeSettings n)

Sets the NodeSettings for the right node settings for selection.

Returns:

NodeSettings for the right node.

setSelectAnimatorNodeSettings

public void setSelectAnimatorNodeSettings(NodeSettings n)

Sets the NodeSettings for the animator node settings for selection.

Returns:

NodeSettings for the animator node.

setSelectAnimatorKeySettings

public void setSelectAnimatorKeySettings(KeySettings k)

Sets the KeySettings for the animator key settings for selection.

Returns:

KeySettings for the animator key.

setRotateRootNodeSettings

public void setRotateRootNodeSettings(NodeSettings n)

Sets the NodeSettings for the root node settings for rotation.

Returns:

NodeSettings for the root node.

setRotateChildNodeSettings

public void setRotateChildNodeSettings(NodeSettings n)

Sets the NodeSettings for the child node settings for rotation.

Returns:

NodeSettings for the child node.

setRotateDescendantNodeSettings

public void setRotateDescendantNodeSettings(NodeSettings n)

Sets the NodeSettings for the descendant node settings for rotation.

Returns:

NodeSettings for the descendant node.

setRotateOriginalNodeSettings

public void setRotateOriginalNodeSettings(NodeSettings n)

Sets the NodeSettings for the original node settings for rotation.

Returns:

NodeSettings for the original node.

setRotateAnimatorKeySettings

public void setRotateAnimatorKeySettings(KeySettings k)

Sets the KeySettings for the animator key settings for rotation.

Returns:

KeySettings for the animator key.

setRotateOriginalKeySettings

public void setRotateOriginalKeySettings(KeySettings k)

Sets the KeySettings for the original key settings for rotation.

Returns:

KeySettings for the original key.

setDeleteLeftLinePaintSettings

public void setDeleteLeftLinePaintSettings(PaintSettings p)

Sets the PaintSettings for the left line of Paint.

Returns:

PaintSettings for the left line.

setDeleteRightLinePaintSettings

public void setDeleteRightLinePaintSettings(PaintSettings p)

Sets the PaintSettings for the right line of Paint.

Returns:

PaintSettings for the right line.

setTraverseAnimatorNodeSettings

public void setTraverseAnimatorNodeSettings(NodeSettings n)

Sets the NodeSettings for the animator node settings for traversal.

Returns:

NodeSettings for the animator node.

setTraverseAnimatorKeySettings

public void setTraverseAnimatorKeySettings(KeySettings k)

Sets the KeySettings for the animator key settings for traversal.

Returns:

KeySettings for the animator key.

makeNodeDrawingType

protected BSTTree makeNodeDrawingType(java.lang.Comparable keyInsert,
                                      java.lang.Object valueInsert)

Makes and places the node into the tree. The node is returned for further manipulation. Specific methods for setting the original scheme.

Parameters:

keyInsert - comparable object which is added to the tree.

valueInsert - Object that accompanies keyInsert in the node.

Returns:

BSTTree that was recently inserted into the tree.

Throws:

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

insertDrawingType

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

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

Call to insertTreeType

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.

MakeTree

public void MakeTree(java.awt.Graphics2D g2)

Makes the entire tree from the null head down. The tree is made using the Graphics2D, and generally fills the entire Graphics2D parameter. This method allows the tree's drawing information to be defined without having to render the entire tree.

Specified by:

MakeTree in interface DrawingTreeHead

Parameters:

g2 - Graphics2D which the tree is made to fit unto.

DrawTree

public void DrawTree(java.awt.Graphics2D g2)

Draws the entire tree from the null head down. The tree is drawn onto the Graphics2D, and uses the information defined in the previous call to MakeTree.

Specified by:

DrawTree in interface DrawingTreeHead

Parameters:

g2 - Graphics2D which the tree is drawn onto.

findNode

public DrawingTree findNode(double x,
                            double y)

Finds the node represented by the x-y coordinates given. The (x,y) location represents a location within the Graphics2D to which the node appears. The recursive method progresses through the entire tree looking for the proper node.

Specified by:

findNode in interface DrawingTreeHead

Overrides:

findNode in class BSTTree

Parameters:

x - x-coordinate to find the node.

y - y-coordinate to find the node.

Returns:

DrawingTree representing the x-y coordinates passed or null if no node is found.

constructAnimatingBSTTreeHead

public void constructAnimatingBSTTreeHead()

Constructor for the ANIMATING_BST_TREE_TYPE. This constructs and sets all values to defaults for the ANIMATING_BST_TREE_TYPE.

isTreeRemove

public boolean isTreeRemove()

Gets whether the AnimatingBSTTreeHead is removing an Animation.

Returns:

boolean value as to whether the tree is removing an Animation.

getTreeAnimator

public Animation getTreeAnimator()

Gets the first Animation in the list of Animations for the Head and null if no Animations are present.

Specified by:

getTreeAnimator in interface AnimatingTreeHead

Returns:

first Animation in the Animation list.

isTreeAnimating

public boolean isTreeAnimating()

Returns true if the current AnimatingBSTTreeHead is animating (whether the animating list is empty.

Specified by:

isTreeAnimating in interface AnimatingTreeHead

Returns:

true if the current tree is animating and not empty.

isJumpStep

public boolean isJumpStep()

Gets the JumpStep of the current tree.

Specified by:

isJumpStep in interface AnimatingTreeHead

Returns:

true if the tree is jumpSteping.

isStepPause

public boolean isStepPause()

Gets the StepPause of the current tree.

Specified by:

isStepPause in interface AnimatingTreeHead

Returns:

true if the tree is pausing at the completion of each step.

getTreeAnimationStepSize

public int getTreeAnimationStepSize()

Gets the step size of the Animations of the tree.

Specified by:

getTreeAnimationStepSize in interface AnimatingTreeHead

Returns:

integer step size of the tree.

getTreeStatus

public java.lang.String getTreeStatus()

Gets the Tree's status, using the String status of Animation.

Specified by:

getTreeStatus in interface AnimatingTreeHead

Returns:

String status of the Tree, representing the Animation status.

setRemove

protected void setRemove(boolean b)

Sets whether the AnimatingBSTTreeHead is removing an Animation, because multiple Animations may occur simultaneously.

Parameters:

b - boolean value as to whether the tree is removing an Animation.

clearAnimators

public void clearAnimators()

Clears the Animations from the list of Animations for the Head.

addTreeAnimator

public void addTreeAnimator(Animation a)

Adds the Animation to the list of Animations for the Head. The method does not add the tree as a listener to the Animation. That must be accomplished by the client.

Specified by:

addTreeAnimator in interface AnimatingTreeHead

Parameters:

a - Animation added to the Animation list.

removeTreeAnimation

public void removeTreeAnimation()

Quickly removes all Animations within the Tree. The method sets the Status of all the Animations to Animation.FINISH so that al listeners of the Animations will receive the AnimationEvent.

Specified by:

removeTreeAnimation in interface AnimatingTreeHead

setJumpStep

public void setJumpStep(boolean b)

Sets the JumpStep of the current tree to the boolean value. The jumpStep determines whether the Animation skips through an entire step at each AnimateTree call.

Specified by:

setJumpStep in interface AnimatingTreeHead

Parameters:

b - sets the jumpStep to the value b.

setStepPause

public void setStepPause(boolean b)

Sets the StepPause of the current tree to the boolean value. The stepPause determines whether the Animation pauses after each step of the Animation completes.

Specified by:

setStepPause in interface AnimatingTreeHead

Parameters:

b - sets the stepPause to the value b.

setTreeAnimationsStepSize

public void setTreeAnimationsStepSize(int t)

Sets the step size of the Animations of the tree. The integer value is passed to every Animation's setStepTime method.

Specified by:

setTreeAnimationsStepSize in interface AnimatingTreeHead

Parameters:

t - integer step size setting.

setTreeStatus

public void setTreeStatus(java.lang.String s)

Sets the Status of the entire tree, using the status of Animation class.

Specified by:

setTreeStatus in interface AnimatingTreeHead

Parameters:

s - String status to set the Tree's Status.

insertAnimatingType

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

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

Call to insertDrawingType

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.

searchAnimatingType

protected Tree searchAnimatingType(java.lang.Comparable keySearch)
                            throws java.lang.ClassCastException

Searches for the Tree in the entire tree.

Call to searchTreeType

Parameters:

keySearch - the comparable key which is searched for within the tree.

Returns:

Tree the Tree found or null if keySearch was not present within the tree.

java.lang.ClassCastException

selectAnimatingType

protected Tree selectAnimatingType(BSTTree node,
                                   int keySelect)
                            throws java.lang.ClassCastException

Selects for the Tree in the entire tree.

Call to selectTreeType

Parameters:

keySelect - integer key selecting the count item.

Returns:

Tree the Tree found or null.

java.lang.ClassCastException

rotateUpAnimatingType

protected void rotateUpAnimatingType(BSTTree node)

Rotates the node up in the BSTTree.

Parameters:

node - BSTTree node that is rotated up.

rotateUpDoubleAnimatingType

protected void rotateUpDoubleAnimatingType(BSTTree node)

Double Rotates the node up in the BSTTree.

Parameters:

node - BSTTree node that is rotated up twice.

splayAnimatingType

protected void splayAnimatingType(BSTTree node)

Splays the node up in the BSTTree.

Parameters:

node - BSTTree node that is splayed.

rotateToTopAnimatingType

protected void rotateToTopAnimatingType(BSTTree node)

Rotates to top the node in the BSTTree.

Parameters:

node - BSTTree node that is splayed.

removeAnimatingType

protected void removeAnimatingType(BSTTree node)

Removes the node in the BSTTree. The method is overiden to allow for animation of the deletion. After the DeleteBSTAnimation is built, using the node, the super remove method is called.

Parameters:

node - BSTTree node that is deleted.

partitionAnimatingType

protected Tree partitionAnimatingType(BSTTree node,
                                      int keySelect)

Partitions from the given node the keySelect value. Replacing the reference in the Tree to the given node, to the keySelectth item.

Call to selectTreeType

Parameters:

keySelect - integer key selecting the count item.

Returns:

Tree that is the reference to the newly partitioned tree (Using selectTreeType).

balanceAnimatingType

public void balanceAnimatingType(BSTTree node)

Balances the tree from the given node, recursively rotating the median to the top. The method is overiden to allow for animation of the balancing, simply calling balanceTREE if no waiting action appears.

Parameters:

node - BSTTree that is balanced from.

traverseAnimatingType

public java.util.LinkedList traverseAnimatingType(int traverseType)

Traverses the tree in the given traversal type.

Parameters:

traverseType - int defining the given traversal type.

changeDisplayAnimatingType

public void changeDisplayAnimatingType()

Change Display of the BSTTree.

makeInsertAnimation

public Animation makeInsertAnimation(BSTTree insertNode)

Makes an insert Animation using the given node. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

insertNode - BSTTree node that the insert Animation is built for.

Returns:

Animation that represents the insertAnimation.

makeSearchAnimation

public Animation makeSearchAnimation(java.lang.Comparable keySearch)

Makes a search Animation using the given keySearch. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

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

makeSelectionAnimation

public Animation makeSelectionAnimation(BSTTree node,
                                        int keySelect)

Makes a select Animation using the given keySelect. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

keySelect - the int which is selected for within the tree.

makeRotationAnimation

public Animation makeRotationAnimation(BSTTree node)

Makes a rotation Animation using the given node. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

node - BSTTree node that the rotation Animation is built from.

Returns:

Animation that represents the rotationAnimation.

makeDeletionAnimation

public Animation makeDeletionAnimation(BSTTree node)

Makes a deletion Animation using the given node. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

node - BSTTree node that the deletion Animation is built from.

Returns:

Animation that represents the deleteAnimation.

makePartitionAnimation

public Animation makePartitionAnimation(BSTTree node,
                                        int keySelect)

Makes a partition Animation using the given node and given keySelect. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

node - BSTTree node that the deletion Animation is built from.

keySelect - finds the keySelectth node and rotates it to the top.

Returns:

Animation that represents the deleteAnimation.

makeBalanceAnimation

public Animation makeBalanceAnimation(BSTTree node)

Makes a balance Animation using the given node. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

node - BSTTree node that the balance Animation is built from.

Returns:

Animation that represents the balanceAnimation.

makeRotationDoubleAnimation

public Animation makeRotationDoubleAnimation(BSTTree node)

Makes a rotationDouble Animation using the given node. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

node - BSTTree node that the doubleRotation Animation is built from.

Returns:

Animation that represents the balanceAnimation.

makeTraverseAnimation

public Animation makeTraverseAnimation(java.util.LinkedList nodeList)

Makes a traverse Animation using the given LinkedList. The Animation adds no listeners, making the client have to add the listeners.

Parameters:

nodeList - the LinkedList containing the nodes that are the path of the traversal.

makeChangeDisplayAnimation

public Animation makeChangeDisplayAnimation()

Makes a changeDisplay Animation. The Animation adds no listeners, making the client have to add the listeners.

AnimateTree

public void AnimateTree(java.awt.Graphics2D g2)

Animates the entire BSTTree. The animation is drawn to the Graphics2D passed. This method is called repeatedly and for each Animation within the list, the drawAnimation method is called. Within this method, checks for removing a Animation are made, as are checks for Waiting Actions.

Specified by:

AnimateTree in interface AnimatingTreeHead

Parameters:

g2 - Graphics2D to which the Animations are drawn.

play

public void play()

Sets the status of the AnimatingBSTTree to play.

Specified by:

play in interface AnimatingTreeHead

stop

public void stop()

Sets the status of the AnimatingBSTTree to stop.

Specified by:

stop in interface AnimatingTreeHead

rewind

public void rewind()

Sets the status of the AnimatingBSTTree to rewind.

Specified by:

rewind in interface AnimatingTreeHead

pause

public void pause()

Sets the status of the AnimatingBSTTree to pause.

Specified by:

pause in interface AnimatingTreeHead

animationEventPerformed

public void animationEventPerformed(AnimationEvent e)

Implements AnimationListener which requires the following method. The only status of animation it listens for is Animation.FINISH, to remove the animation from the animators list and Animation.STEP, to possible pause the animation if stepPause is true.

Specified by:

animationEventPerformed in interface AnimationListener

Overrides:

animationEventPerformed in class BSTTree

Parameters:

e - AnimationEvent that represents the information of the Animation.