page355.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 186 行 · 第 1/2 页

binary tree of height <I>h</I>.
To prove the upper bound we must show that  <IMG WIDTH=103 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66236" SRC="img1443.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1443.gif"  >.
<P>
<b>Base Case</b>
There is exactly one node in a tree of height zero.
Therefore,  <IMG WIDTH=113 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66238" SRC="img1444.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1444.gif"  >.
<P>
<b>Inductive Hypothesis</b>
Assume that  <IMG WIDTH=103 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66236" SRC="img1443.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1443.gif"  > for  <IMG WIDTH=114 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63710" SRC="img1125.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1125.gif"  >, for some  <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61524" SRC="img761.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img761.gif"  >.
Consider the complete binary tree of height <I>k</I>+1
which has the largest number of nodes.
Its left subtree is a perfect tree of height <I>k</I>
and its right subtree is a complete tree of height <I>k</I>
having the largest number of nodes.
<P>
There are exactly  <IMG WIDTH=58 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66252" SRC="img1445.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1445.gif"  > nodes in the perfect left subtree.
From the inductive hypothesis,
there are  <IMG WIDTH=58 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66252" SRC="img1445.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1445.gif"  > nodes in the right subtree.
Thus,
<P> <IMG WIDTH=500 HEIGHT=38 ALIGN=BOTTOM ALT="eqnarray24243" SRC="img1446.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1446.gif"  ><P>
Therefore, by induction  <IMG WIDTH=103 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66236" SRC="img1443.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1443.gif"  > for all  <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63700" SRC="img1122.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1122.gif"  >,
which proves the upper bound.
<P>
It follows from Theorem&nbsp;<A HREF="page355.html#theorempqueuesi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#theorempqueuesi"><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>
that there exists exactly one complete binary tree
that contains exactly <I>n</I> internal nodes
for every integer  <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59063" SRC="img241.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img241.gif"  >.
It also follows from Theorem&nbsp;<A HREF="page355.html#theorempqueuesi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#theorempqueuesi"><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>
that the height of a complete binary tree containing <I>n</I> internal nodes
is  <IMG WIDTH=82 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66266" SRC="img1447.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1447.gif"  >.
<P>
Why are we interested in complete trees?
As it turns out, complete trees have some useful characteristics.
For example,
in the preceding chapter we saw that the internal path length of a tree,
i.e., the sum of the depths of all the internal nodes,
determines the average time for various operations.
A complete binary tree has the nice property that
it has the smallest possible internal path length:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesii">&#160;</A>
The internal path length of a binary tree with <I>n</I> nodes
is at least as big as the internal path length of
a <em>complete</em> binary tree with <I>n</I> nodes.
</BLOCKQUOTE>
<P>
	extbfProof
Consider a binary tree with <I>n</I> nodes that has the smallest possible
internal path length.
Clearly, there can only be one node at depth zero--the root.
Similarly, at most two nodes can be at depth one;
at most four nodes can be at depth two; and so on.
Therefore, the internal path length of a tree with <I>n</I> nodes
is always at least as large as the sum of the first <I>n</I> terms in the series
<P> <IMG WIDTH=393 HEIGHT=36 ALIGN=BOTTOM ALT="displaymath66155" SRC="img1448.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1448.gif"  ><P>
But this summation is precisely the internal path length
of a complete binary tree!
<P>
Since the depth of the average node in a tree is obtained by 
dividing the internal path length of the tree by <I>n</I>,
Theorem&nbsp;<A HREF="page355.html#theorempqueuesii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#theorempqueuesii"><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> tells us that complete trees are the best
possible in the sense that the average depth of a node in a complete
tree is the smallest possible.
But how small is small?
I.e., is does the average depth grow logarithmically with <I>n</I>.
The following theorem addresses this question:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesiii">&#160;</A>
The <em>internal path length</em>
<A NAME=24267>&#160;</A>
of a complete binary tree with <I>n</I> nodes is
<P> <IMG WIDTH=438 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath66156" SRC="img1449.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1449.gif"  ><P></BLOCKQUOTE>
<P>
	extbfProof
The proof of Theorem&nbsp;<A HREF="page355.html#theorempqueuesiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#theorempqueuesiii"><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 left as an exercise for the reader (Exercise&nbsp;<A HREF="page385.html#exercisepqueuesipl" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page385.html#exercisepqueuesipl"><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>).
<P>
From Theorem&nbsp;<A HREF="page355.html#theorempqueuesiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#theorempqueuesiii"><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> we may conclude that
the internal path length of a complete tree is  <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59897" SRC="img405.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img405.gif"  >.
Consequently, the depth of the average node in a complete tree is  <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"  >.
<P>
<BR> <HR>
<UL> 
<LI> <A NAME="tex2html6320" HREF="page356.html#SECTION0012211000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page356.html#SECTION0012211000000000000000">Complete <I>N</I>-ary Trees</A>
</UL>
<HR><A NAME="tex2html6316" HREF="page356.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page356.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="tex2html6314" HREF="page354.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.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="tex2html6308" HREF="page354.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.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="tex2html6318" 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="tex2html6319" 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 &#169; 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>