📄 page410.html
字号:
<HTML><HEAD><TITLE>Union by Size</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="tex2html5902" HREF="page411.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5900" HREF="page403.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5894" HREF="page409.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5904" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0012430000000000000000">Union by Size</A></H2><P>While using collapsing find does mitigate the negative effects of poor trees,a better approach is to avoid creating bad trees in the first place.As shown in Figure <A HREF="page408.html#figsets3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,when we join to trees we have a choice--which node should we choose to be the root of the new tree.A simple, but effective choice is to attach the smaller treeunder the root of the larger one.In this case, the smaller tree is the one which has fewer nodes.This is the so-called <em>union-by-size</em><A NAME=29466> </A> join algorithm.Program <A HREF="page410.html#progpartitionAsForestV2b"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows how this can be done.<P><P><A NAME="29714"> </A><A NAME="progpartitionAsForestV2b"> </A> <IMG WIDTH=575 HEIGHT=275 ALIGN=BOTTOM ALT="program29468" SRC="img1637.gif" ><BR><STRONG>Program:</STRONG> <tt>PartitionAsForest</tt> class union-by-size <tt>join</tt> method.<BR><P><P>The implementation uses the <tt>_count</tt> instance attributeto keep track of the number of items contained in the tree.(Since each node contains one item from the universal set,the number of items contained in a tree is equal to the number of nodesin that tree).The algorithm simply selects the tree with the largest number of nodesto become the root of the resultand attaches the root of the smaller tree under that of the larger one.Clearly, the running time of the union-by-size version of <tt>join</tt> is <I>O</I>(1).<P>The following theorem shows that when using the union-by-size join operation,the heights of the resulting trees grow logarithmically.<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremsetsi"> </A>Consider an initial partition <I>P</I> of the universe <IMG WIDTH=149 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66651" SRC="img1553.gif" >comprised of <I>N</I> sets of size 1.Let <I>S</I> be an element of the partition obtained from <I>P</I> aftersome sequence of <em>union-by-size</em> join operations,such that |<I>S</I>|=<I>n</I> for some <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58983" SRC="img341.gif" >.Let <I>T</I> be the tree representing the set <I>S</I>.The height of tree <I>T</I> satisfies the inequality<P> <IMG WIDTH=293 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath67151" SRC="img1638.gif" ><P></BLOCKQUOTE><P> extbfProof (By induction).<P><b>Base Case</b>Since a tree comprised of a single node has height zero,the theorem clearly holds for <I>n</I>=1.<P><b>Inductive Hypothesis</b>Suppose the theorem holds for trees containing <I>n</I> nodesfor <IMG WIDTH=98 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67181" SRC="img1639.gif" > for some <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59027" SRC="img353.gif" >.Consider a union-by-size join operation that produces a treecontaining <I>k</I>+1 nodes.Such a tree is obtained by joining a tree <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67187" SRC="img1640.gif" > having <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67189" SRC="img1641.gif" > nodeswith another tree <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67191" SRC="img1642.gif" > that has <IMG WIDTH=44 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67193" SRC="img1643.gif" > nodes,such that <I>l</I>+<I>m</I>=<I>k</I>+1.<P>Without loss of generality, suppose <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67197" SRC="img1644.gif" >.As a result, <I>l</I> is less than or equal to <I>m</I>.Therefore, the union-by-size algorithm will attach <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67187" SRC="img1640.gif" >under the root of <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67191" SRC="img1642.gif" >.Let <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67207" SRC="img1645.gif" > and <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67209" SRC="img1646.gif" > be the heights of <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67187" SRC="img1640.gif" > and <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67213" SRC="img1647.gif" > respectively.The height of the resulting tree is <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67215" SRC="img1648.gif" >.<P>According to the inductive hypothesis,the height of <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67191" SRC="img1642.gif" > is given by<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray29487" SRC="img1649.gif" ><P>Similarly, the quantity <IMG WIDTH=40 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67219" SRC="img1650.gif" > is bounded by<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray29489" SRC="img1651.gif" ><P>Therefore, the height of the tree containing <I>k</I>+1 nodesis no greater than <IMG WIDTH=220 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67223" SRC="img1652.gif" >.By induction on <I>k</I>, the theorem holds for all values of <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58983" SRC="img341.gif" >.<P>Note that Theorem <A HREF="page410.html#theoremsetsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and its proof does not require thatwe use the collapsing find algorithm of Section <A HREF="page409.html#secsetsfind"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.That is, the height of a tree containing <I>n</I> nodesis guaranteed to be <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" > when the simple find is used.Of course, there is nothing precluding the use of the collapsing findin conjunction with the union-by-size join method.And doing so only makes things better.<P><HR><A NAME="tex2html5902" HREF="page411.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5900" HREF="page403.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5894" HREF="page409.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5904" 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 © 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 + -