page255.html

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

a significant number of external nodes.
The following theorem tells us precisely how many external nodes we can expect:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theoremtreesi">&#160;</A>
An <I>N</I>-ary tree with  <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"  > internal nodes
contains (<I>N</I>-1)<I>n</I>+1 external nodes.
</BLOCKQUOTE>
<P>
	extbfProof
Let the number of external nodes be <I>l</I>.
Since every node except the root (empty or not) has a parent,
there must be (<I>n</I>+<I>l</I>-1)/<I>N</I> parents in the tree
since every parent has <I>N</I> children.
Therefore, <I>n</I>=(<I>n</I>+<I>l</I>-1)/<I>N</I>.
Rearranging this gives <I>l</I>=(<I>N</I>-1)<I>n</I>+1.
<P>
Since the external nodes have no subtrees,
it is tempting to consider them to be the leaves of the tree.
However, in the context of <I>N</I>-ary trees,
it is customary to define a <em>leaf node</em><A NAME=15513>&#160;</A>
as an internal node which has only external subtrees.
According to this definition,
the trees shown in Figure&nbsp;<A HREF="page255.html#figtree3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#figtree3"><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> have exactly the same
sets of leaves as the corresponding
general trees shown in Figure&nbsp;<A HREF="page251.html#figtree1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page251.html#figtree1"><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>
Furthermore, since height is defined with respect to the leaves,
by having the leaves the same for both kinds of trees,
the heights are also the same.
The following theorem tells us something about
the maximum size of a tree of a given height <I>h</I>:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theoremtreesii">&#160;</A>
Consider an <I>N</I>-ary tree <I>T</I> of height  <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"  >.
The maximum number of internal nodes in <I>T</I> is given by
<P> <IMG WIDTH=285 HEIGHT=35 ALIGN=BOTTOM ALT="displaymath63606" SRC="img1123.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1123.gif"  ><P></BLOCKQUOTE>
<P>
	extbfProof (By induction).
<P>
<b>Base Case</b>
Consider an <I>N</I>-ary tree of height zero.
It consists of exactly one internal node and <I>N</I> empty subtrees.
Clearly the theorem holds for <I>h</I>=0 since
<P> <IMG WIDTH=315 HEIGHT=40 ALIGN=BOTTOM ALT="displaymath63607" SRC="img1124.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1124.gif"  ><P>
<P>
<b>Inductive Hypothesis</b>
Suppose the theorem holds 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 a tree of height <I>k</I>+1.
Such a tree consists of a root and <I>N</I> subtrees each of which
contains at most  <IMG WIDTH=139 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63718" SRC="img1126.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1126.gif"  > nodes.
Therefore, altogether the number of nodes is at most
<P> <IMG WIDTH=500 HEIGHT=39 ALIGN=BOTTOM ALT="equation15527" SRC="img1127.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1127.gif"  ><P>
I.e., the theorem holds for <I>k</I>+1.
Therefore, by induction on <I>k</I>,
the theorem is true for all values of <I>h</I>.
<P>
An interesting consequence of Theorems&nbsp;<A HREF="page255.html#theoremtreesi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#theoremtreesi"><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&nbsp;<A HREF="page255.html#theoremtreesii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#theoremtreesii"><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 that the maximum number of external nodes
in an <I>N</I>-ary tree of height <I>h</I> is given by
<P> <IMG WIDTH=362 HEIGHT=39 ALIGN=BOTTOM ALT="displaymath63608" SRC="img1128.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1128.gif"  ><P>
<P>
The final theorem of this section addresses the maximum number of <em>leaves</em>
in an <I>N</I>-ary tree of height <I>h</I>:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theoremtreesiii">&#160;</A>
Consider an <I>N</I>-ary tree <I>T</I> of height  <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"  >.
The maximum number of leaf nodes in <I>T</I> is  <IMG WIDTH=21 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline63742" SRC="img1129.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1129.gif"  >.
</BLOCKQUOTE>
<P>
	extbfProof (By induction).
<P>
<b>Base Case</b>
Consider an <I>N</I>-ary tree of height zero.
It consists of exactly one internal node which has <I>N</I> empty subtrees.
Therefore, the one node is a leaf.
Clearly the theorem holds for <I>h</I>=0 since  <IMG WIDTH=50 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline63750" SRC="img1130.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1130.gif"  >.
<P>
<b>Inductive Hypothesis</b>
Suppose the theorem holds 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 a tree of height <I>k</I>+1.
Such a tree consists of a root and <I>N</I> subtrees each of which
contains at most  <IMG WIDTH=21 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline63760" SRC="img1131.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1131.gif"  > leaf nodes.
Therefore, altogether the number of leaves is at most  <IMG WIDTH=115 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63762" SRC="img1132.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1132.gif"  >.
I.e., the theorem holds for <I>k</I>+1.
Therefore, by induction on <I>k</I>,
the theorem is true for all values of <I>h</I>.
<P>
<HR><A NAME="tex2html5070" HREF="page256.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page256.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="tex2html5068" HREF="page250.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page250.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="tex2html5062" HREF="page254.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page254.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="tex2html5072" 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="tex2html5073" 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>