page307.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 109 行
HTML
109 行
<HTML>
<HEAD>
<TITLE>Successful Search</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="tex2html5725" HREF="page308.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page308.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="tex2html5723" HREF="page306.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page306.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="tex2html5717" HREF="page306.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page306.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="tex2html5727" 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="tex2html5728" 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="SECTION0011310000000000000000">Successful Search</A></H2>
<P>
When a search is successful,
exactly <I>d</I>+1 internal nodes are visited,
where <I>d</I> is the depth in the tree of object of the search.
E.g., if the object of the search is at the root which has depth zero,
the search visits just one node--the root itself.
Similarly, if the object of the search is at depth one,
two nodes are visited, and so on.
We shall assume that it is equally likely for the object of the search
to appear in any node of the search tree.
In that case, the <em>average</em> number of nodes visited during
a successful search is <IMG WIDTH=35 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline64558" SRC="img1243.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1243.gif" >,
where <IMG WIDTH=10 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline64560" SRC="img1244.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1244.gif" > is the average of the depths of the nodes in a given tree.
I.e., given a binary search tree with <I>n</I><I>></I>0 nodes,
<P> <IMG WIDTH=293 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath64550" SRC="img1245.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1245.gif" ><P>
where <IMG WIDTH=11 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64564" SRC="img1246.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1246.gif" > is the depth of the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > node of the tree.
<P>
The quantity <IMG WIDTH=52 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline64568" SRC="img1247.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1247.gif" > is called
the <em>internal path length</em><A NAME=19085> </A><A NAME=19086> </A>.
The internal path length of a tree is simply the sum of the depths (levels)
of all the internal nodes in the tree.
Clearly, the average depth of an internal node is equal
to the internal path length divided by <I>n</I>,
the number of nodes in the tree.
<P>
Unfortunately, for any given number of nodes <I>n</I>,
there are many different possible search trees.
Furthermore,
the internal path lengths of the various possibilities are not equal.
Therefore, to compute the average depth of a node in a tree with <I>n</I> nodes,
we must consider all possible trees with <I>n</I> nodes.
In the absence of any contrary information,
we shall assume that all trees having <I>n</I> nodes are equiprobable
and then compute the average depth of a node in the average tree
containing <I>n</I> nodes.
<P>
Let <I>I</I>(<I>n</I>) be the average internal path length of a tree containing <I>n</I> nodes.
Consider first the case of <I>n</I>=1.
Clearly, there is only one binary tree that contains one node--the tree of height zero.
Therefore, <I>I</I>(1)=0.
<P>
Now consider an arbitrary tree, <IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64590" SRC="img1248.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1248.gif" >,
having <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" > internal nodes altogether,
<I>l</I> of which are found in its left subtree, where <IMG WIDTH=64 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline64596" SRC="img1249.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1249.gif" >.
Such a tree consists of a root,
the left subtree with <I>l</I> internal nodes and
and a right subtree with <I>n</I>-<I>l</I>-1 internal nodes.
The average internal path length for such a tree is the sum
of the average internal path length of the left subtree, <I>I</I>(<I>l</I>),
plus that of the right subtree, <I>I</I>(<I>n</I>-<I>l</I>-1),
plus <I>n</I>-1 because the nodes in the two subtrees
are one level lower in <IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64590" SRC="img1248.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1248.gif" >.
<P>
In order to determine the average internal path length for
a tree with <I>n</I> nodes,
we must compute the average of the internal path lengths of the trees
<IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64590" SRC="img1248.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1248.gif" > averaged over all possible sizes, <I>l</I>,
of the (left) subtree, <IMG WIDTH=64 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline64596" SRC="img1249.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1249.gif" >.
<P>
To do this we consider an ordered set of <I>n</I> distinct keys,
<IMG WIDTH=145 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline64620" SRC="img1250.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1250.gif" >.
If we select the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline64622" SRC="img1251.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1251.gif" > key, <IMG WIDTH=10 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64624" SRC="img1252.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1252.gif" >, to be the root of a binary search tree,
then there are <I>l</I> keys, <IMG WIDTH=14 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64628" SRC="img1253.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1253.gif" >, <IMG WIDTH=13 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64392" SRC="img1220.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1220.gif" >, ..., <IMG WIDTH=27 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline64632" SRC="img1254.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1254.gif" >,
in its left subtree and
<I>n</I>-<I>l</I>-1 keys, <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64636" SRC="img1255.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1255.gif" >, <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64638" SRC="img1256.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1256.gif" >, ..., <IMG WIDTH=31 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline64396" SRC="img1222.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1222.gif" > in its right subtree.
<P>
If we assume that it is equally likely
for any of the <I>n</I> keys to be selected as the root,
then all the subtree sizes in the range <IMG WIDTH=64 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline64596" SRC="img1249.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1249.gif" > are equally likely.
Therefore, the average internal path length for a tree with <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" > nodes is
<P> <IMG WIDTH=500 HEIGHT=101 ALIGN=BOTTOM ALT="eqnarray19093" SRC="img1257.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1257.gif" ><P>
<P>
Thus, in order to determine <I>I</I>(<I>n</I>)
we need to solve the recurrence
<P><A NAME="eqnsrchtreerecurrence"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation19103" SRC="img1258.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1258.gif" ><P>
<P>
To solve this recurrence we consider the case <I>n</I><I>></I>1
and then multiply Equation <A HREF="page307.html#eqnsrchtreerecurrence" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page307.html#eqnsrchtreerecurrence"><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> by <I>n</I> to get
<P><A NAME="eqnsrchtreea"> </A> <IMG WIDTH=500 HEIGHT=46 ALIGN=BOTTOM ALT="equation19113" SRC="img1259.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1259.gif" ><P>
Since this equation is valid for any <I>n</I><I>></I>1,
by substituting <I>n</I>-1 for <I>n</I> we can also write
<P><A NAME="eqnsrchtreeb"> </A> <IMG WIDTH=500 HEIGHT=46 ALIGN=BOTTOM ALT="equation19118" SRC="img1260.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1260.gif" ><P>
which is valid for <I>n</I><I>></I>2.
Subtracting Equation <A HREF="page307.html#eqnsrchtreeb" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page307.html#eqnsrchtreeb"><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> from Equation <A HREF="page307.html#eqnsrchtreea" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page307.html#eqnsrchtreea"><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
<P> <IMG WIDTH=410 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64551" SRC="img1261.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1261.gif" ><P>
which can be rewritten as
<P><A NAME="eqnsrchtreec"> </A> <IMG WIDTH=500 HEIGHT=34 ALIGN=BOTTOM ALT="equation19125" SRC="img1262.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1262.gif" ><P>
<P>
Thus, we have shown the solution to the recurrence
in Equation <A HREF="page307.html#eqnsrchtreerecurrence" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page307.html#eqnsrchtreerecurrence"><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>
is the same as the solution of the recurrence
<P><A NAME="eqnsrchtreed"> </A> <IMG WIDTH=500 HEIGHT=66 ALIGN=BOTTOM ALT="equation19130" SRC="img1263.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1263.gif" ><P><HR><A NAME="tex2html5725" HREF="page308.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page308.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="tex2html5723" HREF="page306.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page306.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="tex2html5717" HREF="page306.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page306.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="tex2html5727" 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="tex2html5728" 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 + -
显示快捷键?