com.tangosol.util
Class Tree.Node

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

All Implemented Interfaces:

Serializable, Cloneable

Enclosing class:

Tree

protected static class Tree.Node
extends Object
implements Cloneable, Serializable

A red/black tree node. This class is used only within the Tree class.

This class represents a data structure used by the Tree class. The methods of this class are not synchronized; synchronization is the responsibility of the Tree class. The data members are not private; they are "package" private so that they can be manipularted by the Tree class (and related classes, like Crawler). The Node class is not an "inner" class of Tree due to the requirement to make a static final (i.e. constant) NIL node.

Author:

Cameron Purdy

Field Summary

protected Comparable	key The key of the node.
protected Tree.Node	left The left child of this node.
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 Tree.Node	parent The parent of this node.
protected boolean	red The color (red or black) of this node.
protected Tree.Node	right The right child of this node.
protected Object	value The value associated with the key.

Constructor Summary

Tree.Node()
Default constructor.

Method Summary

Object	clone() Make a shallow copy of the node and its sub-nodes.
boolean	equals(Object obj) Test for node equality.
protected int	getDepth() Determine the 2-3-4 node depth of this node (i.e.
protected boolean	isLeaf() Determine if this node is a part of a 2-3-4 leaf node (i.e.
protected void	print() In-order printing of the contents of the node and its children.
String	toString() Provide a string representation of this node's value.

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.

key

protected Comparable key

The key of the node. The key is always assumed to be non-null. The key, once set, is considered immutable.

value

protected Object value

The value associated with the key.

parent

protected Tree.Node parent

The parent of this node.

left

protected Tree.Node left

The left child of this node.

right

protected Tree.Node right

The right child of this node.

red

protected boolean red

The color (red or black) of this node.

Constructor Detail

Tree.Node

public Tree.Node()

Default constructor.

Method Detail

toString

public String toString()

Provide a string representation of this node's value.

equals

public boolean equals(Object obj)

Test for node equality.

clone

public Object clone()

Make a shallow copy of the node and its sub-nodes.

isLeaf

protected boolean isLeaf()

Determine if this node is a part of a 2-3-4 leaf node (i.e. at least one NIL child).

Returns:

true if this node is a leaf

getDepth

protected int getDepth()

Determine the 2-3-4 node depth of this node (i.e. the number of black links from the head to this node).

Returns:

the (black) depth of the node

print

protected void print()

In-order printing of the contents of the node and its children.