com.sas.collection
Class AVLTree

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

All Implemented Interfaces:

Countable, Enumerable, PublicClonable,

public class AVLTree

extends java.lang.Object

implements java.io.Serializable, PublicClonable, Enumerable, Countable

An AVL tree, named after Adelson-Velskii and Landis. An AVL Tree consists of a root AVLNode and a comparator which is used to add new items or to search for values.

Since:

1.2

See Also:

Serialized Form

Field Summary

static String

RB_KEY

Constructor Summary

AVLTree()

AVLTree(Comparator comparator)

AVLTree(Comparator comparator, boolean duplicatesAllowed)

Method Summary

void	add(Object object) Add the object into a tree rooted at root, using the comparator.
Object	clone() Clone this AVL tree node.
boolean	contains(Object object) Test if an object exists in the tree.
int	count() Return the number of nodes in the tree.
AVLNode	firstNode()
Object	get(Object query) Return the object in the tree which is equal to query
Comparator	getComparator() Return the comparator used to compare items.
Enumeration	getItems() Get an enumeration of the tree contents
AVLNode.Cursor	getItems(boolean backwards) Get an enumeration of the tree contents.
Enumeration	getItems(int start, int end) Get an enumeration of the tree contents
boolean	isDuplicatesAllowed() Return true if duplicate values may be added to the AVL tree.
AVLNode	lastNode()
boolean	remove(Object object) Remove an object from the tree.
void	removeAll() Remove all items from the tree.
AVLNode	root()
void	setComparator(Comparator newComparator) Set the comparator.
void	setDuplicatesAllowed(boolean duplicatesAllowed) Set the whether the tree allows duplicate values to be inserted.

Methods inherited from class java.lang.Object

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

Field Detail

RB_KEY

public static final String RB_KEY

Constructor Detail

AVLTree

public AVLTree()

AVLTree

public AVLTree(Comparator comparator)

AVLTree

public AVLTree(Comparator comparator,
               boolean duplicatesAllowed)

Method Detail

count

public int count()

Return the number of nodes in the tree.

Specified by:

count in interface Countable

Returns:

the number of nodes in the tree.

setComparator

public void setComparator(Comparator newComparator)

Set the comparator. This will also empty the tree and add the items back in.

Parameters:

newComparator - the new comparator.

removeAll

public void removeAll()

Remove all items from the tree.

root

public AVLNode root()

firstNode

public AVLNode firstNode()

lastNode

public AVLNode lastNode()

getComparator

public Comparator getComparator()

Return the comparator used to compare items.

Returns:

the tree's comparator.

setDuplicatesAllowed

public void setDuplicatesAllowed(boolean duplicatesAllowed)

Set the whether the tree allows duplicate values to be inserted.

Parameters:

duplicatesAllowed - if false, you cannot add an item that already exists to an AVLTree.

isDuplicatesAllowed

public boolean isDuplicatesAllowed()

Return true if duplicate values may be added to the AVL tree.

Returns:

true if duplicate values may be added to the AVL tree.

add

public void add(Object object)

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

Parameters:

object - the object to add into the tree

root - the root node. This may be null

comparator - the Comparator to use when comparing items.

Returns:

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

contains

public boolean contains(Object object)

Test if an object exists in the tree.

Parameters:

object - a value to search for. The tree's comparator is used; the object will be the first parameter.

Returns:

true if the object exists.

get

public Object get(Object query)

Return the object in the tree which is equal to query

Parameters:

query - a value to search for. The tree's comparator is used; the query object will be the first parameter to the comparator's compare method; the item in the tree will be the second parameter.

Returns:

a non-null value if an object equal to query exists

remove

public boolean remove(Object object)

Remove an object from the tree.

Parameters:

object - a value to remove. The tree's comparator is used; the object will be the first parameter.

Returns:

true if the object was removed.

getItems

public Enumeration getItems()

Get an enumeration of the tree contents

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

getItems

public AVLNode.Cursor getItems(boolean backwards)

Get an enumeration of the tree contents.

Parameters:

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

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.

See Also:

AVLNode.clone()