📄 page371.html
字号:
<HTML>
<HEAD>
<TITLE>Binomial Trees</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="tex2html6514" HREF="page372.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page372.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="tex2html6512" HREF="page370.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page370.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="tex2html6506" HREF="page370.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page370.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="tex2html6516" 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="tex2html6517" 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="SECTION0012410000000000000000">Binomial Trees</A></H2>
<P>
A binomial tree is a general tree with a very special shape:
<P>
<BLOCKQUOTE> <b>Definition (Binomial Tree)</b><A NAME="defnbinomialtree"> </A>
The <em>binomial tree of order <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" ></em> with root <I>R</I>
is the tree <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66576" SRC="img1498.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1498.gif" > defined as follows
<OL><LI> If <I>k</I>=0, <IMG WIDTH=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66580" SRC="img1499.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1499.gif" >.
I.e., the binomial tree of order zero consists of a single node, <I>R</I>.<LI> If <I>k</I><I>></I>0, <IMG WIDTH=194 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66586" SRC="img1500.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1500.gif" >.
I.e., the binomial tree of order <I>k</I><I>></I>0 comprises the root <I>R</I>,
and <I>k</I> binomial subtrees, <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66594" SRC="img1501.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1501.gif" >, <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66596" SRC="img1502.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1502.gif" >, ..., <IMG WIDTH=36 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline66598" SRC="img1503.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1503.gif" >.
</OL></BLOCKQUOTE>
<P>
Figure <A HREF="page371.html#figbinom1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page371.html#figbinom1"><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 first five binomial trees, <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66594" SRC="img1501.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1501.gif" >- <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66602" SRC="img1504.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1504.gif" >.
It follows directly from Definition <A HREF="page371.html#defnbinomialtree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page371.html#defnbinomialtree"><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 root of <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66576" SRC="img1498.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1498.gif" >,
the binomial tree of order <I>k</I>,
has degree <I>k</I>.
Since <I>k</I> may arbitrarily large,
so too can the degree of the root.
Furthermore, the root of a binomial tree has the largest fanout of
any of the nodes in that tree.
<P>
<P><A NAME="26877"> </A><A NAME="figbinom1"> </A> <IMG WIDTH=575 HEIGHT=426 ALIGN=BOTTOM ALT="figure26610" SRC="img1505.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1505.gif" ><BR>
<STRONG>Figure:</STRONG> Binomial Trees <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66594" SRC="img1501.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1501.gif" >, <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66596" SRC="img1502.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1502.gif" >, ..., <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66602" SRC="img1504.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1504.gif" ><BR>
<P>
<P>
The number of nodes in a binomial tree of order <I>k</I> is a function of <I>k</I>:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesv"> </A>
The binomial tree of order <I>k</I>, <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66576" SRC="img1498.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1498.gif" >,
contains <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58821" SRC="img179.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img179.gif" > nodes.
</BLOCKQUOTE>
<P>
extbfProof (By induction).
Let <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline66638" SRC="img1506.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1506.gif" > be the number of nodes in <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66576" SRC="img1498.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1498.gif" >,
a binomial tree of order <I>k</I>.
<P>
<b>Base Case</b>
By definition, <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66594" SRC="img1501.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1501.gif" > consists a single node.
Therefore <IMG WIDTH=82 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66646" SRC="img1507.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1507.gif" >.
<P>
<b>Inductive Hypothesis</b>
Assume that <IMG WIDTH=53 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66648" SRC="img1508.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1508.gif" > for <IMG WIDTH=110 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66650" SRC="img1509.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1509.gif" >, for some <IMG WIDTH=33 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66652" SRC="img1510.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1510.gif" >.
Consider the binomial tree of order <I>l</I>+1:
<P> <IMG WIDTH=359 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66564" SRC="img1511.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1511.gif" ><P>
Therefore the number of nodes in <IMG WIDTH=31 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66656" SRC="img1512.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1512.gif" > is given by
<P> <IMG WIDTH=500 HEIGHT=168 ALIGN=BOTTOM ALT="eqnarray26890" SRC="img1513.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1513.gif" ><P>
Therefore, by induction on <I>l</I>, <IMG WIDTH=53 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66648" SRC="img1508.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1508.gif" > for all <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" >.
<P>
It follows from Theorem <A HREF="page371.html#theorempqueuesv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page371.html#theorempqueuesv"><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 binomial trees only come
in sizes that are a power of two.
I.e., <IMG WIDTH=155 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66664" SRC="img1514.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1514.gif" >.
Furthermore, for a given power of two,
there is exactly one shape of binomial tree.
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesvi"> </A>
The height of <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66576" SRC="img1498.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1498.gif" >, the binomial tree of order <I>k</I>, is <I>k</I>.
</BLOCKQUOTE>
<P>
extbfProof (By induction).
Let <IMG WIDTH=15 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66672" SRC="img1515.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1515.gif" > be the height of <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66576" SRC="img1498.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1498.gif" >,
a binomial tree of order <I>k</I>.
<P>
<b>Base Case</b>
By definition, <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66594" SRC="img1501.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1501.gif" > consists a single node.
Therefore <IMG WIDTH=44 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66680" SRC="img1516.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1516.gif" >.
<P>
<b>Inductive Hypothesis</b>
Assume that <IMG WIDTH=46 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66682" SRC="img1517.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1517.gif" > for <IMG WIDTH=110 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66650" SRC="img1509.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1509.gif" >, for some <IMG WIDTH=33 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66652" SRC="img1510.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1510.gif" >.
Consider the binomial tree of order <I>l</I>+1:
<P> <IMG WIDTH=359 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66564" SRC="img1511.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1511.gif" ><P>
Therefore the height <IMG WIDTH=31 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66656" SRC="img1512.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1512.gif" > is given by
<P> <IMG WIDTH=500 HEIGHT=75 ALIGN=BOTTOM ALT="eqnarray26911" SRC="img1518.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1518.gif" ><P>
Therefore, by induction on <I>l</I>, <IMG WIDTH=46 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66682" SRC="img1517.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1517.gif" > for all <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" >.
<P>
Theorem <A HREF="page371.html#theorempqueuesvi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page371.html#theorempqueuesvi"><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 the height of a binomial tree of order <I>k</I>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -