📄 page408.html

📁 Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and
💻 HTML
字号:
<HTML><HEAD><TITLE>find and join Methods</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5880" HREF="page409.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5878" HREF="page405.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5874" HREF="page407.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5882" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0012413000000000000000"><tt>find</tt> and <tt>join</tt> Methods</A></H3><P>Two elements of the universe are in the same part of the partitionif and only if they share the same root node.Since every tree has a unique root,it makes sense to use the root node as the ``handle'' for that tree.Therefore, the <em>find</em> operation takes an element of the universal setand returns the root node of the tree that contains that element.And because of way in which the trees are represented,we can follow the chain of parent pointers to find the root node.<P>Program&nbsp;<A HREF="page408.html#progpartitionAsForestc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for the <tt>find</tt>method of the <tt>PartitionAsForest</tt> class.The <tt>find</tt> method takes as its argumentan <tt>int</tt> and returns a set.The argument specifies the item of the universethat is the object of the search.<P><P><A NAME="28808">&#160;</A><A NAME="progpartitionAsForestc">&#160;</A> <IMG WIDTH=575 HEIGHT=180 ALIGN=BOTTOM ALT="program28744" SRC="img1630.gif"  ><BR><STRONG>Program:</STRONG> <tt>PartitionAsForest</tt> class <tt>find</tt> method.<BR><P><P>The <tt>find</tt> operation begins at the node <tt>_array[item]</tt>and follows the chain of parent instance attributesto find the root node of the treethat contains the specified item.The result of the method is the root node.<P>The running time of the <tt>find</tt> operationis <I>O</I>(<I>d</I>) where <I>d</I> is the depthin the tree of the node from which the search begins.If we don't do anything special to prevent it,the worst case running time is <I>O</I>(<I>N</I>),where <I>N</I> is the size of the universe.The best performance is achieved when every non-root nodepoints to the root node.In this case, the running time is <I>O</I>(1).<P>Another advantage of having the parent instance attribute in each nodeis that the <em>join</em> operation can be implemented easily and efficiently.For example, suppose we wish to <em>join</em>the two sets  <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif"  > and  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59801" SRC="img455.gif"  > shown in Figure&nbsp;<A HREF="page405.html#figsets1"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.While there are many possible representations for  <IMG WIDTH=50 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67101" SRC="img1631.gif"  >,it turns out that there are two simple alternatives which can beobtained in constant time.These are shown in Figure&nbsp;<A HREF="page405.html#figsets2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In the first alternative,the root of  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59801" SRC="img455.gif"  > is made a child of the root of  <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif"  >.This can be done in constant time simply by making the parent instance attributeof the root of  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59801" SRC="img455.gif"  > refer to the root of  <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif"  >.The second alternative is essentially the same as the firstexcept that the roles of  <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif"  > and  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59801" SRC="img455.gif"  > are exchanged.<P><P><A NAME="29073">&#160;</A><A NAME="figsets3">&#160;</A> <IMG WIDTH=575 HEIGHT=415 ALIGN=BOTTOM ALT="figure28760" SRC="img1632.gif"  ><BR><STRONG>Figure:</STRONG> Alternatives for joining elements of a partition.<BR><P><P>Program&nbsp;<A HREF="page408.html#progpartitionAsForestd"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the simplest possible implementationfor the <tt>join</tt> operation.In addition to <tt>self</tt>,the <tt>join</tt> method of the <tt>PartitionAsForest</tt> classtakes two arguments.Both arguments are required to be references to distinct<tt>PartitionTree</tt> instances which are contained in the given partition.Furthermore, both of them are required to be root nodes.Therefore, the sets that the arguments represent are <em>disjoint</em>.The <tt>assert</tt> statement makes sure that the argumentssatisfy these conditions.<P>The <tt>join</tt> operation is trivial and executes in constant time:It simply makes one node the parent of the other.In this case, we have arbitrarily chosen thatthe node specified by the first argument shall always become the parent.<P><P><A NAME="29142">&#160;</A><A NAME="progpartitionAsForestd">&#160;</A> <IMG WIDTH=575 HEIGHT=180 ALIGN=BOTTOM ALT="program29085" SRC="img1633.gif"  ><BR><STRONG>Program:</STRONG> <tt>PartitionAsForest</tt> class simple <tt>join</tt> method.<BR><P><HR><A NAME="tex2html5880" HREF="page409.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5878" HREF="page405.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5874" HREF="page407.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5882" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -