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. * @author Corey Sanders * @version 3.4 9/15/01 */ public class RedBlackTreeHead extends BSTTreeHead { /*************************************************************************/ /* BSTTreeHead constructor, methods, and variables, regardless of type. */ /*************************************************************************/ /** * String representing information regarding the type of tree. */ public static final String TREE_INFORMATION = "A red-black BST is a binary search tree in which each node is marked to be either red\n"+ "or black, with the additional restriction that no two red nodes appear consecutively on\n"+ "any path from an external link to the root (Sedgewick, 558).\n\n"+ "A balanced red-black BST is a red-black BST in which all paths from external links to\n"+ "the root have the same number of black nodes (Sedgewick, 558).\n\n"+ "Search Hits and Search Misses require about 1.002 lg N comparisons,\n"+ "on the average, in a tree built from N random keys.\n\n"+ "Search Hits and Search Misses can require 2 lg N + 2 comparisons in the worst case.\n"; /** * Constructs a new, null RedBlackTree, sorted according to the keys' natural * order. * *
Default type is BST_TREE_TYPE.
*/
public RedBlackTreeHead() {
this(0);
}
/**
* Constructs a new, empty RedBlackTree according to the type passed.
*
*@param treeType type of tree that should be implemented.
*/
public RedBlackTreeHead(int treeType) {
super(treeType);
}
/**
* Gets the tree type String for the BSTTree.
*
* @return tree type String for the tree.
*/
public String getTreeTypeString() {
return "Red-Black Tree";
}
/**
******************************************************************************
* BST_TREE_TYPE Static methods for determining best/average/worst case times *
******************************************************************************
*/
/**
* Returns the average Search hit time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the average search hit is needed.
*
* @return double the is the average search hit.
*/
public double averageSearchHit(int n) {
return (Math.log((double)n) * 1.002);
}
/**
* Returns the average Search miss time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the average search hit is needed.
*
* @return double the is the average search hit.
*/
public double averageSearchMiss(int n) {
return (Math.log((double)n) * 1.002);
}
/**
* Returns the worst case Search hit time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the worst case search hit is needed.
*
* @return double the is the worst case search hit.
*/
public double worstCaseSearchHit(int n) {
return (Math.log((double)n) * 2 + 2);
}
/**
* Returns the worst case Search miss time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the worst case search hit is needed.
*
* @return double the is the worst case search hit.
*/
public double worstCaseSearchMiss(int n) {
return (Math.log((double)n) * 2 + 2);
}
/**
* Returns the average Insertion time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the average search hit is needed.
*
* @return double the is the average search hit.
*/
public double averageInsertion(int n) {
return (Math.log((double)n) * 1.002);
}
/**
* Returns the worst case Insertion time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the worst case search hit is needed.
*
* @return double the is the worst case search hit.
*/
public double worstCaseInsertion(int n) {
return (Math.log((double)n) * 2 + 2);
}
/**
**********************************
* Waiting Action Method *
**********************************
*/
/**
* 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.
*
* @param action String action representing the next action for the BSTTreeHead.
* @param elements elemetns to which the action could be occuring, depending on the type of action.
*/
public void waitingAction(String action, Object element) {
if (action.equals(TreeHead.INSERT_NODE)) {
insertAnimatingType((RedBlackTree)element);
}
else {
super.waitingAction(action, element);
}
}
/*-----------------------------------------------------------------------*/
/*-------------------------------BST_TREE_TYPE---------------------------*/
/*-----------------------------------START-------------------------------*/
/*-----------------------------------------------------------------------*/
/*************************************************************************/
/* BST_TREE_TYPE : Methods and Variables specific to the BST_TREE_TYPE. */
/* These methods are universally used, regardless of the type of BST. */
/*************************************************************************/
/**
************************************************************************
* BST_TREE_TYPE Original Methods(Overiden in ANIMATING_BST_TREE_TYPE *
************************************************************************
*/
/**
* Sets the child of the TreeHead and sets its red link to false.
*
* @param child Tree, beginning the Tree nodes.
*/
public void setChild(Tree child) {
super.setChild(child);
}
/**
* Makes and places the node into the tree. The node is returned for further manipulation.
*
* @param keyInsert comparable object which is added to the tree.
* @param valueInsert Object that accompanies keyInsert in the node.
*
* @return BSTTree that was recently inserted into the tree.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected BSTTree makeNodeTreeType(Comparable keyInsert, Object valueInsert) {
// Get node from node factory.
RedBlackTree newTree = new RedBlackTree(getTreeType());
newTree.setHead(this);
// Set the null leaves.
newTree.setLeaf();
((BSTTree)newTree.getRightTree()).setHead(this);
((BSTTree)newTree.getLeftTree()).setHead(this);
// Set the values of the node.
newTree.setNode(keyInsert, valueInsert);
return newTree;
}
/*-----------------------------------------------------------------------*/
/*-------------------------------BST_TREE_TYPE---------------------------*/
/*------------------------------------END--------------------------------*/
/*-----------------------------------------------------------------------*/
/*/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
/*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////////*/
/*-----------------------------------------------------------------------*/
/*----------------------------DRAWING_BST_TREE_TYPE----------------------*/
/*-----------------------------------START-------------------------------*/
/*-----------------------------------------------------------------------*/
/*************************************************************************/
/* DRAWING_BST_TREE_TYPE : Methods and Variables specific to the */
/* DRAWING_BST_TREE_TYPE. These methods are specificaly used for drawing*/
/* to a Graphics2D. Therefore, do not use this type unless that is your */
/* purpose. */
/*************************************************************************/
/**
* The current redLinkPaint (Red Default...heh heh OBVIOUSLY)
*/
private PaintSettings redLinkPaint = PaintSettings.getScheme(PaintSettings.RED);
/**
* The current redLinkStroke (BasicStroke(2.0F) Default)
*/
private Stroke redLinkStroke = new BasicStroke(2.0F);
/**
*******************************************
* DRAWING_BST_TREE_TYPE Accesssor methods *
*******************************************
*/
/**
* Gets the red link paint for the current RedBlackTree.
*
* @return the paint for the red links of the drawing node.
*/
public PaintSettings getRedLinkPaint() {
return redLinkPaint;
}
/**
* Gets the red link stroke for the current RedBlackTree.
*
* @return the stroke for the red links of the drawing node.
*/
public Stroke getRedLinkStroke() {
return redLinkStroke;
}
/**
*******************************************
* DRAWING_BST_TREE_TYPE Mutator methods *
*******************************************
*/
/**
* Sets the red link paint for the current RedBlackTree.
*
* @param redLinkPaint the paint for the red links of the drawing node.
*/
public void setRedLinkPaint(PaintSettings redLinkPaint) {
this.redLinkPaint = redLinkPaint;
}
/**
* Gets the red link stroke for the current RedBlackTree.
*
* @return the stroke for the red links of the drawing node.
*/
public void setRedLinkStroke(Stroke redLinkStroke) {
this.redLinkStroke = 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.
*
* @param s NodeSettings for use in drawing the entire tree.
* @param k KeySettings for use in drawing the keys of the entire tree.
*/
public void setTreeSettings(NodeSettings s, KeySettings k, PaintSettings redLinkPaint, Stroke redLinkStroke) {
if (!isDrawingBSTTree())
return;
setDrawingNodeSettings(s);
setDrawingKeySettings(k);
setRedLinkPaint(redLinkPaint);
setRedLinkStroke(redLinkStroke);
if (!isTreeEmpty()) {
((RedBlackTree)getChild()).setTreeSettings(s, k, redLinkPaint, redLinkStroke);
}
}
/*-----------------------------------------------------------------------*/
/*---------------------------ANIMATING_BST_TREE_TYPE---------------------*/
/*-----------------------------------START-------------------------------*/
/*-----------------------------------------------------------------------*/
/*************************************************************************/
/* ANIMATING_BST_TREE_TYPE : Methods and Variables specific to the */
/* ANIMATING_BST_TREE_TYPE. These methods are specificaly used for */
/* animaitng to a Graphics2D. Therefore, do not use this type unless */
/* that is your purpose. */
/*************************************************************************/
/**
*********************************************
* ANIMATING_BST_TREE_TYPE Overiding methods *
*********************************************
*/
/**
* Insert the comaparable node to the tree using its natural ordering .
*
*
Call to insertDrawingType
*
* @param node BSTTree node to be inserted into the tree
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected void insertAnimatingType(BSTTree node) throws ClassCastException {
if ((!isAnimatingBSTTree()) || (isTreeEmpty())) {
((RedBlackTree)node).setRedLink(true);
insertDrawingType(node);
return;
}
// If Animation is occuring, add ROTATE_UP to the waitingList.
if (isTreeAnimating()) {
getWaitingList().add(AnimatingTreeHead.INSERT_NODE, node);
return;
}
Animation insertAnimator = makeInsertAnimation(node);
// Add animation and recieve listening events.
this.addTreeAnimator(insertAnimator);
insertAnimator.addAnimationListener(this);
// Add animation to the inserting node.
node.addAnimator(insertAnimator);
insertAnimator.addAnimationListener(node);
// Super call
insertDrawingType(node);
// Add the final location, after the tree is built.
((InsertRedBlackAnimation)insertAnimator).add(node);
}
/**
****************************************************
* ANIMATING_BST_TREE_TYPE Constructing Animations *
****************************************************
*/
/**
* Makes an insert Animation using the given node. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param insertNode BSTTree node that the insert Animation is built for.
* @return Animation that represents the insertAnimation.
*/
public Animation makeInsertAnimation(BSTTree insertNode) {
if (!isAnimatingBSTTree()) {
return null;
}
// Head node (backup test).
if (insertNode == this)
return null;
// Construct animation for Insert.
InsertRedBlackAnimation newAnimator = new InsertRedBlackAnimation(insertNode,getInsertNodeLeftSettings(),getInsertNodeRightSettings(),getInsertAnimatorNodeSettings(), getInsertAnimatorKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
// Starting Animation.
//AffineTransform a = AffineTransform.getScaleInstance(getScreenBounds().getWidth() * .35, getScreenBounds().getHeight() * .35);
// Add initial animation.
//newAnimator.add(a);
// Recursive call to insert the tree, starting at the head level.
((RedBlackTree)getChild()).makeInsertAnimation(insertNode, newAnimator);
return newAnimator;
}
/**
* Makes a delete Animation using the given node. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param node BSTTree node that the deletion Animation is built from.
* @return Animation that represents the deleteAnimation.
*/
public Animation makeDeletionAnimation(BSTTree node) {
if (!isAnimatingBSTTree()) {
return null;
}
// If this is the node to be deleted (precautionary check).
if (node == this)
return null;
// New deletion animation.
DeleteRedBlackAnimation newAnimator = new DeleteRedBlackAnimation(node, getDeleteLeftLinePaintSettings(), getDeleteRightLinePaintSettings(), getTreeStatus(), getTreeAnimationStepSize());
return newAnimator;
}
}