cnslab.cnsmath

Class RBCell<T extends Comparable>

java.lang.Object

cnslab.cnsmath.Cell<T>

cnslab.cnsmath.RBCell<T>

All Implemented Interfaces:

Serializable, Cloneable

public class RBCell<T extends Comparable>
extends Cell<T>

RBCell implements basic capabilities of Red-Black trees, an efficient kind of balanced binary tree. The particular algorithms used are adaptations of those in Corman, Lieserson, and Rivest's Introduction to Algorithms. This class was inspired by (and code cross-checked with) a similar class by Chuck McManis. The implementations of rebalancings during insertion and deletion are a little trickier than those versions since they don't swap cell contents or use a special dummy nilnodes.

It is a pure implementation class. For harnesses, see:

Version:

0.93

For an introduction to this package see Overview .

Author:

Doug Lea

See Also:

RBTree, Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	color_ The node color (RED, BLACK)
protected RBCell	left_ Pointer to left child
protected RBCell	right_ Pointer to right child

Fields inherited from class cnslab.cnsmath.Cell

element_

Constructor Summary

Constructors

Constructor and Description
RBCell(T element) Make a new cell with given element, null links, and BLACK color.

Method Summary

Methods

Modifier and Type	Method and Description
int	count(T element) Return number of nodes of current subtree containing element.
RBCell	delete(RBCell root) Delete the current node, and then rebalance the tree it is in
RBCell	find(T element) Return node of current subtree containing element as element(), if it exists, else null.
protected RBCell	fixAfterDeletion(RBCell root) From CLR
protected RBCell	fixAfterInsertion(RBCell root) From CLR
RBCell	insertLeft(RBCell cell, RBCell root) There's no generic element insertion.
RBCell	insertRight(RBCell cell, RBCell root) Insert cell as the right child of current node, and then rebalance the tree it is in.
boolean	isRoot() Return true if node is a root (i.e., has a null parent)
RBCell	left() Return left child (or null)
RBCell	leftmost() Return the minimum element of the current (sub)tree
RBCell	parent() Return parent (or null)
RBCell<T>	predecessor() Return the inorder predecessor, or null if no such
RBCell	right() Return right child (or null)
RBCell	rightmost() Return the maximum element of the current (sub)tree
RBCell	root() Return the root (parentless node) of the tree
protected RBCell	rotateLeft(RBCell root) From CLR
protected RBCell	rotateRight(RBCell root) From CLR
int	size() Return the number of nodes in the subtree
RBCell<T>	successor() Return the inorder successor, or null if no such
RBCell<T>	treeMaximum()
RBCell<T>	treeMinimum() Searches a node with smallest key starting from the node x which is usually the root.

Methods inherited from class cnslab.cnsmath.Cell

clone, element, element

Methods inherited from class java.lang.Object

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

Field Detail

color_

protected boolean color_

The node color (RED, BLACK)

left_

protected RBCell left_

Pointer to left child

right_

protected RBCell right_

Pointer to right child

Constructor Detail

RBCell

public RBCell(T element)

Make a new cell with given element, null links, and BLACK color. Normally only called to establish a new root.

Method Detail

left

public final RBCell left()

Return left child (or null)

right

public final RBCell right()

Return right child (or null)

parent

public final RBCell parent()

Return parent (or null)

leftmost

public final RBCell leftmost()

Return the minimum element of the current (sub)tree

rightmost

public final RBCell rightmost()

Return the maximum element of the current (sub)tree

root

public final RBCell root()

Return the root (parentless node) of the tree

isRoot

public final boolean isRoot()

Return true if node is a root (i.e., has a null parent)

successor

public final RBCell<T> successor()

Return the inorder successor, or null if no such

predecessor

public final RBCell<T> predecessor()

Return the inorder predecessor, or null if no such

size

public final int size()

Return the number of nodes in the subtree

find

public RBCell find(T element)

Return node of current subtree containing element as element(), if it exists, else null. Uses Comparator cmp to find and to check equality.

count

public int count(T element)

Return number of nodes of current subtree containing element. Uses Comparator cmp to find and to check equality.

insertLeft

public RBCell insertLeft(RBCell cell,
                RBCell root)

There's no generic element insertion. Instead find the place you want to add a node and then invoke insertLeft or insertRight.

Insert cell as the left child of current node, and then rebalance the tree it is in.

Parameters:

cell - the cell to add

root, - the root of the current tree

Returns:

the new root of the current tree. (Rebalancing can change the root!)

insertRight

public RBCell insertRight(RBCell cell,
                 RBCell root)

Insert cell as the right child of current node, and then rebalance the tree it is in.

Parameters:

cell - the cell to add

root, - the root of the current tree

Returns:

the new root of the current tree. (Rebalancing can change the root!)

delete

public RBCell delete(RBCell root)

Delete the current node, and then rebalance the tree it is in

Parameters:

root - the root of the current tree

Returns:

the new root of the current tree. (Rebalancing can change the root!)

treeMinimum

public RBCell<T> treeMinimum()

Searches a node with smallest key starting from the node x which is usually the root. Runs in O(h) time where h is the height of the tree.

Parameters:

x - The node from which to start, usually the root.

Returns:

The node with the smallest key.

Throws:

NullPointerException - If the parameter x is null.

treeMaximum

public RBCell<T> treeMaximum()

rotateLeft

protected final RBCell rotateLeft(RBCell root)

From CLR

rotateRight

protected final RBCell rotateRight(RBCell root)

From CLR

fixAfterInsertion

protected final RBCell fixAfterInsertion(RBCell root)

From CLR

fixAfterDeletion

protected final RBCell fixAfterDeletion(RBCell root)

From CLR