page411.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 96 行
HTML
96 行
<HTML>
<HEAD>
<TITLE>Union by Size</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html7003" HREF="page412.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page412.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7001" HREF="page404.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page404.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6995" HREF="page410.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page410.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7005" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7006" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0013430000000000000000">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="page409.html#figsets3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page409.html#figsets3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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 tree
under 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=29997> </A> join algorithm.
Program <A HREF="page411.html#progpartition5c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page411.html#progpartition5c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows how this can be done.
<P>
<P><A NAME="30245"> </A><A NAME="progpartition5c"> </A> <IMG WIDTH=575 HEIGHT=334 ALIGN=BOTTOM ALT="program29999" SRC="img1683.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1683.gif" ><BR>
<STRONG>Program:</STRONG> <tt>PartitionAsForest</tt> Class Union-by-Size <tt>Join</tt> Member Function Definition<BR>
<P>
<P>
The implementation uses the <tt>count</tt> field
of the <tt>Container</tt> class, from which <tt>PartitionTree</tt> is derived,
to 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 nodes
in that tree).
The algorithm simply selects the tree with the largest number of nodes
to become the root of the result
and 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=150 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67278" SRC="img1605.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1605.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> after
some sequence of <em>union-by-size</em> join operations,
such that |<I>S</I>|=<I>n</I> for some <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59533" SRC="img344.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img344.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=17 ALIGN=BOTTOM ALT="displaymath67766" SRC="img1684.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1684.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> nodes
for <IMG WIDTH=100 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67796" SRC="img1685.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1685.gif" > for some <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline59577" SRC="img356.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img356.gif" >.
Consider a union-by-size join operation that produces a tree
containing <I>k</I>+1 nodes.
Such a tree is obtained by joining a tree <IMG WIDTH=12 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67802" SRC="img1686.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1686.gif" > having <IMG WIDTH=35 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline67804" SRC="img1687.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1687.gif" > nodes
with another tree <IMG WIDTH=19 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67806" SRC="img1688.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1688.gif" > that has <IMG WIDTH=44 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline67808" SRC="img1689.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1689.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_inline67812" SRC="img1690.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1690.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=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67802" SRC="img1686.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1686.gif" >
under the root of <IMG WIDTH=19 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67806" SRC="img1688.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1688.gif" >.
Let <IMG WIDTH=12 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67822" SRC="img1691.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1691.gif" > and <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67824" SRC="img1692.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1692.gif" > be the heights of <IMG WIDTH=12 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67802" SRC="img1686.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1686.gif" > and <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67828" SRC="img1693.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1693.gif" > respectively.
The height of the resulting tree is <IMG WIDTH=110 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67830" SRC="img1694.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1694.gif" >.
<P>
According to the inductive hypothesis,
the height of <IMG WIDTH=19 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67806" SRC="img1688.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1688.gif" > is given by
<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray30020" SRC="img1695.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1695.gif" ><P>
Similarly, the quantity <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67834" SRC="img1696.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1696.gif" > is bounded by
<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray30022" SRC="img1697.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1697.gif" ><P>
Therefore, the height of the tree containing <I>k</I>+1 nodes
is no greater than <IMG WIDTH=221 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline67838" SRC="img1698.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1698.gif" >.
By induction on <I>k</I>, the theorem holds for all values of <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59533" SRC="img344.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img344.gif" >.
<P>
Note that Theorem <A HREF="page411.html#theoremsetsi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page411.html#theoremsetsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> and its proof does not require that
we use the collapsing find algorithm of Section <A HREF="page410.html#secsetsfind" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page410.html#secsetsfind"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
I.e., the height of a tree containing <I>n</I> nodes
is guaranteed to be <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" > when the simple find is used.
Of course, there is nothing precluding the use of the collapsing find
in conjunction with the union-by-size join routine.
And doing so only makes things better.
<P>
<HR><A NAME="tex2html7003" HREF="page412.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page412.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7001" HREF="page404.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page404.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6995" HREF="page410.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page410.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7005" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7006" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?