com.sas.collection
Class AVLNode

java.lang.Object
  |
  +--com.sas.collection.AVLNode

All Implemented Interfaces:

Enumerable, PublicClonable,

public class AVLNode

extends java.lang.Object

implements java.io.Serializable, PublicClonable, Enumerable

A node for AVL tree. This class represents the nodes within an AVL tree, named after Adelson-Velskii and Landis. The nodes are threaded which means nodes which do not have a left or right child have links to the previous or next subtree; this allows for easy forward or backward enumeration of the items in the tree. Each node has either a left child or a reference to the subtree containing the previous node. Each node also has either a right child or a reference to the a subtree containing the next node.

Since:

1.2

See Also:

AVLTree, Serialized Form

Inner Class Summary

Field Summary

static String

RB_KEY

Constructor Summary

AVLNode()
Construct a new AVLNode.

AVLNode(Object object)
Construct a new AVLNode which contains an object

Method Summary

static AVLNode	add(AVLNode node, AVLNode root, Comparator comparator, boolean allowDuplicates) Add a AVL node into a tree rooted at root, using the comparator.
static AVLNode	add(Object object, AVLNode root, Comparator comparator, boolean allowDuplicates) Add the object into a tree rooted at root, using the comparator.
protected int	balance() Return a node's balance
Object	clone() Clone this AVL tree node.
static AVLNode	find(AVLNode root, Object object, Comparator comparator) Search for and return a value in the AVL tree
Enumeration	getItems() Return an enumeration of the items in the tree rooted at this node.
AVLNode.Cursor	getItems(boolean reversedOrder) Get an enumeration of the tree contents.
Enumeration	getItems(int start, int end) Get an enumeration of the tree contents, or a subrange of items.
AVLNode	getLeftChild() Get the left child.
AVLNode	getLeftThread() Get the left thread
AVLNode	getNextNode() Get the next node.
Object	getObject() Return the object stored at this node.
AVLNode	getPreviousNode() Get the previous node.
AVLNode	getRightChild() Get the right child.
AVLNode	getRightThread() Get the right thread
boolean	hasLeftChild() Return true if the node has a left child
protected boolean	hasLeftThread() Return true if the node is left threaded, that is the leftLink() is a link to a previous node in the enumeration.
boolean	hasRightChild() Return true if the node has a right child.
protected boolean	hasRightThread() Return true if the node is right threaded, that is the rightLink() is a link to a next node in the enumeration.
protected boolean	isEvenlyBalanced() Return true if the node has even balance.
protected boolean	isNegativelyBalanced() Return true if the node has negative balance.
protected boolean	isPositivelyBalanced() Return true if the node has positive balance.
AVLNode	leftLink() Get the left link.
AVLNode	leftMostDescendent() Return the left-most descendent
AVLNode	rightLink() Get the right link.
AVLNode	rightMostDescendent() Return the right-most descendent
static AVLNode	search(Object object, AVLNode node, Comparator comparator) Search for an object in the tree rooted by node, using the comparator.
protected void	setBalance(int balance) Set a node's balance to negative, even, or positive In many published algorithms, this is denoted by node.balance = a Positive balance means the depth of the right subtree is greater than the depth of the left subtree.
protected void	setEvenBalance() Mark the node as having even balance.
protected void	setLeftChild(AVLNode child) Assign the left child node.
protected void	setLeftChild(AVLNode child, AVLNode thread) Assign the left child node or the left thread if child is null
protected void	setLeftThread(AVLNode prev) Assign the previous node.
protected void	setNegativeBalance() Mark the node as having negative balance.
void	setObject(Object object) Set the object stored at this node.
protected void	setPositiveBalance() Mark the node as having positive balance.
protected void	setRightChild(AVLNode child) Assign the right child node.
protected void	setRightChild(AVLNode child, AVLNode thread) Assign the right child node, or the right thread if child is null.
protected void	setRightThread(AVLNode next) Assign the next node.
String	toString() Return the string representation of this node.
String	toString(boolean printValue, boolean showThreads) Return the string representation of this node.

Methods inherited from class java.lang.Object

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

Field Detail

RB_KEY

public static final String RB_KEY

Constructor Detail

AVLNode

public AVLNode()

Construct a new AVLNode.

AVLNode

public AVLNode(Object object)

Construct a new AVLNode which contains an object

Method Detail

setObject

public void setObject(Object object)

Set the object stored at this node. This object is used for comparing new items being inserted or in item searches.

Parameters:

object - the object stored at this node.

getObject

public Object getObject()

Return the object stored at this node.

Returns:

the object stored at this node.

setBalance

protected void setBalance(int balance)

Set a node's balance to negative, even, or positive In many published algorithms, this is denoted by node.balance = a Positive balance means the depth of the right subtree is greater than the depth of the left subtree. Negative balance means the depth of the left subtree is greater than the depth of the rightsubtree.

Parameters:

balance - -1 for negative balance, 0 for even balance, 1 for positive balance

balance

protected int balance()

Return a node's balance

Returns:

the current node balance; -1 means negative, 0 is balanced, 1 is positive balance. Positive balance means the depth of the right subtree is greater than the depth of the left subtree. Negative balance means the depth of the left subtree is greater than the depth of the rightsubtree.

setNegativeBalance

protected void setNegativeBalance()

Mark the node as having negative balance. In many published algorithms, this is denoted by node.balance == -1 Calling setNegativeBalance is equivalent to setting node.balance = -1

See Also:

setBalance(int)

setPositiveBalance

protected void setPositiveBalance()

Mark the node as having positive balance. In many published algorithms, this is denoted by node.balance == +1 but for space reasons, the balance is embedded within the state variable. Calling setPositiveBalance is equivalent to setting node.balance = +1

See Also:

setBalance(int)

setEvenBalance

protected void setEvenBalance()

Mark the node as having even balance. In many published algorithms, this is denoted by node.balance == 0 but for space reasons, the balance is embedded within the state variable. Calling setEvenBalance is equivalent to setting node.balance = 0

See Also:

setBalance(int)

isNegativelyBalanced

protected boolean isNegativelyBalanced()

Return true if the node has negative balance.

isPositivelyBalanced

protected boolean isPositivelyBalanced()

Return true if the node has positive balance.

isEvenlyBalanced

protected boolean isEvenlyBalanced()

Return true if the node has even balance.

leftLink

public AVLNode leftLink()

Get the left link. If the node is left threaded, this is the previous node in the tree. If the node is not left threaded, this is the left child.

Returns:

the left link

setLeftChild

protected void setLeftChild(AVLNode child,
                            AVLNode thread)

Assign the left child node or the left thread if child is null

Parameters:

child - the node to assign as the left child node.

thread - the node to assign as the left thread, iff child == null

setLeftChild

protected void setLeftChild(AVLNode child)

Assign the left child node.

Parameters:

prev - the node to assign as the left child node.

getLeftChild

public AVLNode getLeftChild()

Get the left child.

Returns:

the left child, or null if there is no left child.

getLeftThread

public AVLNode getLeftThread()

Get the left thread

Returns:

the left thread, or null if there is no left thread

setLeftThread

protected void setLeftThread(AVLNode prev)

Assign the previous node. This node will no longer have a left child. This node is marked as left threaded.

Parameters:

prev - the node to assign as the previous node.

hasLeftThread

protected boolean hasLeftThread()

Return true if the node is left threaded, that is the leftLink() is a link to a previous node in the enumeration. Note that this may be true when the left thread is null. This method is really the equivalent to !(hasLeftChild())

hasLeftChild

public final boolean hasLeftChild()

Return true if the node has a left child

Returns:

true if the node has a left child

rightLink

public AVLNode rightLink()

Get the right link. If the node is right threaded, this is the next node in the tree. If the node is not left threaded, this is the left child.

Returns:

the right link

getRightChild

public AVLNode getRightChild()

Get the right child.

Returns:

the right child, or null if there is no right child.

getRightThread

public AVLNode getRightThread()

Get the right thread

Returns:

the right thread, or null if there is no right thread

setRightThread

protected void setRightThread(AVLNode next)

Assign the next node. This node will no longer have a right child. This node is marked as right threaded.

Parameters:

next - the node to assign as the next node.

setRightChild

protected void setRightChild(AVLNode child,
                             AVLNode thread)

Assign the right child node, or the right thread if child is null. Mark the node as not right threaded. The right link is not a link to a next node in the enumeration.

Parameters:

child - the new right child node

thread - the node to assign as the right thread, iff child == null

setRightChild

protected void setRightChild(AVLNode child)

Assign the right child node. Mark the node as not right threaded. The right link is not a link to a next node in the enumeration.

Parameters:

child - the new right child node

hasRightThread

protected boolean hasRightThread()

Return true if the node is right threaded, that is the rightLink() is a link to a next node in the enumeration. Note: this right thread link may be null. This method is really the equivalent to !(hasRightChild())

hasRightChild

public final boolean hasRightChild()

Return true if the node has a right child.

Returns:

true if the node has a right child.

getNextNode

public AVLNode getNextNode()

Get the next node. If the node has a right child, we find its letftmost descendent.

Returns:

the next node, or null if there is no next node node.

leftMostDescendent

public AVLNode leftMostDescendent()

Return the left-most descendent

Returns:

the left-most descendent

getPreviousNode

public AVLNode getPreviousNode()

Get the previous node. If the node has a left child, we find its rightmost descendent.

Returns:

the previous node, or null if there is no previous node.

rightMostDescendent

public AVLNode rightMostDescendent()

Return the right-most descendent

Returns:

the right-most descendent

search

public static AVLNode search(Object object,
                             AVLNode node,
                             Comparator comparator)

Search for an object in the tree rooted by node, using the comparator.

Parameters:

the - object to search for

node - the root node to start the search

comparator - the comparator to use. The object is passed as the first argument to the Comparator.compare(Object, Object) method; the element from the AVL tree nodes is passed as the second.

Returns:

the AVLNode that contains an item matcing the object, or null if no item was found.

add

public static AVLNode add(Object object,
                          AVLNode root,
                          Comparator comparator,
                          boolean allowDuplicates)

Add the object into a tree rooted at root, using the comparator.

Parameters:

object - the object to insert into the tree

root - the root node. This may be null

comparator - the Comparator to use when comparing items.

allowDuplicates - if true, you can insert equal items into the tree; a unique identifier is assigned each node and that is used to distinguish items.

Returns:

the new root, or null if a item that equals node.object already exists in the tree and allowDuplicates is false

add

public static AVLNode add(AVLNode node,
                          AVLNode root,
                          Comparator comparator,
                          boolean allowDuplicates)

Add a AVL node into a tree rooted at root, using the comparator.

Parameters:

node - an AVL tree node

root - the root node. This may be null

comparator - the Comparator to use when comparing items.

allowDuplicates - if true, you can insert equal items into the tree; a unique identifier is assigned each node and that is used to distinguish items.

Returns:

the new root, or null if a item that equals node.object already exists in the tree and allowDuplicates is false

getItems

public Enumeration getItems()

Return an enumeration of the items in the tree rooted at this node.

Specified by:

getItems in interface Enumerable

Following copied from interface: com.sas.util.Enumerable

Returns:

an enumeration of objects. If the Enumerable does not support enumerations, the getItems() method returns null (An empty Enumerable still returns a non-null Enumeration, but the first call to hasMoreElements() returns false).

getItems

public Enumeration getItems(int start,
                            int end)

Get an enumeration of the tree contents, or a subrange of items.

Parameters:

start - the enumeration after start items.

end - the enumeration after end items.

getItems

public AVLNode.Cursor getItems(boolean reversedOrder)

Get an enumeration of the tree contents.

Parameters:

backwards - if true, the enumeration traverses the tree backwards, from the end to the beginning.

find

public static AVLNode find(AVLNode root,
                           Object object,
                           Comparator comparator)

Search for and return a value in the AVL tree

Parameters:

root - the root of the tree

object - The object to search for

comparator - comparison function

Returns:

The first node whose getObject() equals the object, or null if none was found

toString

public String toString()

Return the string representation of this node. This calls toString(false, false)

Overrides:

toString in class Object

Returns:

the string representation of this node.

toString

public String toString(boolean printValue,
                       boolean showThreads)

Return the string representation of this node.

Parameters:

printValue - if true, include getObject().toString()

showThreads - if true, show left/right threading information

Returns:

the string representation of this node.

clone

public Object clone()
             throws CloneNotSupportedException

Clone this AVL tree node. The subtrees or the object held in this node are not cloned.

Specified by:

clone in interface PublicClonable

Overrides:

clone in class Object

Returns:

a clone of this node.