redblacktree.html

学习JAVA的很好的JAVA包和文档包

<HR>

<A NAME="insert(java.lang.Comparable)"><!-- --></A><H3>
insert</H3>
<PRE>
protected <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>insert</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html">Comparable</A>&nbsp;c)</PRE>
<DL>
<DD>Insert a (possibly duplicate) value to red-black search tree<DD><DL>
<DT><B>Parameters:</B><DD><CODE>c</CODE> - The value to be inserted into the tree.<DT><B>Precondition:</B><DD>c is a non-null Comparable value<DT><B>Postcondition:</B><DD>c is inserted into search tree rooted at this</DL>
</DD>
</DL>
<HR>

<A NAME="redFixup()"><!-- --></A><H3>
redFixup</H3>
<PRE>
public void <B>redFixup</B>()</PRE>
<DL>
<DD>Takes a red node and, restores the red nodes of the tree  
 to maintain red-black properties if this node has a red parent.<DD><DL>
<DT><B>Precondition:</B><DD>this node is a red node; if parent is red, violates property<DT><B>Postcondition:</B><DD>red nodes of the tree are adjusted to maintain properties</DL>
</DD>
</DL>
<HR>

<A NAME="remove(java.lang.Comparable)"><!-- --></A><H3>
remove</H3>
<PRE>
public <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>remove</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html">Comparable</A>&nbsp;c)</PRE>
<DL>
<DD>Remove an value "equals to" the indicated value.  Only one value
 is removed, and no guarantee is made concerning which of duplicate
 values are removed.  Value returned is no longer part of the
 structure<DD><DL>
<DT><B>Parameters:</B><DD><CODE>val</CODE> - Value sought to be removed from tree<DT><B>Precondition:</B><DD>c is non-null<DT><B>Postcondition:</B><DD>the value is removed; resulting tree is returned<DT><B>Returns:</B><DD>Actual value removed from tree</DL>
</DD>
</DL>
<HR>

<A NAME="blackFixup()"><!-- --></A><H3>
blackFixup</H3>
<PRE>
protected void <B>blackFixup</B>()</PRE>
<DL>
<DD>If a black node has just been removed above this;
 this node is the root of a black-height balanced tree, but
 the ancestors of this node are shy one black node on this branch.
 This method restores black-height balance to such an imbalanced
 tree.<DD><DL>
<DT><B>Precondition:</B><DD>a black node has just been removed above this;
      this node is the root of a black-height balanced tree, but
      the ancestors of this node are shy one black node on this branch<DT><B>Postcondition:</B><DD>the tree is black-height balanced</DL>
</DD>
</DL>
<HR>

<A NAME="contains(java.lang.Comparable)"><!-- --></A><H3>
contains</H3>
<PRE>
public boolean <B>contains</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html">Comparable</A>&nbsp;c)</PRE>
<DL>
<DD>Determines if the red black search tree contains a value<DD><DL>
<DT><B>Parameters:</B><DD><CODE>val</CODE> - The value sought.  Should be non-null<DT><B>Precondition:</B><DD>c is non-null<DT><B>Postcondition:</B><DD>returns true iff c is contained within the tree<DT><B>Returns:</B><DD>True iff the tree contains a value "equals to" sought value</DL>
</DD>
</DL>
<HR>

<A NAME="locate(java.lang.Comparable)"><!-- --></A><H3>
locate</H3>
<PRE>
protected <A HREF="../structure/RedBlackTree.html">RedBlackTree</A> <B>locate</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html">Comparable</A>&nbsp;c)</PRE>
<DL>
<DD>Locates a value in the search tree or returns the largest value
 less than <code>value</code>.<DD><DL>
<DT><B>Precondition:</B><DD>c is non-null<DT><B>Postcondition:</B><DD>returns a node of this tree that contains c, or null</DL>
</DD>
</DL>
<HR>

<A NAME="get(java.lang.Comparable)"><!-- --></A><H3>
get</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html">Comparable</A> <B>get</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html">Comparable</A>&nbsp;c)</PRE>
<DL>
<DD>Returns a c-equivalent value from tree, or null.<DD><DL>
<DT><B>Parameters:</B><DD><CODE>c</CODE> - The c-equivalent value we are looking for in the tree.<DT><B>Precondition:</B><DD>c is non-null<DT><B>Postcondition:</B><DD>returns a c-equivalent value from tree, or null</DL>
</DD>
</DL>
<HR>

<A NAME="consistency()"><!-- --></A><H3>
consistency</H3>
<PRE>
public boolean <B>consistency</B>()</PRE>
<DL>
<DD>Returns true if this node is consistently structured<DD><DL>
<DT><B>Postcondition:</B><DD>returns true if this node is consistently structured</DL>
</DD>
</DL>
<HR>

<A NAME="blackHeight()"><!-- --></A><H3>
blackHeight</H3>
<PRE>
protected int <B>blackHeight</B>()</PRE>
<DL>
<DD>Returns the black height of this subtree.<DD><DL>
<DT><B>Precondition:</B><DD>tree is black-height balanced<DT><B>Postcondition:</B><DD>returns the black height of this subtree</DL>
</DD>
</DL>
<HR>

<A NAME="redConsistency()"><!-- --></A><H3>
redConsistency</H3>
<PRE>
protected boolean <B>redConsistency</B>()</PRE>
<DL>
<DD>Returns true if no red node in subtree has red children<DD><DL>
<DT><B>Postcondition:</B><DD>returns true if no red node in subtree has red children</DL>
</DD>
</DL>
<HR>

<A NAME="blackConsistency()"><!-- --></A><H3>
blackConsistency</H3>
<PRE>
protected boolean <B>blackConsistency</B>()</PRE>
<DL>
<DD>Returns true if black properties of tree are correct<DD><DL>
<DT><B>Postcondition:</B><DD>returns true if black properties of tree are correct</DL>
</DD>
</DL>
<HR>

<A NAME="consistentlyBlackHeight(int)"><!-- --></A><H3>
consistentlyBlackHeight</H3>
<PRE>
protected boolean <B>consistentlyBlackHeight</B>(int&nbsp;height)</PRE>
<DL>
<DD>Checks to make sure that the black height of tree is height<DD><DL>
<DT><B>Postcondition:</B><DD>checks to make sure that the black height of tree is height</DL>
</DD>
</DL>
<HR>

<A NAME="wellConnected(structure.RedBlackTree)"><!-- --></A><H3>
wellConnected</H3>
<PRE>
public boolean <B>wellConnected</B>(<A HREF="../structure/RedBlackTree.html">RedBlackTree</A>&nbsp;expectedParent)</PRE>
<DL>
<DD>Returns true iff this tree is well-connected.</DL>
<HR>

<A NAME="print()"><!-- --></A><H3>
print</H3>
<PRE>
public void <B>print</B>()</PRE>
<DL>
</DL>
<HR>

<A NAME="iterator()"><!-- --></A><H3>
iterator</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/util/Iterator.html">Iterator</A> <B>iterator</B>()</PRE>
<DL>
<DD>Returns an in-order iterator over the subtree rooted at 
 this node.<DD><DL>
<DT><B>Returns:</B><DD>An in-order iterator over the subtree rooted at 
 this node.</DL>
</DD>
</DL>
<HR>

<A NAME="hashCode()"><!-- --></A><H3>
hashCode</H3>
<PRE>
public int <B>hashCode</B>()</PRE>
<DL>
<DD>Computes hash code associated with values of tree.<DD><DL>
<DT><B>Overrides:</B><DD><CODE><A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html#hashCode()">hashCode</A></CODE> in class <CODE><A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Postcondition:</B><DD>computes hash code associated with values of tree</DL>
</DD>
</DL>
<HR>

<A NAME="treeString()"><!-- --></A><H3>
treeString</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/String.html">String</A> <B>treeString</B>()</PRE>
<DL>
<DD>Returns a string representing the tree rooted at this node.
 <font color="#FF0000">WARNING</font> this can be a very long string.<DD><DL>
<DT><B>Returns:</B><DD>A string representing the tree rooted at this node.</DL>
</DD>
</DL>
<HR>

<A NAME="getHand()"><!-- --></A><H3>
getHand</H3>
<PRE>
private <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/String.html">String</A> <B>getHand</B>()</PRE>
<DL>
<DD>Support method for <A HREF="../structure/RedBlackTree.html#toString()"><CODE>toString()</CODE></A>. Returns R if this is node 
 is a right child, L if this node is a left child and Root if this
 node is the root.<DD><DL>
<DT><B>Returns:</B><DD>R if this is node 
 is a right child, L if this node is a left child and Root if this
 node is the root.</DL>
</DD>
</DL>
<HR>

<A NAME="getColor()"><!-- --></A><H3>
getColor</H3>
<PRE>
private <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/String.html">String</A> <B>getColor</B>()</PRE>
<DL>
<DD>Support method for <A HREF="../structure/RedBlackTree.html#toString()"><CODE>toString()</CODE></A>. Returns Red if this is node 
 is a red, and Black if this node is black.<DD><DL>
<DT><B>Returns:</B><DD>R if this is node 
 is a right child, L if this node is a left child and Root if this
 node is the root.</DL>
</DD>
</DL>
<HR>

<A NAME="toString()"><!-- --></A><H3>
toString</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/String.html">String</A> <B>toString</B>()</PRE>
<DL>
<DD>Returns string representation of red-black tree.<DD><DL>
<DT><B>Overrides:</B><DD><CODE><A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html#toString()">toString</A></CODE> in class <CODE><A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Precondition:</B><DD>returns string representation of red-black tree</DL>
</DD>
</DL>
<!-- ========= END OF CLASS DATA ========= -->
<HR>

<!-- ========== START OF NAVBAR ========== -->
<A NAME="navbar_bottom"><!-- --></A>
<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0">
<TR>
<TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
<A NAME="navbar_bottom_firstrow"><!-- --></A>
<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3">
  <TR ALIGN="center" VALIGN="top">
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;<FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A>&nbsp;</TD>
  </TR>
</TABLE>
</TD>
<TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM>
<a href=../copyright.html target=_top>&copy; 1998-2002 McGraw-Hill</a></EM>
</TD>
</TR>

<TR>
<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
&nbsp;<A HREF="../structure/RedBlackSearchTree.html"><B>PREV CLASS</B></A>&nbsp;
&nbsp;<A HREF="../structure/ReverseComparator.html"><B>NEXT CLASS</B></A></FONT></TD>
<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
  <A HREF="../index.html" TARGET="_top"><B>FRAMES</B></A>  &nbsp;
&nbsp;<A HREF="RedBlackTree.html" TARGET="_top"><B>NO FRAMES</B></A></FONT></TD>
</TR>
<TR>
<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
  SUMMARY: &nbsp;INNER&nbsp;|&nbsp;<A HREF="#field_summary">FIELD</A>&nbsp;|&nbsp;<A HREF="#constructor_summary">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_summary">METHOD</A></FONT></TD>
<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
DETAIL: &nbsp;<A HREF="#field_detail">FIELD</A>&nbsp;|&nbsp;<A HREF="#constructor_detail">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_detail">METHOD</A></FONT></TD>
</TR>
</TABLE>
<!-- =========== END OF NAVBAR =========== -->

<HR>

</BODY>
</HTML>