Class RedBlackTree

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

All Implemented Interfaces:

AnimatingTree, AnimationListener, DrawingTree, java.util.EventListener, Tree

public class RedBlackTree

extends BSTTree

The class provides the base structure of a RedBlackTree, a node of a Red-Black tree. It uses the elements natural ordering. It uses everything defined within the AbstractTree

The BSTTree cannot be the head of the tree, it is only the nodes. It defines recursive methods which aren't defined in the head node and it does not define the methods for the head node.

The Red-Black tree is a natural extension of a Binary Search Tree, because it is in fact a specialized 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.

Field Summary

Fields inherited from class BSTTree

ANIMATING_BST_TREE_TYPE, BST_TREE_TYPE, DRAWING_BST_TREE_TYPE

Constructor Summary

RedBlackTree()
Constructs a new, empty RedBlackTree.

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

Method Summary

protected void	copyBSTTree(BSTTree copy) Copies the fields of this RedBlackTree into the RedBlackTree copy.
protected void	drawLeftLink(java.awt.Graphics2D g2, double sectionHeight, java.awt.geom.AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) Draws just the left link according to the NodeSettings currently set.
protected void	drawRightLink(java.awt.Graphics2D g2, double sectionHeight, java.awt.geom.AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) Draws just the right link according to the NodeSettings currently set.
protected RedBlackTree	findReplacingNode() Finds the replacing node for a deletion.
protected void	fixUpRedBlackLinks() Fixes down to the bottom of the node passed, the red-black links.
PaintSettings	getRedLinkPaint() Gets the red link paint for the current RedBlackTree.
java.awt.Stroke	getRedLinkStroke() Gets the red link stroke for the current RedBlackTree.
protected void	insert(BSTTree newTree, int currentLevel) Inserts the given object into the tree, using recursive calls and is called from the Head node.
protected void	insertRedBlackTree(RedBlackTree newTree) Inserts the given object into the tree, using recursive calls and is called from the Head node.
boolean	isRedLink() Gets the red link for the node.
protected void	makeInsertAnimation(BSTTree insertNode, InsertRedBlackAnimation newAnimator) Insert the BSTTree down from the current node.
protected void	remove() Removes the BSTTree from the tree.
protected void	setLeaf() Sets the values of a new Node left and right tress, to refer to null trees.
void	setRedLink(boolean redLink) Sets the red link for the node.
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.
protected void	setTreeSettings(NodeSettings s, KeySettings k, PaintSettings redLinkPaint, java.awt.Stroke redLinkStroke) Sets the settings of the entire tree.

Methods inherited from class BSTTree

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

Methods inherited from class java.lang.Object

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

Constructor Detail

RedBlackTree

public RedBlackTree()

Constructs a new, empty RedBlackTree.

Default type is BST_TREE_TYPE.

RedBlackTree

public RedBlackTree(int treeType)

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

Parameters:

treeType - type of tree that should be implemented.

Method Detail

copyBSTTree

protected void copyBSTTree(BSTTree copy)

Copies the fields of this RedBlackTree into the RedBlackTree copy. The only additional information is the red bit.

Overrides:

copyBSTTree in class BSTTree

Parameters:

copy - the BSTTree that takes the fields of the BSTTree.

isRedLink

public boolean isRedLink()

Gets the red link for the node.

Returns:

true if the link to the current node is red.

setRedLink

public void setRedLink(boolean redLink)

Sets the red link for the node.

Parameters:

redLink - true if the link to the current node is red.

setLeaf

protected void setLeaf()

Sets the values of a new Node left and right tress, to refer to null trees. Both the left and right trees are instantiated and their values are set to the default null values.

Overrides:

setLeaf in class BSTTree

insert

protected void insert(BSTTree newTree,
                      int currentLevel)
               throws java.lang.ClassCastException

Inserts the given object into the tree, using recursive calls and is called from the Head node. This method is recursive until it finds a subtree that is null and sets the node.

Before Recursive calls (on the way down) 4-nodes are split up. Then the node is recursively inserted and on returning calls (on the way back up), Red-Black link integrity is maintained.

Overrides:

insert in class BSTTree

Parameters:

newTree - the tree to be inserted, with key and value already set.

currentLevel - keeps track of the recursive call, and sets the new level if it changes.

Throws:

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

insertRedBlackTree

protected void insertRedBlackTree(RedBlackTree newTree)
                           throws java.lang.ClassCastException

Inserts the given object into the tree, using recursive calls and is called from the Head node. This method is recursive until it finds a subtree that is null and sets the node.

Before Recursive calls (on the way down) 4-nodes are split up. Then the node is recursively inserted and on returning calls (on the way back up), Red-Black link integrity is maintained.

Parameters:

newTree - the tree to be inserted, with key and value already set.

Throws:

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

findReplacingNode

protected RedBlackTree findReplacingNode()

Finds the replacing node for a deletion. It simply searches down to the bottom of the tree Looking for the smallest element from the initial call.

Returns:

RedBlackTree that should be the smallest node.

remove

protected void remove()

Removes the BSTTree from the tree. The call bypasses the BSTTree by partitioning the right subTree and replacing itself with the smallest of the right tree.

Overrides:

remove in class BSTTree

fixUpRedBlackLinks

protected void fixUpRedBlackLinks()

Fixes down to the bottom of the node passed, the red-black links. The pass down separates any 4-nodes and the way back up rotates if necessary.

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

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

Sets the settings of the entire tree. This represents a recursive call through the tree, setting the tree's NodeSettings and then calling both children.

Parameters:

s - NodeSettings being set for the entire tree.

drawRightLink

protected void drawRightLink(java.awt.Graphics2D g2,
                             double sectionHeight,
                             java.awt.geom.AffineTransform a,
                             double drawingLevel,
                             double powerLevel,
                             boolean bottomLinks)

Draws just the right link according to the NodeSettings currently set.

Overrides:

drawRightLink in class BSTTree

Parameters:

g2 - graphics to which the node and links are drawn.

sectionHeight - the height of the tree' section, to draw the correct lengths for the links.

a - transfrom to draw the node and links.

drawingLevel - the level in the tree to which the node is currently being drawn.

powerLevel - the power to which the links extend, depending on how many links are present.

bottomLinks - the boolean to declare whether the bottom links should be drawn.

drawLeftLink

protected void drawLeftLink(java.awt.Graphics2D g2,
                            double sectionHeight,
                            java.awt.geom.AffineTransform a,
                            double drawingLevel,
                            double powerLevel,
                            boolean bottomLinks)

Draws just the left link according to the NodeSettings currently set.

Overrides:

drawLeftLink in class BSTTree

Parameters:

g2 - graphics to which the node and links are drawn.

sectionHeight - the height of the tree' section, to draw the correct lengths for the links.

a - transfrom to draw the node and links.

drawingLevel - the level in the tree to which the node is currently being drawn.

powerLevel - the power to which the links extend, depending on how many links are present.

bottomLinks - the boolean to declare whether the bottom links should be drawn.

makeInsertAnimation

protected void makeInsertAnimation(BSTTree insertNode,
                                   InsertRedBlackAnimation newAnimator)
                            throws java.lang.ClassCastException

Insert the BSTTree down from the current node. This is a recursive call, defined in BSTTree. It is overiden in this class to build the animation of the insertion. The reason this animation is overiden and not simply added in the AnimatingBSTTreeHead, is to allow multiple insertions to occur at once. Therefore, insertion never goes through WaitingActionList.

Parameters:

newAnimator - the InsertBSTAnimation to which the nodes are being added.

Throws:

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