All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class collections.RBCell 

java.lang.Object
   |
   +----collections.Cell
           |
           +----collections.RBCell
public class RBCell
extends Cell
implements ImplementationCheckable
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:

See Also:
RBTree

Variable Index

o color_
The node color (RED, BLACK)
o left_
Pointer to left child
o right_
Pointer to right child

Constructor Index

o RBCell(Object)
Make a new cell with given element, null links, and BLACK color.

Method Index

o assert(boolean)
Implements collections.ImplementationCheckable.assert.
o checkImplementation()
o clone()
Return a new RBCell with same element and color as self, but with null links.
o copyTree()
Return a new subtree containing each element of current subtree
o count(Object, Comparator)
Return number of nodes of current subtree containing element.
o delete(RBCell)
Delete the current node, and then rebalance the tree it is in
o find(Object, Comparator)
Return node of current subtree containing element as element(), if it exists, else null.
o fixAfterDeletion(RBCell)
From CLR
o fixAfterInsertion(RBCell)
From CLR
o insertLeft(RBCell, RBCell)
There's no generic element insertion.
o insertRight(RBCell, RBCell)
Insert cell as the right child of current node, and then rebalance the tree it is in.
o isRoot()
Return true if node is a root (i.e., has a null parent)
o left()
Return left child (or null)
o leftmost()
Return the minimum element of the current (sub)tree
o parent()
Return parent (or null)
o predecessor()
Return the inorder predecessor, or null if no such
o right()
Return right child (or null)
o rightmost()
Return the maximum element of the current (sub)tree
o root()
Return the root (parentless node) of the tree
o rotateLeft(RBCell)
From CLR
o rotateRight(RBCell)
From CLR
o size()
Return the number of nodes in the subtree
o successor()
Return the inorder successor, or null if no such

Variables

o color_ 
 protected boolean color_
The node color (RED, BLACK)

o left_ 
 protected RBCell left_
Pointer to left child

o right_ 
 protected RBCell right_
Pointer to right child

Constructors

o RBCell 
 public RBCell(Object element)
Make a new cell with given element, null links, and BLACK color. Normally only called to establish a new root.

Methods

o clone 
 protected Object clone() throws CloneNotSupportedException
Return a new RBCell with same element and color as self, but with null links. (Since it is never OK to have multiple identical links in a RB tree.)

Overrides:
clone in class Cell
o left 
 public final RBCell left()
Return left child (or null)

o right 
 public final RBCell right()
Return right child (or null)

o parent 
 public final RBCell parent()
Return parent (or null)

o checkImplementation 
 public void checkImplementation() throws ImplementationError
See Also:
o assert 
 public void assert(boolean pred) throws ImplementationError
Implements collections.ImplementationCheckable.assert.

See Also:
assert
o leftmost 
 public final RBCell leftmost()
Return the minimum element of the current (sub)tree

o rightmost 
 public final RBCell rightmost()
Return the maximum element of the current (sub)tree

o root 
 public final RBCell root()
Return the root (parentless node) of the tree

o isRoot 
 public final boolean isRoot()
Return true if node is a root (i.e., has a null parent)

o successor 
 public final RBCell successor()
Return the inorder successor, or null if no such

o predecessor 
 public final RBCell predecessor()
Return the inorder predecessor, or null if no such

o size 
 public final int size()
Return the number of nodes in the subtree

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

o count 
 public int count(Object element,
                  Comparator cmp)
Return number of nodes of current subtree containing element. Uses Comparator cmp to find and to check equality.

o copyTree 
 public RBCell copyTree()
Return a new subtree containing each element of current subtree

o 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!)
o 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!)
o 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!)
o rotateLeft 
 protected final RBCell rotateLeft(RBCell root)
From CLR

o rotateRight 
 protected final RBCell rotateRight(RBCell root)
From CLR

o fixAfterInsertion 
 protected final RBCell fixAfterInsertion(RBCell root)
From CLR

o fixAfterDeletion 
 protected final RBCell fixAfterDeletion(RBCell root)
From CLR 

All Packages  Class Hierarchy  This Package  Previous  Next  Index