EMPTY</H3><PRE>public static final <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>EMPTY</B></PRE><DL><DD>the unique empty node; used as children on leaf trees and as empty search trees.</DL><!-- ========= CONSTRUCTOR DETAIL ======== --><A NAME="constructor_detail"><!-- --></A><TABLE BORDER="1" CELLPADDING="3" CELLSPACING="0" WIDTH="100%"><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TD COLSPAN=1><FONT SIZE="+2"><B>Constructor Detail</B></FONT></TD></TR></TABLE><A NAME="RedBlackTree()"><!-- --></A><H3>RedBlackTree</H3><PRE>protected <B>RedBlackTree</B>()</PRE><DL><DD>A one-time constructor, for constructing empty trees.</DL><HR><A NAME="RedBlackTree(java.lang.Comparable)"><!-- --></A><H3>RedBlackTree</H3><PRE>public <B>RedBlackTree</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html">Comparable</A>&nbsp;v)</PRE><DL><DD>Constructs a red-black tree with no children, value of the node  is provided by the user<DD><DL><DT><B>Parameters:</B><DD><CODE>value</CODE> - A (possibly null) value to be referenced by node</DL></DD></DL><!-- ============ METHOD DETAIL ========== --><A NAME="method_detail"><!-- --></A><TABLE BORDER="1" CELLPADDING="3" CELLSPACING="0" WIDTH="100%"><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TD COLSPAN=1><FONT SIZE="+2"><B>Method Detail</B></FONT></TD></TR></TABLE><A NAME="isRed()"><!-- --></A><H3>isRed</H3><PRE>protected boolean <B>isRed</B>()</PRE><DL><DD>Determines if this tree is red.<DD><DL><DT><B>Postcondition:</B><DD>returns whether or not this node is red<DT><B>Returns:</B><DD>Whether or not this node is red</DL></DD></DL><HR><A NAME="isBlack()"><!-- --></A><H3>isBlack</H3><PRE>protected boolean <B>isBlack</B>()</PRE><DL><DD>Determines if this tree is black.<DD><DL><DT><B>Postcondition:</B><DD>returns whether or not this node is black<DT><B>Returns:</B><DD>Whether or not this node is black</DL></DD></DL><HR><A NAME="setRed()"><!-- --></A><H3>setRed</H3><PRE>protected void <B>setRed</B>()</PRE><DL><DD>Set this node to be a red node<DD><DL><DT><B>Postcondition:</B><DD>sets this node red</DL></DD></DL><HR><A NAME="setRed(boolean)"><!-- --></A><H3>setRed</H3><PRE>protected void <B>setRed</B>(boolean&nbsp;isRed)</PRE><DL><DD>Set this node to be a red or black node, depending on value of  <code>isRed</code>.<DD><DL><DT><B>Postcondition:</B><DD>sets this node red or black, depending on boolean isRed</DL></DD></DL><HR><A NAME="setBlack()"><!-- --></A><H3>setBlack</H3><PRE>protected void <B>setBlack</B>()</PRE><DL><DD>Set this node to be black<DD><DL><DT><B>Postcondition:</B><DD>sets this node black</DL></DD></DL><HR><A NAME="value()"><!-- --></A><H3>value</H3><PRE>protected <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A> <B>value</B>()</PRE><DL><DD>Returns value associated with this node<DD><DL><DT><B>Postcondition:</B><DD>Returns value associated with this node<DT><B>Returns:</B><DD>The node's value</DL></DD></DL><HR><A NAME="left()"><!-- --></A><H3>left</H3><PRE>protected <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>left</B>()</PRE><DL><DD>Get left subtree of current node<DD><DL><DT><B>Postcondition:</B><DD>Returns reference to left subtree, or null<DT><B>Returns:</B><DD>The left subtree of this node</DL></DD></DL><HR><A NAME="right()"><!-- --></A><H3>right</H3><PRE>protected <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>right</B>()</PRE><DL><DD>Get right subtree of current node<DD><DL><DT><B>Postcondition:</B><DD>Returns reference to right subtree, or null<DT><B>Returns:</B><DD>The right subtree of this node</DL></DD></DL><HR><A NAME="parent()"><!-- --></A><H3>parent</H3><PRE>protected <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>parent</B>()</PRE><DL><DD>Get reference to parent of this node<DD><DL><DT><B>Postcondition:</B><DD>Returns reference to parent node, or null<DT><B>Returns:</B><DD>Reference to parent of this node</DL></DD></DL><HR><A NAME="setParent(structure.RedBlackTree)"><!-- --></A><H3>setParent</H3><PRE>protected void <B>setParent</B>(<A HREF="../structure/RedBlackTree.html">RedBlackTree</A>&nbsp;newParent)</PRE><DL><DD>Update the parent of this node<DD><DL><DT><B>Parameters:</B><DD><CODE>newParent</CODE> - A reference to the new parent of this node<DT><B>Postcondition:</B><DD>Re-parents this node to parent reference, or null</DL></DD></DL><HR><A NAME="setLeft(structure.RedBlackTree)"><!-- --></A><H3>setLeft</H3><PRE>protected void <B>setLeft</B>(<A HREF="../structure/RedBlackTree.html">RedBlackTree</A>&nbsp;newLeft)</PRE><DL><DD>Update the left subtree of this node.  Parent of the left subtree is updated consistently.  Existing subtree is detached<DD><DL><DT><B>Precondition:</B><DD>newLeft is a non-null RedBlackTree node, possibly EMPTY<DT><B>Postcondition:</B><DD>does nothing to the EMPTY node;       else makes newLeft a left child of this,        and this newLeft's parent</DL></DD></DL><HR><A NAME="setRight(structure.RedBlackTree)"><!-- --></A><H3>setRight</H3><PRE>protected void <B>setRight</B>(<A HREF="../structure/RedBlackTree.html">RedBlackTree</A>&nbsp;newRight)</PRE><DL><DD>Update the right subtree of this node.  Parent of the right subtree is updated consistently.  Existing subtree is detached<DD><DL><DT><B>Precondition:</B><DD>newRight is a non-null RedBlackTree node, possibly EMPTY<DT><B>Postcondition:</B><DD>does nothing to the EMPTY node;       else makes newRight a right child of this,        and this newRight's parent</DL></DD></DL><HR><A NAME="isLeftChild()"><!-- --></A><H3>isLeftChild</H3><PRE>public boolean <B>isLeftChild</B>()</PRE><DL><DD>Determine if this node is a left child<DD><DL><DT><B>Postcondition:</B><DD>Returns true if this is a left child of parent<DT><B>Returns:</B><DD>True iff this node is a left child of parent</DL></DD></DL><HR><A NAME="isRightChild()"><!-- --></A><H3>isRightChild</H3><PRE>public boolean <B>isRightChild</B>()</PRE><DL><DD>Determine if this node is a right child<DD><DL><DT><B>Postcondition:</B><DD>Returns true if this is a right child of parent<DT><B>Returns:</B><DD>True iff this node is a right child of parent</DL></DD></DL><HR><A NAME="isEmpty()"><!-- --></A><H3>isEmpty</H3><PRE>public boolean <B>isEmpty</B>()</PRE><DL><DD>Returns true if tree is empty.<DD><DL><DT><B>Postcondition:</B><DD>Returns true iff the tree rooted at node is empty<DT><B>Returns:</B><DD>True iff tree is empty</DL></DD></DL><HR><A NAME="isRoot()"><!-- --></A><H3>isRoot</H3><PRE>protected boolean <B>isRoot</B>()</PRE><DL><DD>Determine if this node is a root.<DD><DL><DT><B>Postcondition:</B><DD>Returns true if this is a root node<DT><B>Returns:</B><DD>true iff this is a root node</DL></DD></DL><HR><A NAME="root()"><!-- --></A><H3>root</H3><PRE>protected <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>root</B>()</PRE><DL><DD>Returns reference to root of tree containing n<DD><DL><DT><B>Precondition:</B><DD>this node not EMPTY<DT><B>Postcondition:</B><DD>Returns the root of the tree node n<DT><B>Returns:</B><DD>Root of tree</DL></DD></DL><HR><A NAME="depth()"><!-- --></A><H3>depth</H3><PRE>public int <B>depth</B>()</PRE><DL><DD>Compute the depth of a node.  The depth is the path length from node to root<DD><DL><DT><B>Postcondition:</B><DD>Returns the depth of a node in the tree<DT><B>Returns:</B><DD>The path length to root of tree</DL></DD></DL><HR><A NAME="rotateRight()"><!-- --></A><H3>rotateRight</H3><PRE>protected void <B>rotateRight</B>()</PRE><DL><DD>Method to perform a right rotation of tree about this node Node must have a left child.  Relation between left child and node are reversed<DD><DL><DT><B>Precondition:</B><DD>This node has a left subtree<DT><B>Postcondition:</B><DD>Rotates local portion of tree so left child is root</DL></DD></DL><HR><A NAME="rotateLeft()"><!-- --></A><H3>rotateLeft</H3><PRE>protected void <B>rotateLeft</B>()</PRE><DL><DD>Method to perform a left rotation of tree about this node Node must have a right child.  Relation between right child and node are reversed<DD><DL><DT><B>Precondition:</B><DD>This node has a right subtree<DT><B>Postcondition:</B><DD>Rotates local portion of tree so right child is root</DL></DD></DL><HR><A NAME="add(java.lang.Comparable)"><!-- --></A><H3>add</H3><PRE>public <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>add</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html">Comparable</A>&nbsp;c)</PRE><DL><DD>Add a value to the red black tree, performing neccisary rotations and adjustments.<DD><DL><DT><B>Parameters:</B><DD><CODE>c</CODE> - The value to be added to the tree.<DT><B>Precondition:</B><DD>c is a non-null Comparable value<DT><B>Postcondition:</B><DD>adds a comparable value to the red-black tree;       returns the modified tree<DT><B>Returns:</B><DD>The new value of the root.</DL></DD></DL>