Class BalancedBSTTreeHead

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

All Implemented Interfaces:

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

public class BalancedBSTTreeHead

extends BSTTreeHead

This class provides the head structure for a BalancedBSTTree. Therefore, it overides all important methods necessary for maintaining a Balanced BST.

The BalanceBSTTree defines methods necessary for a BSTTreeHead, a DrawingBSTTreeHead, and an AnimatingBSTTreeHead. The type is set when the node is constructed but can be changed in the middle using methods found in BSTTree. If a method is called for a type that is higher is level than the type of the tree, the method will be ignored.

Nested Class Summary

Nested classes inherited from class BSTTreeHead

BSTTreeHead.NodeAndKey

Field Summary

static int	DEFAULT_BALANCE_DIFFERENCE Default balance probability.
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

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

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

Method Summary

int	getBalanceDifference() Gets the Balance Frequency for the Balanced BSTTree.
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 .
protected BSTTree	makeNode(java.lang.Comparable keyInsert, java.lang.Object valueInsert) Makes and places the node into the tree.
void	remove(Tree node) Removes the given node from the tree.
void	setBalanceDifference(int balanceDifference) Gets the Balance Frequency for the Balanced BSTTree.
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, averageInsertion, 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, makeNodeDrawingType, makeNodeTreeType, makePartitionAnimation, makeRotationAnimation, makeRotationDoubleAnimation, makeSearchAnimation, makeSelectionAnimation, makeTraverseAnimation, MakeTree, messageAction, messageAction, partition, partitionAnimatingType, partitionTreeType, pause, play, remove, removeAnimatingType, removeTreeAnimation, removeTreeMessageListener, removeTreeType, resetTreeLevel, rewind, rotateToTop, rotateToTopAnimatingType, rotateToTopTreeType, rotateUp, rotateUp, rotateUpAnimatingType, rotateUpDouble, rotateUpDouble, rotateUpDoubleAnimatingType, rotateUpDoubleTreeType, rotateUpTreeType, search, 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

DEFAULT_BALANCE_DIFFERENCE

public static final int DEFAULT_BALANCE_DIFFERENCE

Default balance probability. (1)

See Also:

Constant Field Values

Constructor Detail

BalancedBSTTreeHead

public BalancedBSTTreeHead()

Constructs a new, null BalancedBSTTreeHead, sorted according to the keys' natural order and insertion occurs automatically to the root.

Default type is BST_TREE_TYPE.

BalancedBSTTreeHead

public BalancedBSTTreeHead(int treeType)

Constructs a new, empty BalancedBSTTreeHead 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.

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 - Object to which the action could be occuring, depending on the type of action.

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.

Makes the node a BalancedBSTTree.

Overrides:

makeNode in class BSTTreeHead

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.

getBalanceDifference

public int getBalanceDifference()

Gets the Balance Frequency for the Balanced BSTTree. The frequency is a double between 0.0 and 1.0 and is the probability that the tree will balance after every insert/delete.

Returns:

double probability of balancing the tree.

setBalanceDifference

public void setBalanceDifference(int balanceDifference)

Gets the Balance Frequency for the Balanced BSTTree. The frequency is a double between 0.0 and 1.0 and is the probability that the tree will balance after every insert/delete.

Returns:

double probability of balancing the tree.

insert

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

Adds the node to the tree using its natural ordering .

Randomly balances the tree after each insertion.

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.

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.

Randomly balances the tree after each deletion.

Specified by:

remove in interface TreeHead

Overrides:

remove in class BSTTreeHead

Parameters:

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

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.