com.tangosol.util
Class Tree

java.lang.Object
  com.tangosol.util.Base
      com.tangosol.util.Tree

All Implemented Interfaces:

Serializable, Cloneable

public class Tree
extends Base
implements Cloneable, Serializable

A red/black tree is a combination of a 2-3-4 B-tree and binary search tree. The tree's balance is maintained on insertions and deletions only. On the average, less than one rotation occurs per insertion/deletion. Searching the tree uses the simple binary search algorithm, which is very efficient since the tree is kept in a balanced state. The manner in which a red- black tree is balanced ensures that the longest branch of the tree is no longer than twice the length of the shortest branch of the tree. In tests with a Java implementation of a red/black tree, a hash table out-performed the tree on insertions and deletions by a factor of 2:1. The benefit of a binary tree, however, is that the values are maintained in order and therefor are enumerated in order.

Version:

0.50 09/05/97, 1.00 07/28/98 moved Node and Crawler in as inner classes

Author:

Cameron Purdy

Nested Class Summary

protected static class	Tree.Crawler A red/black tree node iterator.
protected static class	Tree.Node A red/black tree node.

Field Summary

protected Tree.Node	head The first node of the tree (or NIL if the tree is empty).
protected static Tree.Node	NIL NIL is the sentinal Node that is used instead of null, simplifying the implementation of the red/black tree.
protected int	size The number of nodes in the tree.

Constructor Summary

Tree()
Default constructor.

Method Summary

void	add(Comparable key) Add the passed key to the tree.
boolean	addAll(Tree that) Adds all of the nodes in the specified Tree to this Tree if they are not already present.
void	clear() Remove all nodes from the tree.
Object	clone() Make a shallow copy of the tree and its nodes.
boolean	contains(Comparable key) Determine if the passed key is in the tree.
Enumeration	elements() Create an enumerator for the tree's values.
boolean	equals(Object obj) Test for tree equality.
protected Tree.Node	find(Comparable key) Find the specified key and return its node.
Object	get(Comparable key) Find the specified key and return its value.
int	getSize() Determine the size of the tree.
protected Tree.Crawler	getUnsynchronizedNodeEnumerator() Get an enumerator of the nodes in the tree.
protected Tree.Crawler	getUnsynchronizedNodeEnumerator(Comparable key) Get an enumerator of the nodes in the tree.
boolean	isEmpty() Test for empty tree.
Enumeration	keys() Create an in-order enumerator for the tree's keys.
void	print() In-order printing of the contents of the tree.
void	put(Comparable key, Object value) Add the passed key to the tree and associate the passed value with the key.
void	putAll(Tree that) Puts all of the nodes in the specified Tree to this Tree (including the ones that are already present).
Object	remove(Comparable key) Remove the specified key from the tree, returning its associated value.
boolean	removeAll(Tree that) Removes from this Tree all of its nodes that are contained in the specified Tree.
boolean	retainAll(Tree that) Retains only the nodes in this Tree that are contained in the specified Tree.
String	toString() Provide a string representation of the tree.

Field Detail

NIL

protected static final Tree.Node NIL

NIL is the sentinal Node that is used instead of null, simplifying the implementation of the red/black tree.

head

protected Tree.Node head

The first node of the tree (or NIL if the tree is empty). The first node is referred to as the "head" or the "root" node.

size

protected int size

The number of nodes in the tree. This can be determined by iterating through the tree, but by keeping the size cached, certain operations that need the size of the tree up front are much more efficient.

Constructor Detail

Tree

public Tree()

Default constructor.

Method Detail

add

public void add(Comparable key)

Add the passed key to the tree.

Parameters:

key - the key to add to the tree

put

public void put(Comparable key,
                Object value)

Add the passed key to the tree and associate the passed value with the key. If the key is already in the tree, the passed value will replace the current value stored with the key.

Parameters:

key - the key to add to the tree

value - the object to associate with the key

get

public Object get(Comparable key)

Find the specified key and return its value.

Parameters:

key - the key to look for in the tree

Returns:

the associated value or null if the key is not in the tree

contains

public boolean contains(Comparable key)

Determine if the passed key is in the tree.

Parameters:

key - the key to look for in the tree

Returns:

true if the key is in the tree, false otherwise

remove

public Object remove(Comparable key)

Remove the specified key from the tree, returning its associated value.

Parameters:

key - the key to look for in the tree

Returns:

the associated value (which can be null) or null if the key is not in the tree

clear

public void clear()

Remove all nodes from the tree.

getSize

public int getSize()

Determine the size of the tree.

Returns:

the number of nodes in the tree

isEmpty

public boolean isEmpty()

Test for empty tree.

Returns:

true if tree has no nodes

keys

public Enumeration keys()

Create an in-order enumerator for the tree's keys.

Returns:

an enumerator of the tree's keys

elements

public Enumeration elements()

Create an enumerator for the tree's values.

Returns:

an enumerator of the tree's values (in the same order that the keys were returned)

addAll

public boolean addAll(Tree that)

Adds all of the nodes in the specified Tree to this Tree if they are not already present. This operation effectively modifies this Tree so that its value is the union of the two Trees. The behavior of this operation is unspecified if the specified Tree is modified while the operation is in progress.

Returns:

true if this Tree changed as a result of the call.

See Also:

Collection.addAll(Collection)

putAll

public void putAll(Tree that)

Puts all of the nodes in the specified Tree to this Tree (including the ones that are already present). This operation effectively modifies this Tree so that its value is the union of the two Trees. The behavior of this operation is unspecified if the specified Tree is modified while the operation is in progress.

retainAll

public boolean retainAll(Tree that)

Retains only the nodes in this Tree that are contained in the specified Tree. In other words, removes from this Tree all of its nodes that are not contained in the specified Tree. This operation effectively modifies this Tree so that its value is the intersection of the two Trees.

Returns:

true if this Collection changed as a result of the call.

See Also:

Collection.retainAll(Collection)

removeAll

public boolean removeAll(Tree that)

Removes from this Tree all of its nodes that are contained in the specified Tree. This operation effectively modifies this Tree so that its value is the asymmetric set difference of the two Trees.

Returns:

true if this Tree changed as a result of the call.

See Also:

Collection.removeAll(Collection)

toString

public String toString()

Provide a string representation of the tree.

equals

public boolean equals(Object obj)

Test for tree equality.

clone

public Object clone()

Make a shallow copy of the tree and its nodes. Note that cloning does make new copies of each node.

print

public void print()

In-order printing of the contents of the tree.

getUnsynchronizedNodeEnumerator

protected Tree.Crawler getUnsynchronizedNodeEnumerator()

Get an enumerator of the nodes in the tree. This enumerator is not in any way thread-safe, so the tree should be synchronized for as long as this enumerator is in use. Note: Purposefully package private; used by StringTable

getUnsynchronizedNodeEnumerator

protected Tree.Crawler getUnsynchronizedNodeEnumerator(Comparable key)

Get an enumerator of the nodes in the tree. This enumerator is not in any way thread-safe, so the tree should be synchronized for as long as this enumerator is in use. Note: Purposefully package private; used by StringTable

find

protected Tree.Node find(Comparable key)

Find the specified key and return its node.

Parameters:

key - the key to look for in the tree

Returns:

the node containing the key or null if the key is not in the tree