📄 page410.html
字号:
<HTML>
<HEAD>
<TITLE>Collapsing Find</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="tex2html6991" HREF="page411.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page411.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="tex2html6989" 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="tex2html6983" HREF="page409.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page409.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="tex2html6993" 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="tex2html6994" 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="SECTION0013420000000000000000">Collapsing Find</A></H2>
<A NAME="secsetsfind"> </A>
<P>
Unfortunately, using the <tt>Join</tt> algorithm given in Program <A HREF="page409.html#progpartition3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page409.html#progpartition3c"><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>
can result in particularly bad trees.
E.g., Figure <A HREF="page410.html#figsets4" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page410.html#figsets4"><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 the worst possible tree that can be obtained.
Such a tree is bad because its height is <I>O</I>(<I>N</I>).
In such a tree both the worst case and the average case running time
for the <tt>Find</tt> operation is <I>O</I>(<I>N</I>).
<P>
<P><A NAME="29824"> </A><A NAME="figsets4"> </A> <IMG WIDTH=575 HEIGHT=271 ALIGN=BOTTOM ALT="figure29630" SRC="img1680.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1680.gif" ><BR>
<STRONG>Figure:</STRONG> A Degenerate Tree<BR>
<P>
<P>
There is an interesting trick we can play
that can improve matters significantly.
Recall that the find operation starts from a given node
and locates the root of the tree containing that node.
If, having found the root,
we replace the parent pointer of the given node with a pointer to the root,
the next time we do a <tt>Find</tt> it will be more efficient.
<P>
In fact, we can go one step further and replace the parent pointer
of every node along the search path to the root.
This is called
a <em>collapsing find</em><A NAME=29829> </A><A NAME=29830> </A>
operation.
Doing so does not change the asymptotic complexity
of the <tt>Find</tt> operation.
However, a subsequent <tt>Find</tt> operation which begins at any point
along the search path to the root will run in constant time!
<P>
Program <A HREF="page410.html#progpartition4c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page410.html#progpartition4c"><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> gives the code for
a collapsing version of the <tt>Find</tt> operation.
The <tt>Find</tt> function first determines the root node as before.
Then, a second pass is made up the chain from the initial node to the root,
during which the parent pointer of each node is made to point at the root.
Clearly, this version of <tt>Find</tt> is slower than the
one given in Program <A HREF="page409.html#progpartition2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page409.html#progpartition2c"><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> because it makes two passes
up the chain rather than one.
However, the running of this version of <tt>Find</tt> is still <I>O</I>(<I>d</I>),
where <I>d</I> is the depth of the node from which the search begins.
<P>
<P><A NAME="29863"> </A><A NAME="progpartition4c"> </A> <IMG WIDTH=575 HEIGHT=315 ALIGN=BOTTOM ALT="program29839" SRC="img1681.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1681.gif" ><BR>
<STRONG>Program:</STRONG> <tt>PartitionAsForest</tt> Class Collapsing <tt>Find</tt> Member Function Definition<BR>
<P>
<P>
Figure <A HREF="page410.html#figsets5" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page410.html#figsets5"><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> illustrates the effect of a collapsing find operation.
After the find,
all the nodes along the search path are attached directly to the root.
I.e., they have had their depths decreased to one.
As a side-effect, any node which is in the subtree of a node along the search
path may have its depth decreased by the collapsing find operation.
The depth of a node is never increased by the find operation.
Eventually, if we do enough collapsing find operations,
it is possible to obtain a tree of height one
in which all the non-root nodes point directly at the root.
<P>
<P><A NAME="29991"> </A><A NAME="figsets5"> </A> <IMG WIDTH=575 HEIGHT=181 ALIGN=BOTTOM ALT="figure29849" SRC="img1682.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1682.gif" ><BR>
<STRONG>Figure:</STRONG> Example of Collapsing Find<BR>
<P><HR><A NAME="tex2html6991" HREF="page411.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page411.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="tex2html6989" 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="tex2html6983" HREF="page409.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page409.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="tex2html6993" 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="tex2html6994" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -