Class RedBlackTreeHead

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

All Implemented Interfaces:

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

public class RedBlackTreeHead

extends BSTTreeHead

This class provides the head structure for a RedBlackTree. It implements the interface for TreeHead and implements all important methods necessary for maintaining a Red-Black Binary Search Tree.

Note that this implementation is not synchronized. If multiple threads access this tree concurrently, and at least one of the threads modifies the tree structurally, it must be synchronized externally.

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

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

RedBlackTreeHead(int treeType)
Constructs a new, empty RedBlackTree 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.
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.
PaintSettings	getRedLinkPaint() Gets the red link paint for the current RedBlackTree.
java.awt.Stroke	getRedLinkStroke() Gets the red link stroke for the current RedBlackTree.
java.lang.String	getTreeTypeString() Gets the tree type String for the BSTTree.
protected void	insertAnimatingType(BSTTree node) Insert the comaparable node to the tree using its natural ordering .
Animation	makeDeletionAnimation(BSTTree node) Makes a delete Animation using the given node.
Animation	makeInsertAnimation(BSTTree insertNode) Makes an insert Animation using the given node.
protected BSTTree	makeNodeTreeType(java.lang.Comparable keyInsert, java.lang.Object valueInsert) Makes and places the node into the tree.
void	setChild(Tree child) Sets the child of the TreeHead and sets its red link to false.
void	setRedLinkPaint(PaintSettings redLinkPaint) Sets the red link paint for the current RedBlackTree.
void	setRedLinkStroke(java.awt.Stroke redLinkStroke) Gets the red link stroke for the current RedBlackTree.
void	setTreeSettings(NodeSettings s, KeySettings k, PaintSettings redLinkPaint, java.awt.Stroke redLinkStroke) Sets the NodeSettings for the entire tree from the head down.
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 BSTTreeHead

addTreeAnimator, addTreeMessageListener, AnimateTree, animationEventPerformed, 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, insert, insertDrawingType, insertTreeType, isJumpStep, isStepPause, isTreeAnimating, isTreeEmpty, isTreeRemove, makeBalanceAnimation, makeChangeDisplayAnimation, makeNode, makeNodeDrawingType, 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, search, searchAnimatingType, searchTreeType, select, selectAnimatingType, selectTreeType, setBackgroundColor, 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

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

RedBlackTreeHead

public RedBlackTreeHead()

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

Default type is BST_TREE_TYPE.

RedBlackTreeHead

public RedBlackTreeHead(int treeType)

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

averageSearchHit

public double averageSearchHit(int n)

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

Overrides:

averageSearchHit 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.

averageSearchMiss

public double averageSearchMiss(int n)

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

Overrides:

averageSearchMiss 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.

worstCaseSearchHit

public double worstCaseSearchHit(int n)

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

Overrides:

worstCaseSearchHit in class BSTTreeHead

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.

Overrides:

worstCaseSearchMiss in class BSTTreeHead

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.

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.

worstCaseInsertion

public double worstCaseInsertion(int n)

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

Overrides:

worstCaseInsertion in class BSTTreeHead

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

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.

setChild

public void setChild(Tree child)

Sets the child of the TreeHead and sets its red link to false.

Specified by:

setChild in interface TreeHead

Overrides:

setChild in class BSTTreeHead

Parameters:

child - Tree, beginning the Tree nodes.

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.

Overrides:

makeNodeTreeType 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.

getRedLinkPaint

public PaintSettings getRedLinkPaint()

Gets the red link paint for the current RedBlackTree.

Returns:

the paint for the red links of the drawing node.

getRedLinkStroke

public java.awt.Stroke getRedLinkStroke()

Gets the red link stroke for the current RedBlackTree.

Returns:

the stroke for the red links of the drawing node.

setRedLinkPaint

public void setRedLinkPaint(PaintSettings redLinkPaint)

Sets the red link paint for the current RedBlackTree.

Parameters:

redLinkPaint - the paint for the red links of the drawing node.

setRedLinkStroke

public void setRedLinkStroke(java.awt.Stroke redLinkStroke)

Gets the red link stroke for the current RedBlackTree.

Returns:

the stroke for the red links of the drawing node.

setTreeSettings

public void setTreeSettings(NodeSettings s,
                            KeySettings k,
                            PaintSettings redLinkPaint,
                            java.awt.Stroke redLinkStroke)

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.

Parameters:

s - NodeSettings for use in drawing the entire tree.

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

insertAnimatingType

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

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

Call to insertDrawingType

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.

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.

Overrides:

makeInsertAnimation in class BSTTreeHead

Parameters:

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

Returns:

Animation that represents the insertAnimation.

makeDeletionAnimation

public Animation makeDeletionAnimation(BSTTree node)

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

Overrides:

makeDeletionAnimation in class BSTTreeHead

Parameters:

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

Returns:

Animation that represents the deleteAnimation.