com.hedgehog.math.graph_tree
Class BalancedBinaryTreeNode

java.lang.Object
  com.hedgehog.HObject
      com.hedgehog.math.graph_tree.BalancedBinaryTreeNode

All Implemented Interfaces:

java.lang.Comparable, java.util.Comparator

public class BalancedBinaryTreeNode
extends HObject

Title: BalancedBinaryTreeNode - models a node in a balanced binary tree.

Description: Balanced binary tree node. Note that this class makes use of Comparator.compare() so that the node object type used must implement Comparator.

Copyright: Copyright (c) Hedgehog Software 2007-2009.

Company: Hedgehog Software.

Since:

1.0

Version:

1.1

Field Summary

protected PlainColour	colour Node colour.
protected java.util.Comparator	comparator Comparator object.
protected BalancedBinaryTreeNode	left Node left node.
protected HObject	object Node object.
protected BalancedBinaryTreeNode	parent Node parent node.
protected BalancedBinaryTreeNode	right Node right node.

Fields inherited from class com.hedgehog.HObject

mID, mName

Constructor Summary

BalancedBinaryTreeNode()
Default constructor.

BalancedBinaryTreeNode(HObject object)
Constructor.

BalancedBinaryTreeNode(HObject object, PlainColour colour, BalancedBinaryTreeNode left, BalancedBinaryTreeNode right, BalancedBinaryTreeNode parent)
Constructor.

Method Summary

BalancedBinaryTreeNode	associatedNode(HObject obj) Searches a binary node for the node associated with an object and returns the associated node if the node is in the tree, else returns null.
int	degree() Returns the degree of a node.
PlainColour	getColour() Returns this node's colour.
java.util.Comparator	getComparator() Returns the Comparator; ie object.
BalancedBinaryTreeNode	getLeftNode() Returns this node's left node.
HObject	getNodeObject() Returns the node object.
BalancedBinaryTreeNode	getParentNode() Returns this node's parent node.
BalancedBinaryTreeNode	getRightNode() Returns this node's right node.
boolean	isLeaf() Returns logical-true if a node is a leaf (i.e.
boolean	isParent() Returns logical-true if a node is a parent (i.e.
BalancedBinaryTreeNode	leftRotate(HBoolean rootNode) Left-rotation of a node.
BalancedBinaryTreeNode	rightRotate(HBoolean rootNode) Right-rotation of a node.
boolean	search(HObject obj) Searches a binary node for an object and returns logical-true if the object is in the node, else logical-false.
boolean	setColour(PlainColour newColour) Sets this node's colour.
boolean	setLeftNode(BalancedBinaryTreeNode newLeftNode) Sets this node's left node.
boolean	setNodeObject(HObject newNodeObject) Sets the node object to the specified object.
boolean	setParentNode(BalancedBinaryTreeNode newParentNode) Sets this node's parent node.
boolean	setRightNode(BalancedBinaryTreeNode newRightNode) Sets this node's right node.
java.lang.String	toString() Returns a String representation of a BalancedBinaryTreeNode object.

Methods inherited from class com.hedgehog.HObject

clone, compare, compareTo, copy, equals, getID, getName, hashCode, hasID, hasName, setID, setName

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

comparator

protected java.util.Comparator comparator

Comparator object.

object

protected HObject object

Node object.

left

protected BalancedBinaryTreeNode left

Node left node.

right

protected BalancedBinaryTreeNode right

Node right node.

parent

protected BalancedBinaryTreeNode parent

Node parent node.

colour

protected PlainColour colour

Node colour.

Constructor Detail

BalancedBinaryTreeNode

public BalancedBinaryTreeNode()

Default constructor. Sets the object, left, right, parent and comparator to null. Sets the colour to PlainColour.BLACK.

BalancedBinaryTreeNode

public BalancedBinaryTreeNode(HObject object)
                       throws java.lang.IllegalArgumentException

Constructor. Sets the object to the specified object and left, right, parent to null. Sets the colour to PlainColour.BLACK. Sets the comparator to the specified object provided that it implements Comparator.

Parameters:

object - Node object. Must implement Comparator.

Throws:

java.lang.IllegalArgumentException - Thrown if object does not implement Comparator.

BalancedBinaryTreeNode

public BalancedBinaryTreeNode(HObject object,
                              PlainColour colour,
                              BalancedBinaryTreeNode left,
                              BalancedBinaryTreeNode right,
                              BalancedBinaryTreeNode parent)
                       throws java.lang.IllegalArgumentException

Constructor. Sets the object, colour, left node, right node, parent node and comparator to the specified objects.

Parameters:

object - Node object.

colour - Node colour.

left - Left node.

right - Right node.

parent - Parent node.

Throws:

java.lang.IllegalArgumentException - Thrown if object does not implement Comparator.

Method Detail

associatedNode

public BalancedBinaryTreeNode associatedNode(HObject obj)

Searches a binary node for the node associated with an object and returns the associated node if the node is in the tree, else returns null. Note that only the tree below the invoking object is checked, so that if you wish to search the entire tree then use the root node.

Parameters:

obj - Object node to search for.

Returns:

Node associated with specified object.

getColour

public PlainColour getColour()

Returns this node's colour.

Returns:

This node's colour.

setColour

public boolean setColour(PlainColour newColour)

Sets this node's colour.

Parameters:

newColour - New colour.

Returns:

Logical-true if the colour is set, else logical-false.

getComparator

public java.util.Comparator getComparator()

Returns the Comparator; ie object. Note that no setComparator() method is defined because the Comparator is set via setNodeObject().

Returns:

The object Comparator.

degree

public int degree()

Returns the degree of a node.

Returns:

The degree of a node, either 0, 1 or 2.

isLeaf

public boolean isLeaf()

Returns logical-true if a node is a leaf (i.e. no children), else logical-false. Note: a tree with just the root node qualifies as a tree with one leaf.

Returns:

Logical-true if a node is a leaf (i.e. no children), else logical-false.

isParent

public boolean isParent()

Returns logical-true if a node is a parent (i.e. at least one child), else logical-false.

Returns:

Logical-true if a node is a parent (i.e. at least one child), else logical-false.

getLeftNode

public BalancedBinaryTreeNode getLeftNode()

Returns this node's left node.

Returns:

This node's left node.

setLeftNode

public boolean setLeftNode(BalancedBinaryTreeNode newLeftNode)

Sets this node's left node.

Parameters:

newLeftNode - New left node.

Returns:

Logical-true if this node's left node is set, else logical-false.

leftRotate

public BalancedBinaryTreeNode leftRotate(HBoolean rootNode)

Left-rotation of a node. Returns the new parent node (y) and logical-true if the operated-on node is a root node, else logical-false.

Parameters:

rootNode - Returned, via reference, and set to logical-true if root node, else logical-false.

Returns:

The new parent node (y).

getNodeObject

public HObject getNodeObject()

Returns the node object.

Returns:

The node object.

setNodeObject

public boolean setNodeObject(HObject newNodeObject)

Sets the node object to the specified object. Note that object must implement Comparator, so that a logical-false value will be returned and the object NOT set if object does not implement Comparator.

Parameters:

newNodeObject - New node object. Must implement Comparator.

Returns:

Logical-true if object set, else logical-false.

getParentNode

public BalancedBinaryTreeNode getParentNode()

Returns this node's parent node.

Returns:

This node's parent node.

setParentNode

public boolean setParentNode(BalancedBinaryTreeNode newParentNode)

Sets this node's parent node.

Parameters:

newParentNode - New parent node.

Returns:

Logical-true if this node's parent node is set, else logical-false.

getRightNode

public BalancedBinaryTreeNode getRightNode()

Returns this node's right node.

Returns:

This node's right node.

setRightNode

public boolean setRightNode(BalancedBinaryTreeNode newRightNode)

Sets this node's right node.

Parameters:

newRightNode - New right node.

Returns:

Logical-true if this node's right node is set, else logical-false.

rightRotate

public BalancedBinaryTreeNode rightRotate(HBoolean rootNode)

Right-rotation of a node. Returns the new parent node (y) and logical-true if the operated-on node is a root node, else logical-false.

Parameters:

rootNode - Returned, via reference, and set to logical-true if root node, else logical-false.

Returns:

The new parent node (y).

search

public boolean search(HObject obj)

Searches a binary node for an object and returns logical-true if the object is in the node, else logical-false.

Parameters:

obj - Object to search for.

Returns:

Logical-true if object found, else logical-false.

toString

public java.lang.String toString()

Returns a String representation of a BalancedBinaryTreeNode object.

Overrides:

toString in class java.lang.Object

Returns:

A String representation of a BalancedBinaryTreeNode object.