    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

##

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

##

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

##

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

##

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

##

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.

##

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

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)

checkImplementation

     public void checkImplementation() throws ImplementationError

  See Also:

assert

     public void assert(boolean pred) throws ImplementationError

  Implements collections.ImplementationCheckable.assert.

  See Also:
    assert

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 successor()

  Return the inorder successor, or null if no such

predecessor

     public final RBCell 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(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.

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.

copyTree

     public RBCell copyTree()

  Return a new subtree containing each element of current subtree

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!)

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

    All Packages  Class Hierarchy  This Package  Previous  Next  Index